TadaoYamaokaの日記

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

将棋AIの進捗 その30(NNキャッシュ)

先日、Leela Chess Zeroのソースを流用して、LRUキャッシュを実装したが、これを自己対局プログラムに組み込んだ。

はじめ、LRUキャッシュを1つにしてすべての探索スレッドで共有するようにしたが、ゲーム木の展開済みノードのNN計算結果が、他のスレッドの探索によって削除されることがあった。
キャッシュサイズを十分に大きくすればよいが、メモリ効率が悪いため、探索スレッドごとにNNキャッシュを保持するようにした。
それにより、必要なキャッシュサイズの見積もりが可能になる。

dlshogiの自己対局は、探索とNN計算の直列化を行っているため、必要なキャッシュサイズは、シミュレーション回数×バッチサイズとなる。

Leela Chess Zeroの実装では、キャッシュヒットした場合も順番を先頭にしないようになっていたため、上記の構成にしてもキャッシュが削除されることがあった。
そのため、キャッシュヒットした場合に、キャッシュ内の順番を先頭にもってきてゲーム木の展開済みノードのNN計算結果が削除されないようにした。
(Leela Chess Zeroではこの制御を行っておらず、どのように対処しているか気になっているがソースを読み切れていない。)

また、スレッドごとにNNキャッシュを保持するようになるため、排他制御のコードは削除した。

NNキャッシュの効果

NNキャッシュの実装前後で、局面生成速度は、以下の通りとなった。

NNキャッシュなし 41.50 nodes/sec
NNキャッシュあり 64.92 nodes/sec

NNキャッシュにより局面生成速度が、1.56倍になった。

余談

Leela Chess Zeroのソースを調べていたら、SE Netや、価値のブートストラップが実装されていて、dlshogiで行っているようなことは次々と試されているようだ。
issueで議論も活発に行われているので参考になる。
αβ探索の将棋ソフトは、Stockfishを参考に開発が行われているが、MCTSではlc0を参考にする流れになってきそうだ。

2019/6/25 追記

バックアップする際に親ノードをキーにしてキャッシュを調べていたバグがあり、修正して再測定したところ、以下の通りとなった。

NNキャッシュあり 47.46 nodes/sec

キャッシュなしの1.14倍程度であまり早くなっていない。
どれくらいキャッシュにヒットしているか調べたところ、49.2%ヒットしていた。
キャッシュヒット率から2倍くらいの生成速度になってもよいはずなので、遅すぎる。

ボトルネックを調べるためにVisual Studioのプロファイラで調査した。
f:id:TadaoYamaoka:20190625090030p:plain
2スレッドで1GPUを利用しているため、CPUによる探索の処理(Playout)とGPUによる推論処理(EvalNode)がバランスしている場合に、GPUの利用効率が高くなる。
プロファイラで調べた結果、CPU処理の方に時間がかかっており、GPUに待ちが発生していた。

次に、CPUによる探索処理を調べると以下のようになっていた。
f:id:TadaoYamaoka:20190625085943p:plain
末端ノードでの詰み探索処理(mateMoveInOddPly)にかなりの時間が費やされていた。

NNキャッシュにヒットした場合には詰み探索も実施済みのため、詰み探索を行う必要はないが行っていた。
これがキャッシュを導入しても速くならない原因だったようだ。

NNキャッシュヒットした場合に詰み探索をしないように修正

NNキャッシュにヒットした場合は、詰み探索を行わないように修正して再測定した結果、以下の通りとなった。

NNキャッシュあり 72.06 nodes/sec

キャッシュなしの1.74倍になっており、キャッシュの効果が表れている。
プロファイラの結果は以下の通りになった。
f:id:TadaoYamaoka:20190625091147p:plain
CPUの探索処理とGPUの推論処理がほぼバランスしており、GPUが効率的に使用されている。