証明駒

詰み探索に証明駒を実装した。

証明駒は以下の論文の説明の通り実装した。
詰将棋を解くアルゴリズムにおける優越関係の効率的な利用について

速度比較

証明駒の実装前後で速度は以下の通りとなった。
実装前の状態は、前回の日記に書いた先端ノードで2手詰めと3手詰めを行い、優越関係の反証への利用を行ったものと比較している（前回の実装に一部バグがあったので修正している）。

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

	探索ノード数	処理時間
実装前	19504	71ms
実装後	20652	73ms

わずかに遅くなってしまった。

速くなる局面もあった。
sfen 7n1/+R5glK/n4s1p1/p4pkl1/2s3n2/P3PP2P/1P+pG5/2P6/9 b R2B2G2S2L8Pn 1

	探索ノード数	処理時間
実装前	476743	1076ms
実装後	215831	517ms

他にもテスト用の37局面で比較したが、平均して改善はわずか(0.8%)であった。

実装の変更

論文では、詰みの局面と後手の局面で、後手が1枚も持っていない種類の先手の駒を証明駒に加えるとなっているが、近接王手の場合は不要なため、近接王手以外の場合のみその処理を行うようにした。

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

	探索ノード数	処理時間
変更前	20652	73ms
変更後	28433	106ms

sfen 7n1/+R5glK/n4s1p1/p4pkl1/2s3n2/P3PP2P/1P+pG5/2P6/9 b R2B2G2S2L8Pn 1

	探索ノード数	処理時間
変更前	215831	517ms
変更後	187811	443ms

遅くなる局面と速くなる局面がある、37局面の合計では、6%ほどの改善であった。

考察

証明駒を実装してもそれほど改善されなかった。
証明駒にはどれくらい効果があるものかデータがあれば調べたい。もっと効果があるものであれば、どこかで実装が誤っているかもしれない。
反証駒も同様に実装できるので、試したい。

github.com