TadaoYamaokaの日記

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

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

前回、ねね将棋が世界コンピュータ将棋選手権で高い探索速度を出していたので、バリューの計算中に末端ノードから新しく探索を行う方法で簡易な実装をして実験を行った。
しかし、末端ノードから新しく探索を始めると、新しく始めた探索のバリューの計算されるまで、元の探索のバックアップが行われないため、正しくゲーム木が成長しない状態となっていた。

そこで、ねね将棋と同じように経路を保存して、バッチで評価した後にバックアップを行う実装に変更して検証をやり直した。
ねね将棋では、シングルスレッドで探索を行い、GPUの計算をマルチプロセスで行う実装になっているが、GPUの計算中も探索を行いたいため、以下のような方式にした。

f:id:TadaoYamaoka:20180509104213p:plain
探索とGPU計算は同一のスレッドで直列に実行し、GPU計算の完了のためにスレッドの同期を不要にした。探索はバッチサイズ分実行し、GPU計算はバッチ処理を行う。
この探索スレッドを2つ並列で実行し、GPUの計算は競合するため排他制御を行う。
そうすることで、一方のスレッドでGPUの計算中にも探索を行うことができる。

GPUが複数枚ある場合は、GPUごとに2つの探索スレッドを割り当てる。

探索速度比較

GPU2枚のPCで探索速度の比較を行った。

スレッド数 探索速度(シミュレーション/秒)
変更前 168×2 12457
変更後 2×2(バッチサイズ192) 14158

※初期局面で10万回シミュレーション

探索速度が向上することが確かめられた。

探索の深さ

前回の記事で、探索速度を上げるとモンテカルロ木探索の特性としてゲーム木が幅方向に広がるため、強さに結びつかないという考察を行った。

幅方向に広がるのを抑えるため、バッチサイズ分探索を繰り返す際、同じ経路を探索した場合は、その探索は破棄して、バッチサイズを減らす実装にした。
そうすることで、バリューの計算を待つ処理を疑似的に再現できる。

今回の実装方法で、探索の深さを確認した。

探索の深さ
変更前 36
変更後 35

今回の実装では、探索の深さはバリューを待つ実装と同等になった。

強さの確認

GPSfishと対局して、強さの確認を行った。
f:id:TadaoYamaoka:20180509110213p:plain
1手3秒50回対局で勝率は72%となり、変更前とほぼ同じ勝率となった。

2スレッドの効果

GPUあたり2スレッドで探索を行うことの効果を確認した。

スレッド数 探索速度(シミュレーション/秒)
1 13154
2 14158
3 14057

スレッド数を2にすると1の場合よりも探索速度が向上している。3にしてもGPU計算が競合するため意味がない。

Linuxでの速度

以前の実装はスレッドの同期を行うため、Linuxで性能がでなかった。
今回の実装はGPUの計算を待つ処理を直列で実装しているため、スレッドの同期が不要となっている。
そのため、Linuxでも探索速度が上がることが期待できる。
そこで、探索速度をLinuxで測定を行った。

スレッド数 探索速度(シミュレーション/秒)
変更前 168×2 2258
変更後 2×2(バッチサイズ192) 11388

探索速度が5倍に向上した。
しかし、Windowsの8割程度なので、まだ改善の余地はありそうである。

スケーラビリティ

GPUの枚数をさらに増やした場合に、探索速度が向上するかAWSの4GPUのインスタンス(p3.8xlarge)で確認を行った。

GPU枚数 探索速度(シミュレーション/秒) 探索の深さ 探索時間(秒)
1 9416 30 9.512
2 18529 35 4.533
3 27475 35 2.632
4 35701 33 2

※バッチサイズ192
※初期局面で10万回シミュレーション
f:id:TadaoYamaoka:20180509111510p:plain
探索速度がほぼ線形に伸びている。
10万回シミュレーションで測定しているため、探索の深さは深くなっていないが、同じ時間の探索ではより多くのシミュレーションが行えるため、深さも深くできる可能性がある。

そこでGPU枚数4枚でシミュレーション回数を40万回にして測定を行った。

シミュレーション回数 探索速度(シミュレーション/秒) 探索の深さ 探索時間(秒)
10万 35701 33 2
40万 36298 37 9.077

探索時間は、GPU1枚のときと同じだが、探索の深さはより深く探索できている。
探索速度の向上が、強さに結びつくことが予想できる。

まとめ

探索とGPU計算の直列化によって、探索速度を改善できることが確認できた。
自己対局による強化学習の実行速度も改善できそうなので、変更を行う予定である。
実装方法を教えていただいた、ねね将棋の日高さんに感謝いたします。