金図式・銀図式・桂馬図式の全列挙

金図式・銀図式・桂馬図式の全列挙
京都大学
○太田圭亮
川原純
伊藤大雄
堀山貴史
詰将棋問題
• 将棋の駒を用いた，攻方と玉方の手番からな
るパズル．
• 金図式とは玉と金のみで構成される詰将棋．
王
手
を
か
3手詰の詰将棋け
る
玉方手番
王
手
を
外
す
1手詰
王
手
を
か
け
る
詰み
研究動機
• 計算機を用いて詰将棋問題を解く研究
は，数多く行なわれている．
→1997年に脊尾詰によって現在最長の詰将棋で
あるミクロコスモス(1525手詰)が解かれる．
• 生成研究は数が少なく，
発展が期待される分野
である．
詰将棋生成研究の難しさ
どうやって局面が詰将棋であることを示すか？
本研究における＝
詰将棋
不詰（詰まないこと）
余詰（攻方が手を変えても詰むこと）
駒余り（詰みに攻方持駒が余ること）のない局面
余剰な駒
既存の研究
詰将棋の解答プログラム
に解かせて判定
本研究
逆算法を用いて
詰みのある局面を全生成する
欠点：解答プログラムの実行は
時間がかかる
玉周囲に限定した金銀図式：２週間[野下,飯田02 ]
１八裸玉
：３００MIPS年 [小山00]
解答プログラムを使うことなく
高速に列挙と判定が可能
逆算法に基づく詰将棋問題の列挙
[中塚ら04]（京大・岩間研）
中塚らの研究
• 逆算法の提案．
• 局面を拡張した局面集合の提案．
• 飛び駒（香，飛，角）は使用しないとする．
飛び駒が存在すると，より複雑になる．
・手の戻し方が増える
・玉方持駒の概念が生じる
・王手駒が２つ存在し得る etc
ただし，逆算法アルゴリズムは飛び駒にも対応可
“飛び道具を考慮した逆算法に基づく詰将棋問題の列挙”
[蟻塚ら08]（京大・岩間研）
逆算法
3手詰
玉方手番
1手詰
詰め上がり図
局面集合
王手に関係しない余剰な部分
代表局面
{駒無}
暗黙的な駒
その時点では
王手に無関係
明示的な駒
{金}
{駒無，金}
{駒無，金}
逆算は局面集合で考える．
逆算法による列挙アルゴリズム
全詰め上がり図作成
攻方逆算手探索
余詰判定
DB登録
玉方逆算手探索
不詰判定
DB登録
詰将棋の抽出
研究目的
ス
タ
ー
ト
アルゴリズムの一部に誤りを発見した単なる実装上のバグではない
・反転局面が詰将棋ではない局面が出力される
・余剰な駒を含む局面が出力される
以前の研究
正しい列挙を行なうアルゴリズムに修正した．
ア
ル
ゴ
ス
高
リ
並
パ
ズ
実
速
列コ
ム
装
化
化ン
の
等
桂
金
全
設
馬
銀
駒
計
図
図
用
式
式
い
た
の
の
列
列
列
挙
挙
挙
反転局面が詰将棋でない局面
• 駒の進め方は左右対称なので，ある局面が
詰将棋なら，その反転局面もまた詰将棋であ
る．
互いに
反転局面
もしこの局面が詰将棋なら・・・
こちらも詰将棋であるはず逆も同様
反転局面が詰将棋でない局面
• 出力された詰将棋の反転局面が詰将棋として出力
されているか調べた結果，漏れている局面があった．
• 反転局面同士の余詰判定が異なってしまっている．
互いに
反転局面
余詰有
余詰無
（正しくは余詰有）
本研究における余詰
• 余詰を厳密に定義する．
（余詰：攻方に複数の詰みへの手順がある）
• 最終手に1手で詰む手順が複数あるもの
→余詰としない
• 最終手に3手以上で詰む手順があるもの
• 玉方変化の中に余詰を含むもの
→余詰とする
変化とは，玉方に複数の手があること．
一般に含まれていても問題はない．
最終手に1手の手順が複数ある
詰み
詰み
1手詰
この局面は余詰としない
最終手に3手以上の手順がある
詰み
詰み
1手詰
この局面は余詰とする
変化に余詰がある場合
余詰無で詰む
余詰有で詰む（左の余詰無と同手数）
変化
玉方手番
この局面は余詰とする
攻方手番
以上の定義に基づき，
余詰の判定，伝播を行なう箇所を修正．
結果，反転局面同士の余詰を正しく判定できた．
余剰な駒を含む局面の除去1
局面集合
0手詰
1手詰
代表局面
暗黙的な駒
{駒無}
{金}
{駒無，金}
{駒無，金}
明示的な駒
｛駒無，攻桂，・・・｝
⊃
余剰な駒
余剰な駒を含む局面は除きたい
→局面集合同士の包含関係の概念を導入
他の局面集合に包含される局面集合は
データベースに登録しない
包含を考慮した逆算の様子
・
・
・
⊂
・
・
・
包含を考えるのは同手数のみ
２手詰
⊂
4手詰
｛駒無，攻桂，・・・｝
3手詰
異なる詰将棋
5手詰
余剰な駒を含む局面の除去２
• 飛び駒が存在しないので，玉方は持駒を打つ
ことはない．
• 玉に取られるだけの攻方駒は余剰な駒となる．
実
際
に
出
力
さ
れ
て
い
た
例
7手詰
余剰な駒
5手詰
この2局面を別々に生成したため
余剰な駒を含む局面の除去２
• 玉方戻しをまとめて生成するよう修正．
玉方戻し
{駒無}
玉方戻し
{駒無，攻方金}
以上の修正により
余剰な駒を含む局面を除去できた．
研究結果
1手詰
3手詰
5手詰
7手詰
9手詰
11手詰
13手詰
15手詰
17手詰
記憶量(MB)
計算時間(s)
金図式
3,491
1,365
334
90
2
9
1.67
銀図式
桂馬図式
46,438
12,318
20,924
6,274
5,786
1,394
1,266
306
586
36
1,184
12
112
22
178
38
200.0
16.4
(IntelRCore2DuoCPUE6850@3GHz)
研究結果
1手詰
3手詰
5手詰
7手詰
9手詰
11手詰
13手詰
15手詰
17手詰
記憶量(MB)
計算時間(s)
金3銀1
27,070
12,630
3,702
744
188
108
4
4
142
93.1
金2銀2
77,266
38,505
11,034
2,100
764
622
76
36
400
660.1
金1銀3
96,677
48,387
13,588
2,618
1,152
1,230
142
48
479
951.3
(IntelRCore2DuoCPUE6850@3GHz)
生成した詰将棋の例
攻
方
持
駒
銀
:
:
攻
方
持
駒
金
金図式9手詰
銀図式15手詰
まとめ
• 逆算法に基づく詰将棋問題の列挙[中塚ら04]のア
ルゴリズム上の誤りを修正し，実装した．
－反転局面同士の余詰を正しく判定
－余剰な駒を含む局面を除去
• 金図式，銀図式，桂馬図式の全列挙を行なった．
今後の課題
• アルゴリズムの改良による更なる高速化

Download Report