将棋AIの進捗 その48（NPS改善）

ノード再利用の方式見直しを行った後、強くなっているかApery(WCSC28)と1手3秒100局で確認を行った。

結果、勝利は62%で、変更前は69%だったので、強くなっていないことがわかった。

考察

理由としては、以下が考えられる。

• Ponderなしの秒読みではノード再利用が少なく時間がかかっていないこと、秒読みでも探索打ち切りを行っているので、探索ノード数変わらないことから、そもそもノード再利用の遅延の影響がない
• 合流を処理しなくなった分、合流するノードの探索数が減っている。

秒読みでは、強さは測れなかった。
ただし、秒読みでの強さより、大会ルールでの強さを優先したいため、ノード再利用の変更は取り込む予定である。

また、探索打ち切りを行わずに、秒読みぎりぎりまで探索するようにすれば、おそらくノード再利用変更後が強くなるはずである。
次善手の訪問数が残り時間を費やしても最善手を超えない場合打ち切っているが、これは秒読みでは不利になるので行わない方が良い。
別途、探索打ち切りを行うかどうかをオプションで変更できるようにしたい。

NPSが安定しない問題点

合流を処理しなくなった分、NPSは全体的にあがると考えていたが、平均1万5000くらいのところ、4000くらいに極端に落ちるときがある。
同じ局面を何回か探索すると、毎回結果が異なる。

原因を調べたところ、現在、並列処理で同じ末端ノードに達した場合、探索を破棄するようにしているが、その際バーチャルロスも元に戻していたため、同じスレッドで次の探索を行った際に同じノードに達するため、バッチサイズが上がらない（NPSが上がらない）という問題があった。

同一スレッド内でも、一つのバッチ分の探索が完了するまでは、破棄した探索のバーチャルロスを戻さないように変更した。
それにより、一つのバッチ内でも探索ノードが分散されるようになり、NPSが安定するようになった。

1GPU、2スレッドで、floodgateからサンプリングした100局面での平均NPSは、

変更前	28652.4
変更後	31705.8

となり、平均で11%改善した。

8GPU、GPUあたり3スレッドでは、

変更前	158387.1
変更後	225794.9

となり、平均で43%改善した。
並列数が多いほど、改善の効果がでている。

ただし、並列数によるNPS増えても、強さが線形で伸びるわけではない。
NPSを上げようとすればさらに上げることはできるが、ゲーム木のバランス崩れるので、dlshogiではNPSを上げるよりゲーム木のバランスを優先している。

NPS改善後の強さの測定

NPSの改善を行った後、Apery(WCSC28)と1手3秒100局で確認を行った。
結果、勝率72%（信頼区間95%：62.2%-80.42%）となった。
NPS改善により、強くなっていそうである。

floodgateでのテスト

Tesla V100 8GPUでfloodgateでもテストを行った。

レーティング4283のsuisho2_xeonに2回勝っているが、レーティング3751のBlackCat_ts002_4cに1回負けている。
変更前でも読み筋は同じだったので、探索よりもモデルの精度の問題のようだ。
まだ中盤で読み抜けがありそうなので、強化学習を続けることでふさいでいく必要がある。

AobaZero_w1105_n_p800に1回負けているのはバグでTime outしたためだ。
スレッドプーリングに原因がありそうなので修正したが、本当にそれが原因だったかは再現性がなく確認できない。

将棋AIの進捗 その48（PV表示対応）

Qhapaqさんからプルリクをいただいたので、dlshogiをPV表示に対応しました。

プルリクにはなかったのですが、USIオプション「PV_Interval」を追加しました。
「0」にするとPV表示なし、0以上にすると、設定したms間隔でPVを表示します。

masterブランチに反映しましたが、バイナリは配布しないので使用したい方は各自でビルドをお願います。

Qhapaqさん、ありがとうございました！

あと、対局プログラム実行用のDockerfileも共有していただきました。
DeepLearningShogi/Dockerfile at master · TadaoYamaoka/DeepLearningShogi · GitHub

将棋AIの進捗 その47（Linuxのマルチスレッド排他処理）

昨日の記事で、dlshogiのゲーム木の管理をロックレス方式に見直しを行った。

Windowsでは、ノード単位の排他制御をmutexを用いずに、atomic_flag (TAS機能)で実現することで10%NPSが向上したが、Linuxで測定すると800NPSくらいしかでないという悲惨な結果になった。

原因

Linuxのスレッドは、Windowsのスレッドとは異なり、プロセスの一種にすぎない。
そのため、コンテキストスイッチのコストが高い。

atomic_flagでビジー待機を行った場合、スレッドの切り替えが頻発し、そのたびにコンテキストスイッチが起きる。
そのことが、Linuxでの性能低下を招いたと思われる。

ビジー待機の間にstd::this_thread::yield()を追加してみたが、結果は同じであった。

対策

atomic_flagで排他制御を実装した方が高速になると考えていたが、素直にmutexを使うことにした。
ノード作成のたびにmutex作成のコストが発生するため、オーバーヘッドがあると予想していたが、Windowsでの性能低下は0.5%程度と誤差の範囲であった。

Linuxでは、mutexで実装することで、ノード再利用の方式見直し前と比較して、Tesla V100 8GPU、GPUあたり3スレッドで、floodgateからサンプリングしたした局面での平均NPSは、

変更前	66236.7
変更後	159334.9

となり、約2.4倍になった。

mutexで排他制御を行うことでコンテキストスイッチが抑えられて高速になっている。

mutexは、OSに合わせて最適に実装されているので、独自実装するより素直に標準で用意されいてるものを使った方がよかった。

補足

ノード再利用の待ちがなくなったことで、潜在バグが見つかった。
dlshogiでは、詰み探索をモンテカルロ木探索と並列で動かしているが、詰み探索スレッドの開始のタイミングで局面のコピーを行ってから探索していたが、ノード再利用が速くなったことでコピー前に局面が変更されることでまれに不正な結果を返すことが発生するようになった。
スレッド開始前に局面をコピーするように修正を行った。

ノード再利用の変更前にも発生する可能性はあるので、先日公開したバイナリも修正版に差し替えた。
Release 世界コンピュータ将棋オンライン大会バージョン · TadaoYamaoka/DeepLearningShogi · GitHub

※2020/5/8 追記 修正にバグがあったので再度差し替えた

まとめ

排他制御をatomic_flagを使ってビジー待機で実装すると、Linuxでは性能がでない。
素直にmutexを使った方がよいことがわかった。
修正することで、Linuxでもノード再利用の方式見直しにより高速化できた。

NPS向上により強くなっているか、floodgateでテストする予定。

2020/5/8 追記

途中で投了するバグがあるので見直し中
→マルチスレッド関連の考慮漏れがあったので修正した。

将棋AIの進捗 その46（ノード再利用の見直し）

世界コンピュータ将棋オンライン大会でノード再利用の処理に問題があることがわかったので、見直した。

先日の記事で、Leela Chess Zeroのゲーム木の管理方法を調査して、合流を処理しないでC++のヒープ管理を利用してツリー状にノードを管理していることが分かった。
利用しなくなったノードは、最上流のノードをガベージコレクタに追加することで、別スレッドで芋づる式にヒープから削除される。
この方式によって、ノード再利用の待ちをほぼ0にできる。

Leela Chess Zero方式の問題点

Leela Chess Zeroは、子ノードをsibling_でリンクしてリスト構造で管理している。
ノードが展開された時点で子ノードが作成され、sibling_にリンクされる。
そのため、ルートからゲーム木を辿って展開するノードを選択するまでの間、排他制御を行っている。

スレッドが2つまでの場合は、GPU処理とCPU処理が交互に行われるため、競合は起きないが、マルチGPUでスレッドを増やすとロックの範囲が広いため、マルチスレッドの性能がでにくい構造になっている。

改良した方式（ロックレス方式）

dlshogiはマルチGPUに対応しており多スレッドにすることで性能を上げている。
Leela Chess Zero方式をそのまま利用すると性能がでないと予想される。

また、ノードに訪問数や勝率が記録されているため、UCB値を計算する際に、子ノードの情報を使用するためアドレスが離れたメモリにアクセスする必要があり、CPUキャッシュが効きにくい構造になっている。

そのため、子ノードの管理方式を以下のように変更した。

• sibling_を利用しないで、子ノードの情報は配列で管理する。合法手の要素数分だけ一度に確保する。
• 訪問数と勝率はノードではなく、辺の情報（上記の配列）として親ノードで管理する。
• UCBの計算～ノードの展開の間だけ、ノード単位で排他制御する。
• 排他制御には、mutexを用いずに、atomic_flag (TAS機能)を使って実装する。

これで、ロックレスになるためマルチスレッドでも性能低下が抑えられる。
ただし、実際はメモリをヒープから取得しているため、C++のラインタイム内ではヒープ管理で排他制御が行われているので、その影響は受ける。

NNキャッシュについて

Leela Chess Zeroは、ニューラルネットワークの結果は、LRUキャッシュで管理しているが、これは一旦実装しないことにした。
合流がある場合に、同じ局面についてニューラルネットワークの計算を再度行うことになるが、キャッシュヒットした場合に追加で探索を増やすことでゲーム木のバランスが崩れるデメリットもある。
また、LRUキャッシュの管理には排他制御が必要になるので、合流がない場合の性能にも影響があるので、合流自体がそれほど多くないので合流時にニューラルネットワークの再計算をした方がトータルでよい可能性がある。
という点を考慮した。

NPS測定結果

floodgateの棋譜からサンプリングした100局面で5秒探索した場合のNPSを、変更前後で比較した。

	平均NPS
変更前	26054.84
変更後	28813.81

方式変更により、NPSが10.6%向上した。
ただし、すべての局面で上昇しているわけではなく、一部の局面では低下した（低下の割合は小さい）。
これは、合流を処理していないことによる影響と思われる。

ノード再利用の時間

変更前はノード再利用に、数100ms~数秒かかっていたが、新しい方式ではガベージコレクタに対象ノードを追加するだけのため、ノード再利用による遅延が0になった。

まとめ

ゲーム木の管理方法をLeela Chess Zeroを参考に見直すことでNPSが向上し、ノード再利用による遅延が0になった。
Leela Chess Zeroはロックの範囲が広いという問題があったので、ロックレス方式に改良した。

NPSとノード再利用の改善により、強くなっているかは別途測定する予定。

ソースは、feature/garbage_collectionブランチにコミットした。
github.com

Leela Chess Zeroのノード再利用の方法

世界コンピュータ将棋オンライン大会で、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(EdgeListでラッピングされている)で定義されており、コンストラクタで、サイズを指定して初期化され、ヒープ上に動的に確保されるようになっている。
Nodeのchild_は、std::unique_ptrで定義されており、最初の子ノードへのポインタになっている。兄弟ノードへは、child_のsibling_でリンクされている。
兄弟ノードは、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の仕組みに変更して、ノード再利用を含めた探索速度が改善されるか確認してみたい。

dlshogiの環境構築手順

世界コンピュータ将棋オンライン大会でdlshogiライブラリを使用していたGCTは、AWSのWindows Serverで環境構築されていました。

構築手順を共有いただいたので、参考にしてください。

AWSでのGPU環境の構築手順について · Issue #12 · TadaoYamaoka/DeepLearningShogi · GitHub

Linuxでの構築手順は、以前にQhapaqさんにWikiに記事を記載してもらってます。
Home · TadaoYamaoka/DeepLearningShogi Wiki · GitHub
ただし、TensorRT対応前のバージョンの手順になっています。

Linux構築手順(TensorRT対応)

Dockerを使用した場合の、TensorRTバージョンでのLinuxでの構築手順を簡単に記載します。
wcsoc2020バージョンでの構築手順です。最新のソースでは変更されている可能性があります。

CUDA 10.2のDockerコンテナ作成

docker run -v $(pwd):/workspace -it nvidia/cuda:10.2-cudnn7-devel-ubuntu18.04

TensorRTのインストール

NvidiaのサイトからTensorRT 7.0のUbuntu向け.debパッケージをダウンロードして、

dpkg -i nv-tensorrt-repo-ubuntu1804-cuda10.2-trt7.0.0.11-ga-20191216_1-1_amd64.deb
apt-key add /var/nv-tensorrt-repo-ubuntu1804-cuda10.2-trt7.0.0.11-ga-20191216_1-1_amd64.deb/7fa2af80.pub
apt-get update
apt-get install tensorrt

パッケージインストール

apt install zlib1g-dev
apt install git

GitHubからソースをclone

git clone -b wcsoc2020 https://github.com/TadaoYamaoka/DeepLearningShogi.git

ビルド

cd DeepLearningShogi/usi
make

これで、DeepLearningShogi/usi/binに、実行ファイルusiが出来上がります。

USIエンジンのビルドはここまです。以降は、学習を行う場合に必要な環境構築手順です。

Anacondaインストール

Anacondaのサイトの以前のアーカイブからAnaconda3-2019.10-Linux-x86_64.shをダウンロードして

bash Anaconda3-2019.10-Linux-x86_64.sh

インストール時にconda initを実行する聞かれるので実行する。以降、condaのbase環境で作業する。

boostインストール

conda install boost=1.67.0

環境変数追加

~/.bashrcに以下の行を追加

export LD_LIBRARY_PATH=$LD_LIBRARY_PATH:$CONDA_PREFIX/lib

自己対局コマンドビルド

cd DeepLearningShogi/usi/make_hcpe_by_self_play
make

これで、DeepLearningShogi/make_hcpe_by_self_play/binに、実行ファイルmake_hcpe_by_self_playが出来上がります。

以下、ニューラルネットワークの学習環境の構築手順です。
boostインストールは上記と共通です。

PyTorch 1.3インストール

conda install pytorch==1.3.1 torchvision==0.4.2 cudatoolkit=10.1 -c pytorch

dlshogiのPythonモジュールインストール

cd DeepLearningShogi
pip install -e .

cppshogiビルド

cd cppshogi
make

これで、dlshogi/train_rl_policy_with_value_using_hcpe_bootstrap.pyを使用して、自己対局で生成した学習局面でニューラルネットワークの学習が行えます。

dlshogi（wcsoc2020）のWindows版ビルド済みファイル公開

dlshogiの世界コンピュータ将棋オンライン大会バージョンのWindows版ビルド済みファイルを公開します。

Release 世界コンピュータ将棋オンライン大会バージョン · TadaoYamaoka/DeepLearningShogi · GitHub

実行には、CUDA 10.2に対応したGPUが必要です。
インストール方法は、Releaseページに記載しています。

追加学習が行えるように、学習用モデルファイルも同梱しています。

※2020/5/8 追記
詰み探索がillegal moveになる場合があるバグがあったため、修正を行ったファイルに差し替えた。