逆算法に基づく 詰将棋の列挙 堀山貴史 中塚裕之 岩間一雄 （京都大学） 持駒なし ９手詰め.

Presentation on theme: "逆算法に基づく 詰将棋の列挙 堀山貴史 中塚裕之 岩間一雄 （京都大学） 持駒なし ９手詰め."— Presentation transcript:

1 逆算法に基づく 詰将棋の列挙 堀山貴史 中塚裕之 岩間一雄 （京都大学） 持駒なし ９手詰め

2 詰将棋 攻方は王手になる手の中から 手を選択する 攻方 玉方は必ず最善手を選ぶ 玉方 攻方 詰 詰 詰 詰 ×

3 詰将棋　-不詰め- 不詰め 攻方 攻方の手によらず、 玉方が最善手をとれば 詰みがない 玉方 攻方 詰 詰 × 詰 ×

4 詰将棋　-余詰め- 余詰め 攻方 2つ以上の攻方の手に対し、 玉方が最善手をとった場合でも 詰む 玉方 攻方 × 詰 詰 詰 詰 詰

5 詰将棋　-駒余り- 玉 金 金 持駒 詰み上がりに 駒が余っている 金 詰み上がり

6 詰将棋 1525手詰 ミクロコスモス 橋本孝治 941 メタ新世界 山本昭一 901 万里の駒（余詰） 森長宏明 873 新扇詰 奥薗幸雄
脊尾詰が 解く （1997） 1525手詰 ミクロコスモス 橋本孝治 メタ新世界 山本昭一 万里の駒（余詰） 森長宏明 新扇詰 奥薗幸雄 イオニゼーション 橋本孝治 桃花源 添川公司 バベルの塔 変幻自斉 ゴゴノソラ 今村修 ＦＡＩＲＷＡＹ 馬詰恒司、摩利支天 合作 寿 伊藤看寿 煙詰 伊藤看寿

7 詰将棋 解く研究 脊尾詰が現在最長の1525手詰を解く (1997) 創作する研究
玉 金 玉 金 金 金 解く研究 　 脊尾詰が現在最長の1525手詰を解く (1997) 創作する研究 　 逆算法を用いた自動生成 [Hirose, et al., 1998] 　 １八裸玉の数え上げ [Koyama, 2000] 　 金銀図式の数え上げ [Noshita, et al., 2002]

8 どうやって局面が詰将棋であることを示すか？
詰将棋生成研究の難しさ どうやって局面が詰将棋であることを示すか？ 　　　　　　　　不詰め（詰まないこと） 詰将棋　＝　余詰め（手を変えても詰むこと）　　　　のない局面 　　　　　　　　駒余り（詰み上がりに駒が余ること）

9 どうやって局面が詰将棋であることを示すか？
詰将棋生成研究の難しさ どうやって局面が詰将棋であることを示すか？ 　　　　　　　　不詰め（詰まないこと） 詰将棋　＝　余詰め（手を変えても詰むこと）　　　　のない局面 　　　　　　　　駒余り（詰み上がりに駒が余ること） 既存の研究 詰将棋の解答プログラムに解かせる 欠点：解答プログラムの実行時間は長い 金銀図式の数え上げ　　　　普通の高速パソコンで２週間 １八裸玉の数え上げ　　　　　　 ３００MIPS年

10 どうやって局面が詰将棋であることを示すか？ 逆算法を用いて詰みのある局面を全生成する
詰将棋生成研究の難しさ どうやって局面が詰将棋であることを示すか？ 　　　　　　　　不詰め（詰まないこと） 詰将棋　＝　余詰め（手を変えても詰むこと）　　　　のない局面 　　　　　　　　駒余り（詰み上がりに駒が余ること） 本研究 逆算法を用いて詰みのある局面を全生成する 解答プログラムを使うことなく高速に数え上げを行う

11 逆算法 ・・・ 逆順に手を戻して詰め将棋を創作する方法 玉 玉 金 金 金 金 玉 金 金 玉 玉 金 金 金 金 詰み上がり １手詰め 玉
玉方手番 ３手詰め

12 本研究 逆算法の定式化 拡張局面という概念の導入 列挙アルゴリズムの提案 ｛攻方金｝ ｛攻方金｝ ｛駒なし｝ ｛駒なし、攻方歩、…｝ 局面
玉 玉 玉 玉 ｛攻方金｝ ｛攻方金｝ 金 金 金 金 金 金 金 金 ｛駒なし｝ ｛駒なし、攻方歩、…｝ 局面 拡張局面

13 本研究 飛、角、香を用いない図式を列挙する アルゴリズムを構築 実際に、桂図式（玉と桂のみの詰将棋）他を列挙
※ 用いない駒は玉方持駒となっている

14 列挙アルゴリズム 詰め上がり図作成 攻方逆算手探索 余詰め判定 DB登録 玉方逆算手探索 不詰め判定 DB登録 拡張局面から詰将棋の抽出

15 攻方逆算手探索 余詰め（手を変えても詰むこと）の判定 　　局面 攻方手番 余詰めあり １手戻す 　局面 玉方手番 余詰めあり

16 攻方逆算手探索 余詰め（手を変えても詰むこと）の判定 余詰めなし １手進めた 局面の生成 DB 局面 攻方手番 マッチング 手γ ｎ＋１手
　　局面の生成 DB 　　局面 攻方手番 マッチング 手γ ｎ＋１手 手β 手α 　　手α で１手戻し １つは同じ 　局面 玉方手番 ｎ手 余詰めなし ｎ手以下の全ての 詰みがある局面

17 攻方逆算手探索 余詰め（手を変えても詰むこと）の判定 手αとβの２通りの詰め方があるので 余詰めあり 余詰めなし 局面 攻方手番 手β
　　局面 攻方手番 手β マッチしたもの 　　手α で１手戻し 手αとβの２通りの詰め方があるので 　　　　　　　　　余詰めあり 　局面 玉方手番 余詰めなし

18 攻方逆算手探索 有 攻方：ｎ＋１手 同じ局面 ＤＢ 玉方：ｎ手 攻方：ｎ‘＋１手 有 玉方：ｎ‘手

19 攻方逆算手探索 余詰めあり局面も以降の余詰め判定のために 逆算を続ける 有 攻方：ｎ＋２手 ＤＢ 有 玉方：ｎ＋１手 攻方：ｎ手 有

20 逆算手探索 拡張局面の生成 　　拡張局面 攻方手番 生成とは、拡張局面から ある手を１手戻すこと 生成 　拡張局面 玉方手番

21 逆算手探索 拡張局面の生成 手：２二金を２三金に ｛駒なし、攻方金｝ 玉 玉 金 金 金 金 玉 金 金 玉 玉 金 金 金 金 玉 玉 金

22 攻方逆算手探索 余詰め（手を変えても詰むこと）の判定 余詰めなし １手進めた 拡張局面の生成 DB 拡張局面 攻方手番 マッチング 生成
　　拡張局面の生成 DB 　　拡張局面 攻方手番 マッチング 生成 １つは包含される 　拡張局面 玉方手番 ｎ手 余詰めなし ｎ手以下の全ての 詰みがある局面

23 攻方逆算手探索 余詰め（手を変えても詰むこと）の判定 余詰めなし 余詰めあり 余詰めなし 拡張局面 攻方手番 マッチしたもの 生成 拡張局面
　　拡張局面 攻方手番 マッチしたもの 生成 余詰めあり 　拡張局面 玉方手番 ｎ手 余詰めなし

24 玉方逆算手探索 不詰めの判定 １手進めた 局面の生成 DB 局面 玉方手番 マッチング 手γ ｎ＋１手 手β 手α 手α で１手戻し
　　局面の生成 DB 　　局面 玉方手番 マッチング 手γ ｎ＋１手 手β 手α 　　手α で１手戻し １つは同じ 　局面 攻方手番 ｎ手 ｎ手以下の全ての 詰みがある局面

25 玉方逆算手探索 不詰めの判定 手βでは詰みがないか、 より長い手の逃げ方があるので 不詰め マッチしたもの 局面 玉方手番 ｎ＋１手 手β
　　局面 玉方手番 ｎ＋１手 手β マッチしなかったもの 　　手α で１手戻し 手βでは詰みがないか、 より長い手の逃げ方があるので 　　　　　　　　　不詰め 　局面 攻方手番 ｎ手

26 玉方逆算手探索 不詰めの判定 １手進めた 拡張局面の生成 DB 拡張局面 玉方手番 マッチング 生成 １つは包含される 拡張局面 攻方手番
　　拡張局面の生成 DB 　　拡張局面 玉方手番 マッチング 生成 １つは包含される 　拡張局面 攻方手番 ｎ手 ｎ手以下の全ての 詰みがある局面

27 玉方逆算手探索 不詰めの判定 　　拡張局面 玉方手番 マッチしたもの 生成 不詰めなし 　拡張局面 攻方手番

28 玉方逆算手探索 不詰めの判定 　　拡張局面 玉方手番 生成 不詰めなし 　拡張局面 攻方手番

29 詰将棋列挙の結果 詰み 1手 3手 5手 ７手 ９手 11手 - 桂図式 7,524 12,366 6,142 1,188 242 12
詰め手数別の詰将棋の数 詰み 1手 3手 5手 ７手 ９手 11手 桂図式 7,524 12,366 6,142 1,188 242 12 金２歩１図式 1,129 1,750 529 137 60 - 銀２歩１図式 4,671 9,155 2,156 534 328 36 銀１桂２図式 2,985 6,133 1,588 416 220 14 銀１桂１歩１図式 5,769 11,207 2,784 740 414 20 1.83倍

30 詰将棋列挙の結果 列挙に要した資源量 実行時間（s） メモリ量（KB） 拡張局面（個） 桂図式 4,866 648,385 66,542 金２歩１図式 286 80,213 8,232 銀２歩１図式 1,143 268,759 27,582 銀１桂２図式 2,345 199,616 20,486 銀１桂１歩１図式 1,781 348,894 35,806 Pentium4 2.8GHz/1GB (Debian GNU/Linux 3.0)

31 生成された詰将棋例 ９手詰め

32 生成された詰将棋例 ７手詰め

33 生成された詰将棋例 ７手詰め

34 生成された詰将棋例 ９手詰め

35 生成された詰将棋例 １１手詰め

36 まとめ 拡張局面という概念の導入 逆算法による列挙アルゴリズムの提案 桂図式（玉と桂のみの詰将棋）等を列挙 今後の課題
飛、角、香を加えた定式化 さらなる記憶量削減のための拡張局面の検討 他の図式の列挙