TadaoYamaokaの日記

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

やねうら王の詰み探索をAperyに移植

Aperyの初期局面集には、詰みの局面を数%含んでいるので、これを除きたい。
詰みの局面で自己対局を行い教師局面を生成すると終盤局面に偏りが生じると考えるためである。
なお、初期局面集に詰みの局面を含めることがマイナスか判断するには実験が必要だが、確かめてはいない。

詰みの局面を除くために初期局面集の各局面に対して詰み探索が必要になる。
以前にdf-pnを実装したことがあるので、それを使って試そうと思ったが、証明ノードが多い不詰みの局面でうまく動かなかったためバグ取りをするより、やねうら王の詰み探索を移植することにした。

やねうら王の詰み探索をAperyに移植

やねうら王のmate-engineソースコードをほぼそのまま流用して、Aperyに移植を行った。
ElmoTeacherDecoder/dfpn.cpp at master · TadaoYamaoka/ElmoTeacherDecoder · GitHub

基本的にPositionクラスのメソッド名を変えるだけで対応できたが、やねうら王にあってAperyにない機能については、それらも移植した。
王手の生成については、以前に移植したことがあるのでそれを利用した。
また、Positionから1手指した後のハッシュキーを取得するメソッドがなかったので、AperyのPositionクラスに追加した。
ElmoTeacherDecoder/position.cpp at master · TadaoYamaoka/ElmoTeacherDecoder · GitHub

移植した詰み探索を使って、以前に試した15手詰めの局面の詰み探索を行い探索速度を調査した。
position sfen 1n1g3+Pl/k1p1s4/1ng5p/pSP1p1pp1/1n3p3/P1K3P1P/1P7/9/L1G5L b 2R2BG2SL5Pn 161

結果、1625msと以前に自作したdf-pnと同じくらいの速度だった。
それほど早くないが、バグなく安定して使えるのでこれを使用することにする。

探索速度

20手以上の長手数の詰みや、証明ノード数が多い不詰みの局面だと非常に探索に時間がかかるので、探索の深さと探索局面数に制限を設けて時間がかかる局面は不詰みとして扱うことにした。
探索の深さ=20
探索局面上限=1048576

これで、シングルプロセスで平均33局面/秒の速度で探索できるようになった。

分割処理

詰み探索の置換表はStockfish風になっているが参照、更新する際に特別な考慮をしないとlock lessでは使用できなそうである。
Stockfishがグローバルな置換表をマルチスレッドで使用できる仕組みがどうなっているかはあまり理解できていない。
詰み探索の置換表はマルチスレッドでは使えなそうである。
そこで、初期局面集を分割してマルチプロセスで処理するようにした。

10コアのPCで初期局面集を10分割して、各プロセスで約500万局面ずつ探索して、1.75日くらいで完了する見込みである。
副産物で大量の詰み局面集ができあがるので、何かの用途があるかもしれない。

なお、自玉が王手の場合は、ANDノードから探索を行い詰みの場合はそれも除くようにした。

モンテカルロ木探索での利用

dlshogiではモンテカルロ木探索の末端ノードで7手の詰み探索を行っているが、7手であればAND/OR木を全て探索しても早いので、df-pnは使っていない。
df-pnを使えばもう少し探索手数を増やせるので、置き換えることも検討したい。
置換表がマルチスレッドに対応していないので、スレッドごとに置換表を分けることになると思う(もしくはロックを実装する)。
以前は探索スレッド数が多いこともあったdf-pnはあきらめていたが、探索と評価の直列化をしたことでスレッドごとに置換表を割り当てても問題なさそうである。
スレッドごとに置換表を分ける場合、サイズはあまり大きくできないので、探索ノード数を制限することになりそうである。