TadaoYamaokaの日記

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

3手詰めルーチン

詰み探索に近接王手からの3手詰めルーチンを実装した。
近接王手の手を生成することで、3手で詰む場合無駄合いを省くことができる。

近接王手の生成は、敵玉の8近傍に移動または持駒から打つ手と、桂馬で王手する手を生成する。
王手の指し手生成を変更することで作成した。
3手詰めルーチン · TadaoYamaoka/ElmoTeacherDecoder@4b331e0 · GitHub

3手詰めのルーチンはやねうら王のmate_n_ply.cppを参考に実装した。
3手詰めルーチン · TadaoYamaoka/ElmoTeacherDecoder@4b331e0 · GitHub

生成した近接王手に、自分の駒からの利きがない場合と、敵の王以外の駒からの利きがある場合、移動により自玉が詰む場合は除外する。
残った手について、1手指して、敵玉の王手回避後、1手詰めルーチンですべての手が詰むか調べる。
2手指して、戻す処理が入るため、それなりに計算コストが高い。

速度比較

詰み探索に1手詰めルーチンを使った場合と3手詰めルーチンを使った場合で、前回と同様の15手詰めの局面で速度を比較した。
position sfen 1n1g3+Pl/k1p1s4/1ng5p/pSP1p1pp1/1n3p3/P1K3P1P/1P7/9/L1G5L b 2R2BG2SL5Pn 161

1手詰めルーチン 330ms
3手詰めルーチン 366ms

3手詰めルーチンを使うと10%程遅くなってしまった。

25手詰めの局面では、
position sfen lnl5l/2b6/ppk6/3p1p2p/Ps2p1bP1/1NP3g1K/LP6P/9/1N6+p b R3G2SN2Prs4p 1

1手詰めルーチン 4677ms
3手詰めルーチン 6135ms

34%程遅くなった。

まとめ

3手詰めルーチンは指して戻す処理が必要なため計算コストが高い。3手で詰む場合は無駄合いを省くことができるが、3手で詰まない局面でも呼び出すと探索速度が落ちてしまう。
1手詰めルーチンを使って、無駄合いは優越関係を使って省略した方が良い。


近接王手の生成を実装しているときに、王手生成で歩を必ず成るようにしていた問題に気づいた。
打ち歩詰めが関係するので、歩は成らない手も生成する必要があるので修正しておいた。

詰み探索のループ対策

やねうら王から移植した詰み探索では、以下の後手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倍遅くなってしまったが、対策前はたまたま正しく動いていたものと思われる。

詰み探索で優越関係の利用

やねうら王から移植した詰み探索の速度を上げるために優越関係の実装を行った。

局面Aが局面Bを優越するとは、AとBの盤上の駒の配置が同一で持駒のみが異なっており、Bの持駒がAの持駒の部分集合になっている場合を示す。
参考:
詰将棋を解くアルゴリズムにおける優越関係の効率的な利用について

言い換えると、盤面が同じで持駒が多い局面のことを指す。
詰み探索では、ある局面と盤面が同じで持駒がより少ない局面で詰みが証明できるならば、その局面も詰みであることを利用すると、探索ノード数を減らすことができる。

置換表

優越関係を利用するには、盤面が同じ局面を効率的に置換表から検索できる必要があるため、通常の探索では置換表のキーは、盤面と持駒を合わせたハッシュ値になるが、優越関係を利用する場合、置換表のキーは、盤面のみのハッシュ値とする。
局面を区別するため、持駒も置換表のエントリに保持しておく。

持駒の表現

持駒は、各駒の枚数に必要なビット数を割り当て、32bitに詰め込む。
AperyではHand型で実装されているので、そのまま利用した。
Aperyには優越関係を調べるためのisEqualOrSuperiorメソッドも用意されている。

置換表のエントリ数

ハッシュキーを盤面のみとするため、持駒のみが異なる複数局面のハッシューが同一となる。
そのため、同一のハッシュキーに対して十分なエントリ数を用意しておく必要がある。
256エントリあれば、ほとんどの場合でエントリが不足することはない。
エントリが不足したらどれかのエントリを上書きすることになる。
(情報量が少ないエントリを上書きするのがよいが実装していない。)

優越関係の利用

詰み探索中に置換表を検索する際に、優越関係を満たす局面に詰み(証明数が0)があれば、そのエントリを返すようにする。
ここで、ORノードとANDノードで優越関係が逆になるので注意する。
ORノードでは、持駒の少ない局面を調べるが、ANDノードでは、相手側の持駒になるので相手の持駒が多くても詰むか調べる必要がある。

速度比較

以下の15手詰めの局面で速度を比較した。
position sfen 1n1g3+Pl/k1p1s4/1ng5p/pSP1p1pp1/1n3p3/P1K3P1P/1P7/9/L1G5L b 2R2BG2SL5Pn 161

優越関係利用なし 1625ms
優越関係利用あり 176ms

9.23倍高速になった。

まとめ

優越関係の実装は、ハッシュキーの仕組みを変更するだけで実装することができ実装は難しくないが、効果が大きい。
優越関係を利用することで無駄合いの判定などの特別な処理を行うことなく、無駄合いの局面の探索を省略できる。

なお、優越関係を満たす局面の不詰みも利用することが可能だが、かえって遅くなる場合があったので利用しないことにした。

優越関係の利用は、詰みの局面のみではなく、優越関係を満たす局面のpnの値も利用できる。
そちらについても実装する予定である。

優越関係を実装したソースコードはこちら。
github.com

やねうら王の詰み探索を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はあきらめていたが、探索と評価の直列化をしたことでスレッドごとに置換表を割り当てても問題なさそうである。
スレッドごとに置換表を分ける場合、サイズはあまり大きくできないので、探索ノード数を制限することになりそうである。

やねうら王教師局面からAperyの初期局面集を作成

やねうらおさんが公開してくれていたdepth10で作った110億局面の教師から、Apery用の初期局面集を作成するツールを作成しました。

教師局面に記録されている評価値の絶対値を閾値にして、Aperyの初期局面集形式(hcp)を出力します。

コマンド例)

psv_to_hcp.exe shuffled_sfen1.bin shuffled_sfen1.hcp 500

先日記事にしたAperyでやねうら王のPackedSfenValueを読み込むコードの応用です。

需要があるかわかりませんが、初期局面集のバリエーションを増やしたい場合にご利用ください。
github.com

改造したPositionクラスの本体はこちら
ElmoTeacherDecoder/hcp_decoder at master · TadaoYamaoka/ElmoTeacherDecoder · GitHub

将棋AIの進捗 その23(探索と評価の直列化 その2)

前回、対局プログラムを探索と評価の直列化することによって高速化を行ったが、自己対局プログラムについても探索と評価の直列化を行った。

以前は、探索を複数スレッドで行って、ニューラルネットワークを計算をキューにためて専用のスレッドでバッチ処理を行っていたが、スレッドの同期がボトルネックになっていた。
2枚のGPUのPCで、GPUごとに180スレッドと140スレッドという大量のスレッドで探索を行い、ニューラルネットワークの計算完了を探索スレッドでビジーウェイトで待機していた。
ニューラルネットワークの計算が完了すると同時に、大量スレッドが一斉に動き始めるため、CPUを奪い合う状況が発生しており、性能低下を起こしていた。
Windowsではそれなりの速度で動いていたが、LinuxではWindowsの3割程度の性能になっていた。

このようなマルチスレッドの問題は、コンピュータサイエンスではThundering herd problem(大群の問題)と呼ばれている。「Optimized C++」にも記述されていた。

この問題を避けるため、一つのスレッドで探索をバッチサイズ分繰り返した後、評価(ニューラルネットワークの計算)を同一のスレッドでバッチ処理するように変更を行った。ニューラルネットワークの計算中にも探索を行えるように、2つのスレッドで探索を行うようにした。

自己対局プログラムでは、バッチサイズ分の対局を並行で進行し、各対局のシミュレーションを1回実行し、各対局の評価要求を1つずつキューにためてバッチで処理するようにした。

局面生成速度比較

変更前後で局面の生成速度は、以下のようになった。
GPUの2枚(Titan V+1080Ti)のPCで測定した。スレッド数、バッチサイズは生成速度が最大になるように調整している。

スレッド数 生成速度(node/sec)
変更前 180+140 11.26+8.53=19.79
変更後 2+2(バッチサイズ:192+176) 14.17+11.35=25.52

生成速度が変更前から1.29倍になった。

Linuxでの生成速度

変更前はLinuxで性能がでなかったが、変更後の速度を測定した。

スレッド数 生成速度(node/sec)
変更後 2+2(バッチサイズ:208+176) 12.10+9.55=21.65

Windowsの85%程だが変更前より高速になった。


自己対局による教師局面の生成速度が上がったことで、変更前は500万局面の生成と学習に3日かかっていたが、2日半程度に短縮できそうである。
Linuxでの生成速度も上がったので、価格が安いAWS(もしくはGCP)のLinuxGPUインスタンスの利用も検討したい。

使用ライブラリをAperyに変更

dlshogiは今までAperyから派生したelmo_for_learnのソースを使用していましたが、最新のAperyで修正されたバグの修正を取り込むため使用ライブラリをAperyに変更しました。
入玉宣言に修正が入っていたので、そこだけ取り込むつもりでしたが、ついでにすべてのソースを最新にしました。

また、今までLEARNを有効にしてビルドしていたので、枝狩りが少ない状態になっており長手数の詰みが見つけられない局面があったため、対局用ではLEARNをオフにしてビルドすることにしました。