金図式・銀図式・桂馬図式の全列挙
京都大学
○太田圭亮
川原純
伊藤大雄
堀山貴史
詰将棋問題
• 将棋の駒を用いた,攻方と玉方の手番からな
るパズル.
• 金図式とは玉と金のみで構成される詰将棋.
王
手
を
か
3手詰の詰将棋 け
る
玉方手番
王
手
を
外
す
1手詰
王
手
を
か
け
る
詰み
研究動機
• 計算機を用いて詰将棋問題を解く研究
は,数多く行なわれている.
→1997年に脊尾詰によって現在最長の詰将棋で
あるミクロコスモス(1525手詰)が解かれる.
• 生成研究は数が少なく,
発展が期待される分野
である.
詰将棋生成研究の難しさ
どうやって局面が詰将棋であることを示すか?
本研究における =
詰将棋
不詰(詰まないこと)
余詰(攻方が手を変えても詰むこと)
駒余り(詰みに攻方持駒が余ること) のない局面
余剰な駒
既存の研究
詰将棋の解答プログラム
に解かせて判定
本研究
逆算法を用いて
詰みのある局面を全生成する
欠点:解答プログラムの実行は
時間がかかる
玉周囲に限定した金銀図式:2週間[野下,飯田02 ]
1八裸玉
:300MIPS年 [小山00]
解答プログラムを使うことなく
高速に列挙と判定が可能
逆算法に基づく詰将棋問題の列挙
[中塚ら04](京大・岩間研)
中塚らの研究
• 逆算法の提案.
• 局面を拡張した局面集合の提案.
• 飛び駒(香,飛,角)は使用しないとする.
飛び駒が存在すると,より複雑になる.
・手の戻し方が増える
・玉方持駒の概念が生じる
・王手駒が2つ存在し得る etc
ただし,逆算法アルゴリズムは飛び駒にも対応可
“飛び道具を考慮した逆算法に基づく詰将棋問題の列挙”
[蟻塚ら08](京大・岩間研)
逆算法
3手詰
玉方手番
1手詰
詰め上がり図
局面集合
王手に関係しない余剰な部分
代表局面
{駒無}
暗黙的な駒
その時点では
王手に無関係
明示的な駒
{金}
{駒無,金}
{駒無,金}
逆算は局面集合で考える.
逆算法による列挙アルゴリズム
全詰め上がり図作成
攻方逆算手探索
余詰判定
DB登録
玉方逆算手探索
不詰判定
DB登録
詰将棋の抽出
研究目的
ス
タ
ー
ト
アルゴリズムの一部に誤りを発見した 単なる実装上のバグではない
・反転局面が詰将棋ではない局面が出力される
・余剰な駒を含む局面が出力される
以前の研究
正しい列挙を行なうアルゴリズムに修正した.
ア
ル
ゴ
ス
高
リ
並
パ
ズ
実
速
列コ
ム
装
化
化ン
の
等
桂
金
全
設
馬
銀
駒
計
図
図
用
式
式
い
た
の
の
列
列
列
挙
挙
挙
反転局面が詰将棋でない局面
• 駒の進め方は左右対称なので,ある局面が
詰将棋なら,その反転局面もまた詰将棋であ
る.
互いに
反転局面
もしこの局面が詰将棋なら・・・
こちらも詰将棋であるはず 逆も同様
反転局面が詰将棋でない局面
• 出力された詰将棋の反転局面が詰将棋として出力
されているか調べた結果,漏れている局面があった.
• 反転局面同士の余詰判定が異なってしまっている.
互いに
反転局面
余詰有
余詰無
(正しくは余詰有)
本研究における余詰
• 余詰を厳密に定義する.
(余詰:攻方に複数の詰みへの手順がある)
• 最終手に1手で詰む手順が複数あるもの
→余詰としない
• 最終手に3手以上で詰む手順があるもの
• 玉方変化の中に余詰を含むもの
→余詰とする
変化とは,玉方に複数の手があること.
一般に含まれていても問題はない.
最終手に1手の手順が複数ある
詰み
詰み
1手詰
この局面は余詰としない
最終手に3手以上の手順がある
詰み
詰み
1手詰
この局面は余詰とする
変化に余詰がある場合
余詰無で詰む
余詰有で詰む(左の余詰無と同手数)
変化
玉方手番
この局面は余詰とする
攻方手番
以上の定義に基づき,
余詰の判定,伝播を行なう箇所を修正.
結果,反転局面同士の余詰を正しく判定できた.
余剰な駒を含む局面の除去1
局面集合
0手詰
1手詰
代表局面
暗黙的な駒
{駒無}
{金}
{駒無,金}
{駒無,金}
明示的な駒
{駒無,攻桂,・・・}
⊃
余剰な駒
余剰な駒を含む局面は除きたい
→局面集合同士の包含関係の概念を導入
他の局面集合に包含される局面集合は
データベースに登録しない
包含を考慮した逆算の様子
・
・
・
⊂
・
・
・
包含を考えるのは同手数のみ
2手詰
⊂
4手詰
{駒無,攻桂,・・・}
3手詰
異なる詰将棋
5手詰
余剰な駒を含む局面の除去2
• 飛び駒が存在しないので,玉方は持駒を打つ
ことはない.
• 玉に取られるだけの攻方駒は余剰な駒となる.
実
際
に
出
力
さ
れ
て
い
た
例
7手詰
余剰な駒
5手詰
この2局面を別々に生成したため
余剰な駒を含む局面の除去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
([email protected])
研究結果
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
([email protected])
生成した詰将棋の例
攻
方
持
駒
銀
:
:
攻
方
持
駒
金
金図式9手詰
銀図式15手詰
まとめ
• 逆算法に基づく詰将棋問題の列挙[中塚ら04]のア
ルゴリズム上の誤りを修正し,実装した.
-反転局面同士の余詰を正しく判定
-余剰な駒を含む局面を除去
• 金図式,銀図式,桂馬図式の全列挙を行なった.
今後の課題
• アルゴリズムの改良による更なる高速化
ダウンロード

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