TadaoYamaokaの日記

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

反証駒

前回までに実装した詰み探索では、ループの対策を行っておらず、最大深さまでループする局面があった。
ほとんどの局面では閾値がうまく働いて無限ループにならないが、以下の19手詰めの局面で最大深さまでループが発生していたため、優越関係を反証に利用すると、最大深さに達した局面が不詰み扱いになるため、誤って不詰みと判定されていた。
sfen ln6K/1ksPg1sG1/5s2p/ppp3p2/9/P1P3P2/4+p3P/1+r7/LN3L2L w RBSb2g2n7p 1

完全なループの対策をする方法もあるようだが、とりあえず簡易な実装として千日手チェックを行い千日手となった局面にはハッシュに印をつけて、優越関係では利用しないようにした(親のノードにも影響するので完全な対策にはなっていない)。
判定が誤ることなくても、ある程度ループしている局面があったようで、千日手チェックを入れるとテスト用の37局面の合計で3%程速くなった。

反証駒

前回証明駒を実装したが、反証駒も実装した。
反証駒は、証明駒とは逆に不詰みを証明するための後手の最小の持ち駒のことを示す。

ハッシュは、すべて先手の駒で保持しているため、後手の駒を先手の駒に読み替えて実装する必要があった。

不詰みの局面では、後手側では、反証駒を0にして、先手が1枚も持っていない種類の駒を反証駒に加える。
これを先手の持ち駒で表現すると、先手が持っている種類の持ち駒に後手の持ち駒を加える(後手の持ち駒を0にすると同義)。
先手が1枚も持っていない種類の駒を反証駒に加える部分は、もとから先手の持ち駒は0なので処理は不要となる。

ANDノードでは、後手が駒を打った場合は反証駒を減らし、後手が駒を取った場合は反証駒に加える。

ORノードでは、子局面の反証駒の積集合とする。また、先手が一枚も持っていない種類の駒の反証駒を0にする。

速度比較

反証駒を実装する前後で速度を比較した。

15手詰みの局面

sfen 1n1g3+Pl/k1p1s4/1ng5p/pSP1p1pp1/1n3p3/P1K3P1P/1P7/9/L1G5L b 2R2BG2SL5Pn 161

探索ノード数 処理時間
証明駒のみ 28372 108ms
証明駒+反証駒 28372 110ms

探索ノード数は変わっておらず、処理時間も誤差の範囲である。

不詰み局面

sfen +B2B1n2K/7+R1/p2p1p1ps/3g2+r1k/1p3n3/4n1P+s1/PP7/1S6p/L7L b 3GS7Pn2l2p 1

探索ノード数 処理時間
証明駒のみ 952464 2158ms
証明駒+反証駒 910453 2062ms

探索ノード数が減っており、4.4%程処理時間が速くなっている。

テスト用の37局面の合計では、4.9%程速くなった。

考察

反証駒の実装前後で、処理速度の改善は5%以下であった。
証明駒の効果と同程度である。両方組み合わせると局面に依存するがテストした局面の合計では10%程改善した。
探索ノード数が多い局面ほど、効果があるようである。

証明駒も反証駒も参考にできるオープンソースがないため、実装があっているかあまり自信がない。
github.com