前回の日記で書いた通り、df-pnの実装を行いました。
実装の参考にしたのは、以下の論文です。
上記の論文にはほぼ同じ疑似コードが掲載されていますが、ANDノードとORノードで処理を共通化しており、理解しづらかったため、ANDノードとORノードを別々の処理として記述した。
速度比較
次の15手詰めの局面で、df-pnと優先なし探索で速度を比較した。
position sfen 1n1g3+Pl/k1p1s4/1ng5p/pSP1p1pp1/1n3p3/P1K3P1P/1P7/9/L1G5L b 2R2BG2SL5Pn 161
df-pn | 1,688 msec |
優先なし | 52,794 msec |
31倍高速になった。
課題
ハッシュを利用しているが、上記の15手詰めで1,158,018ノードを使用した。
手数が増えるとノードが指数的に増えるので、ハッシュクリアの仕組みがないと長手詰めには対応できない。
また、詰みが見つからないないときに途中で打ち切る仕組みが必要。
コード
実装したコードはこちらです。
DeepLearningShogi/DfPn.cpp at fd35ae081b1e7754dd233f375d082801639a1d12 · TadaoYamaoka/DeepLearningShogi · GitHub
2020/8/4 追記
最新のソースはこちら。
https://github.com/TadaoYamaoka/DeepLearningShogi/blob/master/usi/dfpn.cpp
関連記事
詰み探索で優越関係の利用 - TadaoYamaokaの開発日記
詰み探索のループ対策 - TadaoYamaokaの開発日記
3手詰めルーチン - TadaoYamaokaの開発日記
2手詰めルーチン - TadaoYamaokaの開発日記
優越関係の反証への利用 - TadaoYamaokaの開発日記
証明駒 - TadaoYamaokaの開発日記
反証駒 - TadaoYamaokaの開発日記
優越関係を利用した証明数と反証数の初期化 - TadaoYamaokaの開発日記
王手生成の最大数 - TadaoYamaokaの開発日記