詰将棋創作プログラミング 3 裸玉全検の可能性
[2014年1月12日最終更新]
詰将棋創作プログラミング 3 裸玉全検の可能性
1) 持駒サーチがあれば、裸玉の全検ができる?
裸玉とは、盤面玉1枚だけの詰将棋。詰方の駒が1枚もないので、普通の詰将棋に比べてずっと詰めにくい(持駒がその分たくさんいる)。詰めるには持駒は最低でも3枚必要(12玉または92玉で持駒飛飛金)で、それ以外の場合は4枚以上なければ詰まない。
裸玉は盤面は玉だけで決定しているので、持駒サーチだけで完全作を探せるように思える。それを81か所の玉位置すべてに対して(実際には左右対称な位置は調べる必要がないので、1筋から5筋の45か所)調べれば、原理的にはすべての裸玉が求まるはずだ。
これはある意味正しいが、実際に実行しようとすると、現実的に許容できる時間でできるかどうかが問題になってくる。単一の作品だけ考えても、例えば岡村孝雄さんの「驚愕の曠野」は、柿木将棋では時間をかけても詰めることができない。この詰将棋は、もっとも強力と思われる岸本章宏さんのプログラムが335925秒かけて詰めたと報告されているが、これは変別解で、完全性を検証しようとすれば、はるかに多くの時間が必要と推測される。
完全と判明している作品でも解けない、完全性を検証できないということは、他に完全作があっても見つけることができないということで、現在の詰将棋プログラムでは、どれを利用しようとも完全作をもれなく探すことは不可能である。
2) 持駒サーチで新規の裸玉が見つけられるか?
詰将棋の創作という観点からは、全検でなくても、新規の裸玉の完全作が一つでも見つかれば大きな成果である。持駒の一つの組み合わせの解答時間、検討時間を抑えても、完全作らしい組み合わせが見つかれば、あとからその組み合わせだけ時間をかけて本当に完全か検証することが可能になる。
ただし、裸玉は持駒の組み合わせ数が3×3×5×5×5×5×19で10万通りを超え、しかも持駒の数が多くないと詰まないので、普通の詰将棋に比べて調べなければならない数がはるかに多い。したがって、実際に調べる数を減らすための工夫が、より重要になってくる。
10万通りの中で詰む組み合わせが均等に分布していれば、二分法で絞るのが効率的だが、実際にはかなり偏りがある。裸玉の中で最もよく調べられているのは11玉(裸玉の検証を参照)である。そこで、11玉の最小持駒リストで、歩の枚数に着目してみると、0枚が最も多く、1枚、2枚とだんだん減ってきて、5枚ぐらいでほとんどなくなる。ところが歩17枚、歩18枚になると詰む組み合わせがかなりある。これは歩の合駒がなくなるためにほかの強い駒を渡さざるを得なくなって詰むパターンである。各駒のこういった事情を踏まえて調べる順を決めれば、かなり時間を短縮できる。
分布の状況を把握するために、エクセルで10万通り全部の状態が可視化できるテンプレートを作って、11玉についてすべて埋めてみた。一部のイメージを示すと、例えば飛0枚角2枚のケースはこんな感じ。
3) 実際に11玉裸玉で試行して、実現性を確かめる
とりあえず簡単な実装として、基本的には飛角金銀桂香歩の順に枚数を1枚ずつ増やしながら詰むかどうか確認することにし、桂香歩については、事前に上限枚数(ただし歩は18枚でなく16枚)で詰むかどうか確認するようにしてみた。例えば桂4で詰まないとわかれば、桂1、桂2、桂3のチェックをスキップできる。
(厳密には、時間の上限を決めているときには成り立たないことがある。香1枚なら詰むが香4枚だと読む量が増えて時間切れになるなど)
柿木将棋での解答時間の上限は5分、検討時間は1手100秒、進行度300上限で、余詰が1件でも見つかったら検討打切りとした。また、完全な全検を目的としたわけではないので、持駒枚数の上限を15枚とした。
これで11玉の持駒サーチ全体がどのくらいで完了するのか、現在判明している最小持駒がこの時間設定でどのくらいカバーできるのか、既存の完全作が見つかるか、といった点が評価ポイントである。
既存の調査結果との比較が容易になるように、実行結果全体のログとともに、完全作候補リスト、最小持駒リストも出力するようにした。
4) 11玉では最小持駒の9割以上をカバー
実行時間は約16時間。なんとか現実的な範囲内に収まった。
11玉の最小持駒リストでは、169通りの組み合わせがあるが、そのうち17通りは歩17枚または18枚を含むもので、駒余りになるため完全には成りえない。それを除いた152通りの組み合わせのうち、今回の試行で発見されたのは139通り(91%)。9割以上が検出された。最小持駒である既発表作は、完全、不完全ともすべてこの中に含まれている。
また、現在の最小持駒リストの中で最小持駒でないものが1件(飛角角金銀)、リストに抜けている最小持駒が1件(角角銀桂3香香)見つかった。現在のリストは手作業で確認しているため見落としたものと思われる。
裸玉の検証は、筆者が2000年ころに3か月ぐらいかけて調査したものだが、そのときは検出できず、のちに岡村孝雄氏によって発表された11玉 持駒 角角銀3桂歩5、村井秀行氏によって発表された11玉 持駒 角角金桂3歩4の二つの裸玉も今回検出している。
一つの持駒の組み合わせあたり5分という短い時間(2000年のときは30分)の設定だったが、3か月かけた調査とほぼ同等レベルの成果を1日足らずで確認できたことになる。
5) ほかの玉位置で新規の裸玉完全作が見つかるか
11玉での成果に気を良くして、他の玉位置もいくつか同じ制約条件で試してみた。やってみると、そう簡単にはいきそうにないことが見えてきた。
一つは解答能力の問題。発表されている完全作で、柿木将棋で5分で詰められないものがかなりある。11玉は裸玉の中では一番詰めやすい位置なのだ。
一つは完全作でも余詰と答えることがあること。これは変化同手数順に余詰がある場合や柿木将棋が変化別詰を解答した場合に発生。
これらは、ある程度予想されたことであるが、そのレベルで検出できる作品が実はもうかなり調べられていて、新たな発見は難しいというのが現状。12玉から19玉までやってみたが、新規の発見は17玉の1件だけだった(それも精査したら余詰)。
特に岡村孝雄さんは多くの玉位置について柿木将棋にはなかなか解けないような裸玉を多数発表しており、かなり高度なレベルで調査検討していると推測される。
新裸玉が見つかるようなら、クラウドで45VMを一定期間かりて11玉から59玉まで裸玉全体の調査をやろうかとも考えていたが、もうすこし考えなければならないようだ。
| 固定リンク
「コンピュータ詰将棋」カテゴリの記事
- 詰将棋創作プログラミング 26 同一作リストの分析(2019.03.27)
- 詰将棋創作プログラミング 25 記録に挑戦!(2018.08.30)
- 詰将棋創作プログラミング 24 飛角図式のランダム生成(2018.01.22)
- 詰将棋創作プログラミング 23 柿木将棋自動化の効果(2017.01.22)
- 詰将棋創作プログラミング 22 詰将棋創作AIを作るには(2017.01.17)
コメント
21玉裸玉をKomoringHeightsで不完全ながら全検してみましたが、完全図候補はことごとく余詰祭りでした。
かなり残念な図(確認できた余詰めはひとつだけで最短手順とほぼ変わりませんが、2手長く微妙に駒の位置が変わってしまう)が以下のものです。
後手の持駒: 飛二 角 金 銀二 桂四 香四 歩十六
9 8 7 6 5 4 3 2 1
+---------------------------+
| ・ ・ ・ ・ ・ ・ ・v玉 ・|一
| ・ ・ ・ ・ ・ ・ ・ ・ ・|二
| ・ ・ ・ ・ ・ ・ ・ ・ ・|三
| ・ ・ ・ ・ ・ ・ ・ ・ ・|四
| ・ ・ ・ ・ ・ ・ ・ ・ ・|五
| ・ ・ ・ ・ ・ ・ ・ ・ ・|六
| ・ ・ ・ ・ ・ ・ ・ ・ ・|七
| ・ ・ ・ ・ ・ ・ ・ ・ ・|八
| ・ ・ ・ ・ ・ ・ ・ ・ ・|九
+---------------------------+
先手の持駒: 角 金三 銀二 歩二
投稿: Rm7367 | 2022.09.17 16:09
21玉裸玉の全検、お疲れ様です。私も昔調べたことがあって、持駒角金3銀銀歩歩の結果は次のようになっていました。
>角 金三 銀二 歩二 : 27手で詰みました(▲4三角、0:05)。
> 余詰:1、非限定:0、手順前後:0、迂回:0 検出しました。
裸玉は昔からかなり調べられているので、完全作の発見はかなりハードルが高いですね。発見できたら、ぜひおもちゃ箱の研究展示室にご投稿ください。
投稿: TETSU | 2022.09.18 00:35