飛び駒を考慮した逆算法に基づく 詰将棋問題の列挙 ○川原 蟻塚 堀山 伊藤 純 正樹 貴史 大雄 京都大学大学院 情報学研究科 京都大学 工学部 埼玉大学大学院 理工学研究科 京都大学大学院 情報学研究科 詰将棋とは • 駒を動かし、玉を詰ませるゲーム 初期盤面 … 攻方 玉方 詰上がり図 重要なルール： 攻方は常に王手をかけなければならない 計算機を用いた詰将棋研究 解く研究 脊尾詰がミクロコスモス（1525手詰）を解く (1997) 知られている最長 創作する研究 逆算法を用いた自動生成 [Hirose, et al., 1998] １八裸玉の数え上げ [Koyama, 2000] 金銀図式の数え上げ [Noshita, et al., 2002] 本研究の目標 • すべての詰将棋問題を列挙 究極の目標 • 使用駒を限定した詰将棋問題の全列挙 例）桂馬4枚と玉 – 飛び駒（飛車、角、香）なし [中塚, 堀山, 岩間 2004] – 飛び駒あり 今回 詰将棋問題創作の難しさ • ある局面が詰将棋の問題として成立しているか 判定するのは難しい 詰将棋の問題として正しいかの 判定は難しい 適当に駒をいくつか並べた局面 詰将棋の問題の成立要件 1. 攻方が適切な手を選べば、玉方がどのように 逃げても詰む 逆に、攻め手（王手をかける手）が なくなる場合は不詰となる 攻方 玉 金 玉方 玉 金 攻め手がない 玉方 詰 詰 玉 攻方 詰将棋の問題の成立要件 2. ある手番に詰みへのパスが2つ以上あっては いけない 攻方 どちらを選んでも詰みにたどりつく →× 余詰 玉方 詰 詰将棋とは認めない （最後の1手を除く） 詰 詰 3. 詰んだときに持ち駒が余っては 駒余り いけない 詰将棋生成研究の難しさ どうやって局面が詰将棋であることを示すか？ 不詰（詰まないこと） 詰将棋 ＝ 余詰（手を変えても詰むこと） のない局面 駒余り（詰み上がりに駒が余ること） 既存の研究 本研究 詰将棋の解答プログラムに 解かせる 欠点：実行に時間がかかる すべての詰将棋問題を列挙し、 データベースを作成することで、 高速判定が可能に 金銀図式の数え上げ 普通の計算機で２週間 １八裸玉の数え上げ ３００MIPS年 発表の概要 • 列挙アルゴリズムの概要 • 飛び駒の導入によって生じる問題の考察と対応 • 列挙の結果 アルゴリズム：逆算法 • 詰んだ状態から手を逆にたどる 3手詰 玉方手番 同様にこれは3手詰の詰将棋 1手詰 詰上がり図 これは1手詰の詰将棋になっている （ただし、不詰、余詰がある可能性がある） 逆算法に基づく列挙 （飛び駒がない場合） 1. すべての詰め上がり図を列挙する 単純な方法 玉をマスに置く 王手をかける駒を置く 玉の逃げ場所がなくなるまで駒を置く すべての置き方を考える … 逆算法に基づく列挙 （飛び駒がない場合） 2-1. 攻方について1手戻す 玉 玉 金 玉 金 金 王手を解除する 金 金 金 余詰の判定も行う 詰め上がり図 逆算法に基づく列挙 （飛び駒がない場合） 2-2. 玉方について一手戻す 王手がかかるようにする 玉 玉 金 金 玉 玉 金 金 金 金 玉 金 金 金 玉 金 金 金 不詰の判定も行う 金 逆算法に基づく列挙 （飛び駒がない場合） 2-1 と 2-2 を繰り返す （幅優先探索） … 攻方 … 玉方 逆算木を構築 … 3手詰詰将棋 … 攻方 詰め上がり図 1手詰詰将棋 詰め上がり図 詰め上がり図 詰め上がり図 データ構造（局面集合） 明示的な駒 金 金 玉 玉 玉 金 金 暗黙的な駒 金 金 金 余剰な駒（王手に関係しない） 玉 玉 金 金 金 金 金 金 金 まとめて 表す ｛駒無、金｝ ｛駒無、金｝ 局面集合 逆算木と局面集合 逆算は局面集合に対して行う 逆算木の各ノードが局面集合に対応する 攻方 玉 金 金 ｛駒無, 金｝ ｛駒無, 金｝ 模式図 飛び駒の導入 • 飛び駒を導入して変わる点は4つ 1. 2. 3. 4. 手の戻し方が増える 局面集合の考慮が必要 玉方持ち駒の概念が生じる 無駄合いの概念が生じる 飛び駒の導入 (1) 手の戻し方 • 飛び駒がない場合、王手をかけている駒（王手駒）は ちょうど1つ 1手戻しではその駒を戻せばよい • 飛び駒がある場合、 王手駒は最大で2つ 飛び駒の導入 (1) 手の戻し方 • 手の戻し方も増える 飛び駒有りの場合 空き王手 両王手 合駒 飛び駒の導入 (1) 手の戻し方 • 飛び駒がない場合、戻す駒は必ず王手駒。 王手駒は明示的駒 金 飛 飛 玉 ｛駒無, 銀, 金｝ 玉 場合の数が著しく増える 玉 • 飛び駒がある場合、 暗黙的な駒を戻すこともある 銀 飛 飛び駒の導入 (1) 手の戻し方 • 飛び駒自身を戻すときは、通過したマスを 駒無にする必要がある 玉 ｛駒無, 金｝ ｛駒無, 金｝ 玉 飛 飛 ｛駒無｝ ｛駒無｝ 残り3つは無効 飛び駒の導入 (1) 手の戻し方 • 玉方1手進めのときも、飛び駒を効かせるため 駒無にすることもある 玉 玉 飛 飛 ｛駒無, 金｝ ｛駒無｝ ｛駒無, 金｝ ｛駒無｝ 飛び駒の導入 (2) 局面集合 • 同じ局面集合で、飛び駒が効く場合と効かない場合 玉 玉 玉 玉 攻方一手戻しによって、 王手を解除するとき 金 金 金 金 金 金 玉 金 金 香 ｛駒無, 金｝ 1つの局面集合では 表せない 玉 局面集合 玉 ｛駒無, 金｝ 香 玉 香 香 玉 ｛駒無, 金｝ 香 金 金 金 金 金 金 金 金 香 金 金 金 金 金 香 香 香 飛び駒の導入 (2) 局面集合 • 同じ局面集合で、飛び駒が効く場合と効かない場合 差の形でそのまま保持する 玉 玉 金 金 ｛駒無, 金｝ ｛駒無, 金｝ 香 ｛駒無, 金｝ ｛駒無｝ マイナス ｛駒無｝ 香 ｛駒無｝ 飛び駒の導入 (3) 玉方持ち駒 玉方が持ち駒を打って防ぐ → 合い駒 玉 飛 飛び駒がない場合、合い駒できないので、 玉方の持ち駒は使わない 飛び駒の導入 (3) 玉方持ち駒 使用駒を香車4枚と玉1枚に限定した詰将棋 香 香 玉 これは詰まない （合い駒できる） 玉 香 香 香 香 これは詰み （合い駒できない） このような合い駒させないためだけに置いた局面は 詰将棋問題として数えない 玉方の持ち駒の概念が必要 列挙の結果 列挙の結果 １５手詰② （残りは①と同じ） ①、②と左右対称 １５手詰① １５手詰③、④ 列挙の結果 詰め上がり図の数 銀1枚 銀2枚 銀2枚 銀3枚 銀3枚 銀4枚 銀4枚 160 金1枚 3,930 金1枚 46,464 金2枚 995,666 金2枚 金3枚 5,437,340 金3枚 24,675,097 金4枚 35,533,434 20分、1200MB メモリ不足のため、列挙できず まとめ • 飛び駒を考慮した詰将棋問題の列挙 1. 2. 3. 4. • 手の戻し方が増える 局面集合の考慮が必要 玉方持ち駒の概念が生じる 無駄合いの概念が生じる 香車3枚に限定し、実際に列挙を行った
© Copyright 2024 ExpyDoc
