TadaoYamaokaの開発日記

個人開発しているスマホアプリや将棋AIの開発ネタを中心に書いていきます。

詰み探索のループ対策

やねうら王から移植した詰み探索では、以下の後手3手詰めの局面を不詰みと判定してしまう。
position sfen +B+R5n1/5gk2/p1pps1gp1/4ppnsK/6pP1/1PPSP3L/PR1P1PP2/6S2/L2G1G3 w B2N2LP2p 1
f:id:TadaoYamaoka:20180521223401p:plain

原因を調べたところ、探索にループが発生し、深さが4で始めと同じ局面になり、pnとdnが誤ってカウントされてしまうことで、後手の2五銀のループが検出できずに最大深さまでループして探索が打ち切られてその結果が置換表に登録されてしまっていた。
やねうら王の詰み探索では、無限ループの対策としてThreshold Controlling Algorithm (TCA)が実装されているが、置換表がループ後に現れた局面を同一と判定してしまっているため誤動作していた。
対策として、探索の深さが異なる局面は別の局面として置換表に登録することにした。
深さが同じでも別の経路から同じ局面に至る場合があるが、それはまた別の対策が必要になる。

対策を入れた後に、前回と同様の15手詰めの局面で速度を比較した。

対策前 176ms
対策後 380ms

2.15倍遅くなってしまったが、対策前はたまたま正しく動いていたものと思われる。