前回の記事ではMCTSにおける行動価値の更新を漸進的実装に変更したが、並列化した際に性能が悪化することがわかった。
MCTSの並列化方法として現在実装しているのはねね将棋、dlshogiで採用されているものと同様の方法である。1GPUにつきCPUが2スレッド稼働し、各スレッドはバッチサイズ分だけ選択ステップを繰り返して評価したい局面を貯め、GPUにまとめて評価してもらい、返ってきた状態価値をバックアップする。GPUでの計算に対してCPUの計算要求を貯める速度は十分に速いため、GPUを交互に利用するような形になる。
バッチサイズ分だけ選択ステップを繰り返す際に、同じパスを何度も選択しないよう、一度選択したパスにはバーチャルロス1というものを加える手法が一般的となっている。MCTSの性質上、選択回数が多いパスの優先度は下がるため、バーチャルロスを加えることで同じパスを選択しにくくなる。バーチャルロスは任意の大きさに設定できるが、一般的には1とすることが多いようだ。
バーチャルロスは重複に注意して実装しなければならない。Policyが偏っているとバーチャルロスを加えても同じパスを何度も探索する場合がありうる。極端な状況として、10回選択ステップを行って以下のような配分になった場合を考える。
このとき、GPUに同じ局面を10回評価させるのは無駄なため、局面の重複を削除してGPUに送るとする。またバックアップにおいて重複回数を引き、まるでR-Aという選択が1回行われたかのように補正する必要がある。報酬の和と選択回数を保持する実装ならこれで上手くいく。
しかし漸進的更新では問題が発生する。たとえば次のような探索木ができている状態から選択ステップを10回行う状況を考える。結果として辺の横に書いてあるような回数パスが選択されたとする。
評価が行われ、先にR-A-Dのパス、次にR-A-Eのパスという順番でバックアップが行われたとする。バーチャルロスを含めた探索回数は次の図のように変化する。最終的に重複を含まないような探索回数になる。
問題になるのは1枚目、R-A-Dをバックアップしたあとの探索回数であり、ここでR-Aの辺は探索回数が7となっている。よってこのバックアップで学習率はとして更新される。しかしここで正しい探索回数は2であり、このタイミングでは
で更新されなければならず、漸進的更新によって不当に小さく評価されてしまう。
学習率が小さくなった場合に性能が悪化することは自明ではないが、実験結果では悪くなっている。理由として探索回数が少ない時点で更新が上手く進まず、良い推定値になるまで時間がかかるようになっているからだと考えられる。MCTSにおいて探索回数の少ないノードは常にリーフノード付近で存在するため、それらの推定値が悪ければ木全体としてやはり良い手を選択できないようになっている可能性がある。
バッチサイズを大きくすればするほど重複しやすくなると考えられるため、漸進的更新の性能が悪化すると予想される。効率的なGPU利用にはバッチ式で評価することは欠かせないため、修正案を考えなければならない。次回に続く。
-
Chaslot, G., Winands, M., and van den Herik, J.(2008), “Parallel Monte-Carlo Tree Search,” In the 6th Internatioal Conference on Computers and Games, volume 5131, pages 60–71, Springer Berlin Heidelberg, 2008.↩
