京都大学 ○太田圭亮 川原純 伊藤大雄 堀山貴史

Presentation on theme: "京都大学 ○太田圭亮 川原純 伊藤大雄 堀山貴史"— Presentation transcript:

1 京都大学 ○太田圭亮 川原純 伊藤大雄 堀山貴史
金図式・銀図式・桂馬図式の全列挙 京都大学 ○太田圭亮 川原純 伊藤大雄 堀山貴史

2 詰将棋問題 将棋の駒を用いた，攻方と玉方の手番からなるパズル． 金図式とは玉と金のみで構成される詰将棋． 王手をかける 王手を外す
3手詰の詰将棋 玉方手番 1手詰 詰み

3 研究動機 計算機を用いて詰将棋問題を解く研究は，数多く行なわれている． 生成研究は数が少なく， 発展が期待される分野 である．
　 　→1997年に脊尾詰によって現在最長の詰将棋で　　 あるミクロコスモス(1525手詰)が解かれる． 生成研究は数が少なく， 発展が期待される分野 である．

4 どうやって局面が詰将棋であることを示すか？
詰将棋生成研究の難しさ どうやって局面が詰将棋であることを示すか？ 不詰（詰まないこと） 余詰（攻方が手を変えても詰むこと） 駒余り（詰みに攻方持駒が余ること） 余剰な駒 本研究における 詰将棋 ＝ のない局面 既存の研究 本研究 詰将棋の解答プログラム に解かせて判定 逆算法を用いて 詰みのある局面を全生成する 欠点：解答プログラムの実行は 　　　 時間がかかる 解答プログラムを使うことなく 高速に列挙と判定が可能 玉周囲に限定した金銀図式：２週間[野下,飯田02 ] 　 　　　　　１八裸玉　 　　　　　 ：３００MIPS年 [小山00] 逆算法に基づく詰将棋問題の列挙 [中塚ら04]（京大・岩間研）

5 中塚らの研究 逆算法の提案． 局面を拡張した局面集合の提案． 飛び駒（香，飛，角）は使用しないとする． 飛び駒が存在すると，より複雑になる．
・手の戻し方が増える ・玉方持駒の概念が生じる ・王手駒が２つ存在し得る　etc ただし，逆算法アルゴリズムは飛び駒にも対応可 “飛び道具を考慮した逆算法に基づく詰将棋問題の列挙” [蟻塚ら08]（京大・岩間研）

6 逆算法 … 3手詰 玉方手番 1手詰 詰め上がり図 … …

7 局面集合 逆算は局面集合で考える． 王手に関係しない余剰な部分 代表局面 暗黙的な駒 {駒無} 明示的な駒 {金} その時点では
王手に無関係 {駒無，金} 逆算は局面集合で考える． {駒無，金}

8 逆算法による列挙アルゴリズム 全詰め上がり図作成 攻方逆算手探索 余詰判定 DB登録 玉方逆算手探索 不詰判定 DB登録 詰将棋の抽出

9 正しい列挙を行なうアルゴリズムに修正した．
研究目的 アルゴリズムの一部に誤りを発見した 　　・反転局面が詰将棋ではない局面が出力される 　　・余剰な駒を含む局面が出力される 単なる実装上のバグではない 以前の研究 　正しい列挙を行なうアルゴリズムに修正した． アルゴリズムの設計 高速化 スパコン等 並列化 実装 スタート 桂馬図式の列挙 金銀図式の列挙 全駒用いた列挙

10 反転局面が詰将棋でない局面 駒の進め方は左右対称なので，ある局面が詰将棋なら，その反転局面もまた詰将棋である． 互いに 反転局面
もしこの局面が詰将棋なら・・・ こちらも詰将棋であるはず　逆も同様

11 反転局面が詰将棋でない局面 出力された詰将棋の反転局面が詰将棋として出力されているか調べた結果，漏れている局面があった．
反転局面同士の余詰判定が異なってしまっている． 互いに 反転局面 余詰有 余詰無 （正しくは余詰有）

12 本研究における余詰 余詰を厳密に定義する． （余詰：攻方に複数の詰みへの手順がある） 最終手に1手で詰む手順が複数あるもの →余詰としない
　（余詰：攻方に複数の詰みへの手順がある） 最終手に1手で詰む手順が複数あるもの 　→余詰としない 最終手に3手以上で詰む手順があるもの 玉方変化の中に余詰を含むもの 　→余詰とする 変化とは，玉方に複数の手があること． 一般に含まれていても問題はない．

13 最終手に1手の手順が複数ある 詰み 詰み 1手詰 この局面は余詰としない

14 最終手に3手以上の手順がある 詰み 詰み 1手詰 この局面は余詰とする

15 変化に余詰がある場合 余詰無で詰む 余詰有で詰む（左の余詰無と同手数） 変化 玉方手番 この局面は余詰とする 以上の定義に基づき，
余詰の判定，伝播を行なう箇所を修正． 結果，反転局面同士の余詰を正しく判定できた． 攻方手番

16 余剰な駒を含む局面の除去1 局面集合 ⊃ 0手詰 1手詰 暗黙的な駒 {駒無} {金} 余剰な駒を含む局面は除きたい
{駒無，金} {金} 暗黙的な駒 明示的な駒 局面集合 代表局面 0手詰 1手詰 ⊃ ｛駒無，攻桂，・・・｝ 余剰な駒 余剰な駒を含む局面は除きたい →局面集合同士の包含関係の概念を導入 他の局面集合に包含される局面集合は データベースに登録しない

17 包含を考慮した逆算の様子 ・・・ ⊂ ・・・

18 包含を考えるのは同手数のみ ⊂ ２手詰 4手詰 ｛駒無，攻桂，・・・｝ 3手詰 5手詰 異なる詰将棋

19 余剰な駒を含む局面の除去２ 飛び駒が存在しないので，玉方は持駒を打つことはない． 玉に取られるだけの攻方駒は余剰な駒となる．
実際に出力されていた例 7手詰 余剰な駒 5手詰 この2局面を別々に生成したため

20 余剰な駒を含む局面の除去２ 玉方戻しをまとめて生成するよう修正． 玉方戻し 玉方戻し {駒無} {駒無，攻方金} 以上の修正により
玉方戻しをまとめて生成するよう修正．　 玉方戻し 玉方戻し {駒無} {駒無，攻方金} 以上の修正により 余剰な駒を含む局面を除去できた．

21 (IntelRCore2DuoCPUE6850@3GHz)
研究結果 金図式 銀図式 桂馬図式 1手詰 3,491 46,438 12,318 3手詰 1,365 20,924 6,274 5手詰 334 5,786 1,394 7手詰 90 1,266 306 9手詰 2 586 36 11手詰 - 1,184 12 13手詰 112 15手詰 22 17手詰 記憶量(MB) 9 178 38 計算時間(s) 1.67 200.0 16.4

22 (IntelRCore2DuoCPUE6850@3GHz)
研究結果 金3銀1 金2銀2 金1銀3 1手詰 27,070 77,266 96,677 3手詰 12,630 38,505 48,387 5手詰 3,702 11,034 13,588 7手詰 744 2,100 2,618 9手詰 188 764 1,152 11手詰 108 622 1,230 13手詰 4 76 142 15手詰 36 48 17手詰 - 記憶量(MB) 400 479 計算時間(s) 93.1 660.1 951.3

23 生成した詰将棋の例 攻方持駒:金 攻方持駒:銀 金図式9手詰 銀図式15手詰

24 まとめ 今後の課題 逆算法に基づく詰将棋問題の列挙[中塚ら04]のアルゴリズム上の誤りを修正し，実装した．
　 －反転局面同士の余詰を正しく判定 －余剰な駒を含む局面を除去 金図式，銀図式，桂馬図式の全列挙を行なった． アルゴリズムの改良による更なる高速化 今後の課題