四追い案 解図結果 (反復深化法) | 連珠プログラムを作ってみるブログ

連珠プログラムを作ってみるブログ

趣味で製作中の連珠プログラムの開発ログです.
ひっそり,まったり,のんびりと開発中です.

まずは対局できるところまで!


テーマ:

限珠案solverの方は大体キリのいいところまでいけたので,ここ最近は四追い案(VCF問題)を解図するプログラムの開発に取り組んでいる.


例によって,「夢幻の構想」(龍鷹 編著)に収録されている問題を主に解図しているのだが,収録されている問題は非常に芸術性が高く解答を眺めるだけでも面白い.


今回は,反復深化法 [*1] で解図を行った結果について述べたいと思う.


解図を行ったのは「夢幻の構想」収録の問題番号1~336の計336問.

ただし,一部の問題は実用時間内に解けないので探索ノード数に上限(100万,1000万,1億)を設けて解図を行っている [*2]


問題の解図率だが,


上限 100万 233問 / 336問 (69.3%)

上限 1000万 303問 / 336問 (90.2%)

上限 1億 326問 / 336問 (97.0%)


となっている.現在はおよそ15万nps程度の探索速度なので古典的な反復深化法であっても1分程度で9割の問題を解図できることが分かる.


1億ノードかけても解図出来なかったのが次の十問で,dep(百万,千万,一億)というのは上限が来たときに探索済みの深さ(ここでは四追いの回数)である.


Title dep(百万) dep(千万) dep(一億)
057月面の足跡 9 17 27
097十年フィーバー 7 11 13
100シンジケート 18 27 34
110スーパーラック 6 9 10
113フリーダム 8 12 19
187星渦II 22 32 44
195星誕 6 7 9
196孤高星 6 9 12
270天地創造 41 46 52
271東高円寺村 11 26 30


反復深化法にとって難問であるのは「十年フィーバー」「スーパーラック[*3]」「星誕」「孤高星」であり,初形における着手可能点の多さがネックになっていると考えられる.もし,「星誕」で「探索ノード数10倍で探索深さ +2」という関係が続いたとすると解図を行うのにおよそ6×10^34秒!という天文学的な時間がかかることになる.


さすがに時間がかかり過ぎなので,「最短性」を捨てて[*4]高速に解図するアルゴリズムを設計し336問全問解くことに成功したので次回はそのアルゴリズムについて述べたい.




[*1] 深さを閾値とするIterative deepening depth-first search.最短解が得られることが保証される.

[*2] 解図を行ったマシンはCPU : Core 2 Duo E6420, Mem 2G, OS : Fedora 7 (with gcc 4.1.2)である.置換表は最大600MBほど確保している.

[*3] 正確には「スーパーラック」の"ラ"の上に「・」が付く.

[*4] 反復深化法でも探索途中の不詰の局面に対し出来るだけ早い段階で不詰であることを判定できれば十分高速化できると考えているが,判定が煩雑であることもあり現時点では実装していない.

quincometさんの読者になろう

ブログの更新情報が受け取れて、アクセスが簡単になります

Ameba人気のブログ

Amebaトピックス