TadaoYamaokaの日記

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

3手詰めルーチン

詰み探索に近接王手からの3手詰めルーチンを実装した。
近接王手の手を生成することで、3手で詰む場合無駄合いを省くことができる。

近接王手の生成は、敵玉の8近傍に移動または持駒から打つ手と、桂馬で王手する手を生成する。
王手の指し手生成を変更することで作成した。
3手詰めルーチン · TadaoYamaoka/ElmoTeacherDecoder@4b331e0 · GitHub

3手詰めのルーチンはやねうら王のmate_n_ply.cppを参考に実装した。
3手詰めルーチン · TadaoYamaoka/ElmoTeacherDecoder@4b331e0 · GitHub

生成した近接王手に、自分の駒からの利きがない場合と、敵の王以外の駒からの利きがある場合、移動により自玉が詰む場合は除外する。
残った手について、1手指して、敵玉の王手回避後、1手詰めルーチンですべての手が詰むか調べる。
2手指して、戻す処理が入るため、それなりに計算コストが高い。

速度比較

詰み探索に1手詰めルーチンを使った場合と3手詰めルーチンを使った場合で、前回と同様の15手詰めの局面で速度を比較した。
position sfen 1n1g3+Pl/k1p1s4/1ng5p/pSP1p1pp1/1n3p3/P1K3P1P/1P7/9/L1G5L b 2R2BG2SL5Pn 161

1手詰めルーチン 330ms
3手詰めルーチン 366ms

3手詰めルーチンを使うと10%程遅くなってしまった。

25手詰めの局面では、
position sfen lnl5l/2b6/ppk6/3p1p2p/Ps2p1bP1/1NP3g1K/LP6P/9/1N6+p b R3G2SN2Prs4p 1

1手詰めルーチン 4677ms
3手詰めルーチン 6135ms

34%程遅くなった。

まとめ

3手詰めルーチンは指して戻す処理が必要なため計算コストが高い。3手で詰む場合は無駄合いを省くことができるが、3手で詰まない局面でも呼び出すと探索速度が落ちてしまう。
1手詰めルーチンを使って、無駄合いは優越関係を使って省略した方が良い。


近接王手の生成を実装しているときに、王手生成で歩を必ず成るようにしていた問題に気づいた。
打ち歩詰めが関係するので、歩は成らない手も生成する必要があるので修正しておいた。