前回詰み探索に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手詰め行わない方がよさそうだ。
バグ修正
王手生成にバグがあったので修正した。開き王手で直線上に移動する場合に直接王手にならない手も生成していた。