飛び駒を考慮した逆算法に基づく詰将棋問題の列挙

Presentation on theme: "飛び駒を考慮した逆算法に基づく詰将棋問題の列挙"— Presentation transcript:

1 飛び駒を考慮した逆算法に基づく詰将棋問題の列挙
○川原　純　　　京都大学大学院　情報学研究科 　 蟻塚　正樹　 京都大学　工学部 　 堀山　貴史　 埼玉大学大学院　理工学研究科　　　 　 伊藤　大雄 　 京都大学大学院　情報学研究科

2 詰将棋とは 駒を動かし、玉を詰ませるゲーム 初期盤面 … 攻方 玉方 詰上がり図 重要なルール：　攻方は常に王手をかけなければならない

3 計算機を用いた詰将棋研究 解く研究 脊尾詰がミクロコスモス（1525手詰）を解く (1997) 創作する研究 逆算法を用いた自動生成 [Hirose, et al., 1998] １八裸玉の数え上げ [Koyama, 2000] 金銀図式の数え上げ [Noshita, et al., 2002] 知られている最長

4 本研究の目標 すべての詰将棋問題を列挙 究極の目標 使用駒を限定した詰将棋問題の全列挙 例）桂馬4枚と玉
すべての詰将棋問題を列挙　　　究極の目標 使用駒を限定した詰将棋問題の全列挙　例）桂馬4枚と玉 飛び駒（飛車、角、香）なし　[中塚, 堀山, 岩間 2004] 飛び駒あり 今回

5 詰将棋問題創作の難しさ ある局面が詰将棋の問題として成立しているか判定するのは難しい 詰将棋の問題として正しいかの 判定は難しい
適当に駒をいくつか並べた局面

6 詰将棋の問題の成立要件 攻方が適切な手を選べば、玉方がどのように 逃げても詰む 逆に、攻め手（王手をかける手）が なくなる場合は不詰となる
　　逃げても詰む 逆に、攻め手（王手をかける手）が なくなる場合は不詰となる 玉 金 攻め手がない 攻方 玉方 攻方 玉方 詰 詰

7 詰将棋の問題の成立要件 2. ある手番に詰みへのパスが2つ以上あっては いけない 3. 詰んだときに持ち駒が余っては いけない 攻方
どちらを選んでも詰みにたどりつく　→× 余詰 玉方 詰将棋とは認めない （最後の1手を除く） 3. 詰んだときに持ち駒が余っては いけない 詰 詰 詰 駒余り

8 どうやって局面が詰将棋であることを示すか？
詰将棋生成研究の難しさ どうやって局面が詰将棋であることを示すか？ 　　　　　　　　不詰（詰まないこと） 詰将棋　＝　余詰（手を変えても詰むこと）　　　　のない局面 　　　　　　　　駒余り（詰み上がりに駒が余ること） 既存の研究 本研究 詰将棋の解答プログラムに 解かせる すべての詰将棋問題を列挙し、 データベースを作成することで、 高速判定が可能に 欠点：実行に時間がかかる 金銀図式の数え上げ　　普通の計算機で２週間 １八裸玉の数え上げ　　　　３００MIPS年

9 発表の概要 列挙アルゴリズムの概要 飛び駒の導入によって生じる問題の考察と対応 列挙の結果

10 アルゴリズム：逆算法 詰んだ状態から手を逆にたどる 3手詰 玉方手番 1手詰 詰上がり図 同様にこれは3手詰の詰将棋
これは1手詰の詰将棋になっている （ただし、不詰、余詰がある可能性がある）

11 逆算法に基づく列挙 1. すべての詰め上がり図を列挙する … （飛び駒がない場合） 単純な方法 玉をマスに置く 王手をかける駒を置く
玉の逃げ場所がなくなるまで駒を置く すべての置き方を考える …

12 逆算法に基づく列挙 2-1. 攻方について1手戻す （飛び駒がない場合） 王手を解除する 玉 金 玉 金 玉 金 余詰の判定も行う
2-1. 攻方について1手戻す 王手を解除する 玉 金 玉 金 玉 金 余詰の判定も行う 詰め上がり図

13 逆算法に基づく列挙 2-2. 玉方について一手戻す （飛び駒がない場合） 王手がかかるようにする 玉 金 玉 金 玉 金 玉 金 玉 金 玉
2-2. 玉方について一手戻す 王手がかかるようにする 玉 金 玉 金 玉 金 玉 金 玉 金 玉 金 不詰の判定も行う

14 逆算法に基づく列挙 2-1 と 2-2 を繰り返す … … … … （飛び駒がない場合） 逆算木を構築 （幅優先探索） 攻方 3手詰詰将棋
2-1 と を繰り返す 逆算木を構築 （幅優先探索） … … 攻方 3手詰詰将棋 … … 玉方 攻方 1手詰詰将棋 詰め上がり図 詰め上がり図 詰め上がり図 詰め上がり図

15 データ構造（局面集合） まとめて 表す 局面集合 明示的な駒 玉 金 玉 金 暗黙的な駒 玉 金 余剰な駒（王手に関係しない） 玉 金 玉
｛駒無、金｝ ｛駒無、金｝ 局面集合

16 逆算木と局面集合 逆算は局面集合に対して行う 逆算木の各ノードが局面集合に対応する 模式図 攻方 玉 金 ｛駒無, 金｝

17 飛び駒の導入 飛び駒を導入して変わる点は4つ 手の戻し方が増える 局面集合の考慮が必要 玉方持ち駒の概念が生じる 無駄合いの概念が生じる

18 飛び駒の導入 (1) 手の戻し方 飛び駒がない場合、王手をかけている駒（王手駒）は ちょうど1つ 飛び駒がある場合、 王手駒は最大で2つ
飛び駒の導入　(1) 手の戻し方 飛び駒がない場合、王手をかけている駒（王手駒）は ちょうど1つ 飛び駒がある場合、 王手駒は最大で2つ 1手戻しではその駒を戻せばよい

19 飛び駒の導入　(1) 手の戻し方 手の戻し方も増える 飛び駒有りの場合 空き王手 両王手 合駒

20 飛び駒の導入 (1) 手の戻し方 飛び駒がない場合、戻す駒は必ず王手駒。 王手駒は明示的駒 飛び駒がある場合、 暗黙的な駒を戻すこともある
飛び駒の導入　(1) 手の戻し方 飛び駒がない場合、戻す駒は必ず王手駒。 王手駒は明示的駒 飛び駒がある場合、 暗黙的な駒を戻すこともある 玉 飛 銀 玉 飛 金 玉 飛 ｛駒無, 銀, 金｝ 場合の数が著しく増える

21 飛び駒の導入 (1) 手の戻し方 飛び駒自身を戻すときは、通過したマスを 駒無にする必要がある 玉 玉 飛 飛 ｛駒無, 金｝
飛び駒の導入　(1) 手の戻し方 飛び駒自身を戻すときは、通過したマスを 駒無にする必要がある 玉 玉 飛 飛 ｛駒無, 金｝ ｛駒無, 金｝ ｛駒無｝ ｛駒無｝ 残り3つは無効

22 飛び駒の導入 (1) 手の戻し方 玉方1手進めのときも、飛び駒を効かせるため 駒無にすることもある 玉 玉 飛 飛 ｛駒無｝ ｛駒無, 金｝
飛び駒の導入　(1) 手の戻し方 玉方1手進めのときも、飛び駒を効かせるため 駒無にすることもある 玉 玉 飛 飛 ｛駒無｝ ｛駒無, 金｝ ｛駒無｝ ｛駒無, 金｝

23 飛び駒の導入 (2) 局面集合 同じ局面集合で、飛び駒が効く場合と効かない場合 1つの局面集合では 表せない 攻方一手戻しによって、 玉
飛び駒の導入　(2) 局面集合 同じ局面集合で、飛び駒が効く場合と効かない場合 攻方一手戻しによって、 王手を解除するとき 玉 金 香 玉 金 ｛駒無, 金｝ ｛駒無, 金｝ 香 ｛駒無, 金｝ 局面集合 1つの局面集合では 表せない

24 飛び駒の導入 (2) 局面集合 同じ局面集合で、飛び駒が効く場合と効かない場合 差の形でそのまま保持する 玉 金 香 ｛駒無, 金｝ 玉 金
飛び駒の導入　(2) 局面集合 同じ局面集合で、飛び駒が効く場合と効かない場合 差の形でそのまま保持する 玉 金 香 ｛駒無, 金｝ 玉 金 香 ｛駒無｝ マイナス

25 飛び駒の導入 (3) 玉方持ち駒 飛び駒がない場合、合い駒できないので、 玉方の持ち駒は使わない 玉 玉方が持ち駒を打って防ぐ → 合い駒
飛び駒の導入　(3) 玉方持ち駒 玉 玉方が持ち駒を打って防ぐ → 合い駒 飛 飛び駒がない場合、合い駒できないので、 玉方の持ち駒は使わない

26 飛び駒の導入 (3) 玉方持ち駒 使用駒を香車4枚と玉1枚に限定した詰将棋 香 玉 香 玉 香 香 香 香 これは詰まない （合い駒できる）
飛び駒の導入　(3) 玉方持ち駒 使用駒を香車4枚と玉1枚に限定した詰将棋 香 玉 香 玉 香 香 香 香 これは詰まない （合い駒できる） これは詰み （合い駒できない） このような合い駒させないためだけに置いた局面は 詰将棋問題として数えない 玉方の持ち駒の概念が必要

27 列挙の結果

28 列挙の結果 １５手詰② （残りは①と同じ） ①、②と左右対称 １５手詰① １５手詰③、④

29 列挙の結果 銀1枚 金1枚 銀2枚 金1枚 銀2枚 金2枚 銀3枚 金2枚 銀3枚 金3枚 銀4枚 金3枚 銀4枚 金4枚 160
詰め上がり図の数 銀1枚　金1枚 銀2枚　金1枚 銀2枚　金2枚 銀3枚　金2枚 銀3枚　金3枚 銀4枚　金3枚 銀4枚　金4枚 160 3,930 46,464 995,666 5,437,340 24,675,097 35,533,434 20分、1200MB メモリ不足のため、列挙できず

30 まとめ 飛び駒を考慮した詰将棋問題の列挙 香車3枚に限定し、実際に列挙を行った 手の戻し方が増える 局面集合の考慮が必要
玉方持ち駒の概念が生じる 無駄合いの概念が生じる 香車3枚に限定し、実際に列挙を行った