TadaoYamaokaの日記

山岡忠夫Homeで公開しているプログラムの開発ネタを中心に書いていきます。

2手詰めルーチン

前回詰み探索に3手詰みルーチンを入れると遅くなったと書いたが、先端ノード以外でも3手詰めルーチンを呼び出していたことが原因だった。

3手詰めを行うのは先端ノードのみとして、15手詰めの局面で速度を比較しなおした。
position sfen 1n1g3+Pl/k1p1s4/1ng5p/pSP1p1pp1/1n3p3/P1K3P1P/1P7/9/L1G5L b 2R2BG2SL5Pn 161

探索ノード数 処理時間
1手詰めルーチン 100591 330ms
3手詰めルーチン 104886 357ms

前回より改善されたが、それでも1手詰めルーチンより遅くなっている。
探索ノード数が増えているのは探索順が変わったためと思われる。

次に、3手詰めチェックを行う際に、1手詰めのチェックを行った結果をハッシュに残すように修正した。

探索ノード数 処理時間
1手詰めルーチン 100591 330ms
3手詰めルーチン 160249 523ms

これも探索順が変わったことで探索ノードが増えてしまった。
3手詰めは近接王手しか生成していないので、ゲーム木のバランスが崩れてしまうのかもしれない。

2手詰めルーチン

以下の論文で、ANDノードで2手読みをすると効果があるという記述があったので、ANDノードでの2手詰めを試してみた。
新規節点で固定深さの探索を併用するdf-pn アルゴリズム
論文では、証明数の先読みを行っているが、証明数の先読みは行わず、1手詰めの結果をハッシュに残すのみとした。

探索ノード数 処理時間
1手詰めのみ 100591 330ms
2手詰めルーチン 24146 92ms

探索ノード数は、24%になり、処理時間は27.8%になった。
先端ノードでの2手詰めチェックは効果があることがわかった。

3手詰めと組み合わせ

2手詰めに加えて、3手詰めも行うようにした。3手詰めでは1手詰めの結果をハッシュに残さない。

探索ノード数 処理時間
1手詰めのみ 100591 330ms
2手詰め+3手詰め 19497 71ms

2手詰めと3手詰めの両方を行うことで、さらに処理速度が改善された。

不詰みの局面

不詰みの局面での速度を比較した。
sfen position l2+S1p2K/1B4G2/p4+N1p1/3+B3sk/5P1s1/P1G3p1p/2P1Pr1+n1/9/LNS5L b R2GL8Pnp 1

探索ノード数 処理時間
1手詰めのみ 395634 645ms
2手詰め 391476 669ms
2手詰め+3手詰め 381496 724ms

不詰めの局面では1手詰めが一番早いという結果になった。
探索ノード数は、減っているため、2手詰め、3手詰めの処理に時間がかかることによって処理時間が伸びている。
実戦のモンテカルロ木探索の末端で使用する場合は、不詰みの方が多いため、2手詰め、3手詰め行わない方がよさそうだ。

github.com

バグ修正

王手生成にバグがあったので修正した。開き王手で直線上に移動する場合に直接王手にならない手も生成していた。