世界コンピュータ将棋オンライン大会で、dlshogiのノード再利用の方法に問題があることが明らかになったので、見直すことにする。
現在のハッシュ管理
dlshogiのハッシュ管理は、Ray+Rnのゾブリストハッシュの実装を参考にしていた。
Ray+Rnのノード再利用の実装は、単にハッシュをクリアしないというもので、これだとdlshogiではすぐにハッシュフルになるため、実際の対局では使用できない。
dlshogiの実装
そのため、dlshogiではルートノードから辿れるノードのみを残して、他のハッシュエントリを削除する処理を実装している。
ルートノードからノードを辿る処理が、300万ノードとかになると、数秒を要してしまい思考時間のうち探索に費やせる時間が相当に減っている。
ただ、すべてをクリアして再度300万ノードを探索しようとするとそれ以上の時間がかかるため、世界コンピュータ将棋オンライン大会では再利用の処理を残したままにした。
問題点
しかし、これが最悪の場合、Ponder開始時は再利用するノードが多く、相手がすぐに手を指して指された手では再利用するノードが少なかった場合、Ponderで再利用処理に時間がかかりPonder終了に遅延が発生して、実際の思考局面では再利用するノードが少ないにも関わらず待ち時間のため思考時間を削られるという状況が発生していた。
遅延の原因
ルートからノードを辿る処理は、複雑な処理はなく単に子ノードの配列のインデックスを再帰的にたどって、そのインデックスに使用中をマークするだけだ。
この単純な処理に時間がかかるのは、ハッシュのメモリサイズが数十GBあり、その広い領域のメモリにランダムに近いアクセスをするために、CPUのキャッシュがほとんど効かないのと、OSによるページ管理処理が頻発することに関連していると思われる。
根本的に今の構成の見直しが必要である。
そのための準備として、Leela Chess Zeroのゲーム木の管理を調査することにする。
Leela Chess Zeroでは、ガベージコレクタの専用スレッドがあり、探索の打ち切りも別スレッドで管理を行っていることは把握しているが、詳細までは調べていなかったので、この際に詳細に調べることにする。
Leela Chess Zeroのゲーム木の管理
Leela Chess Zeroのゲーム木の管理について、node.hのコメントに以下のように説明されている。
- エッジ(edge)とエッジ(edge)が指すノード(node)は別々に保存される。
- ぶら下がっているエッジがある可能性がある（まだどのNodeオブジェクトも指していない）
- 格納されるエッジは、ヒープ上の単純な配列である。
例）
これを次のように表現する。
ソースを確認すると、
Nodeのedges_は、std::unique_ptr
Nodeのchild_は、std::unique_ptr
兄弟ノードは、MCTSの探索によって展開された時点でsibling_のリンクに追加される。
子ノードへのアクセスが、sibling_を辿る必要があり、効率が悪いように見えるが、Edge_Iteratorという仕組みでEdgeとNodeのペアが別に管理されている。
ゲーム木管理の主要な部分は、以上である。
ガベージコレクション
Leela Chess Zeroのゲーム木管理の方法はノード再利用の効率化と関連している。
ガベージコレクションの対象は、goコマンドの処理の開始時にガベージコレクタに追加される。
positionの文字列から、前のpositionコマンド実行と共通する部分を直前に探索したノードとみなして、その子ノードのうち現在のpositionに含まれる子ノードを除いた兄弟ノードが削除対象になる。
goコマンドを処理するメインスレッドでは、ガベージコレクタへの追加のみで実際の削除処理は、別スレッドで行われる。
削除の仕組みは単に、NodeをC++でdeleteするだけである。
ガベージ対象のNodeから連なる子ノードは、上記のゲーム木の管理で説明した通り、すべてunique_ptrで管理されているため、C++のランタイムにより連鎖的に削除される。
このように、C++のメモリ管理を利用して芋づる式に削除する方法がとられている。
メリット・デメリット
Leela Chess Zeroの方式は、C++のメモリ管理の仕組みを利用しているため実装がシンプルである。
ガベージコレクションを別スレッドで行うことで、ノード再利用のための探索開始までの遅延がほぼ0である。
デメリットとしては、ノードの合流が処理できない。
将棋では、同じノードに合流することがある程度あるので、そのたびに重いニューラルネットワークの推論を行うと非効率である。
Leela Chess Zeroでは、ニューラルネットワーク(NN)の推論の結果は、別のLRUキャッシュでキャッシュする仕組みを持っている。
合流を処理しない場合は、NNのキャッシュと組み合わせて使用する必要がある。
また、ヒープを動的に確保、削除しているため、ノードの作成、削除に若干のコストがかかる。
マルチスレッドの場合、ヒープ管理で競合が起きるため、マルチスレッド性能のボトルネックとなりやすいと思われる。
dlshogiではそれを避けるため、はじめに固定サイズメモリを確保していた。
ただし、オープンアドレス法によるハッシュ管理のためにツリーをロックしているため、処理遅延は同じかもしれない。
まとめ
現在のdlshogiのノード再利用の実装には処理に時間がかかりすぎるという問題があり、根本的にハッシュ管理の仕組みを見直す必要がある。
その準備として、Leela Chess Zeroの仕組みを調べた。
Leela Chess Zeroでは、遅延なくノードの再利用ができるようになっていることが分かった。
従来型のコンピュータ将棋の置換表の仕組みは、MCTSと相性が良くなさそうだ。
dlshogiのハッシュ管理をLeela Chess Zeroの仕組みに変更して、ノード再利用を含めた探索速度が改善されるか確認してみたい。
