"A Lock-Free Multitheaded Monte-Carlo Tree Search Algorithm"

概要：
マルチスレッドでモンテカルロ木探索(MCTS)を効率良く行う方法

MCTSのマルチスレッド版がある。アルゴリズムは、全スレッド共通の木が一つあり、シミュレーションを各スレッドが行う。そしてシミュレーションの結果を１回ごとに共通の木に反映させる、といったもの。
問題点は、このアルゴリズムではスレッド数が増えても勝率が上がらないような場合が経験上存在していた（らしい）。
直感的には、スレッド数とシミュレーション回数が比例せず、その理由が、共通の木にアクセスする際の排他制御が遅いからだとは思うが、明記はされてなかった。

そこで、排他制御をなくしたMCTSを提案している。変更点は、スレッドごとにシミュレーションする盤面を決定した後、複数回シミュレーションを繰り返し、排他制御しないで結果を親にリンクさせるという単純なもの。その際、２つのスレッドが同一盤面をシミュレーションしていたら情報が失われる可能性はあるが、著者曰く経験上大丈夫らしい。

結果として勝率は良くなっているんだけど、シミュレーション回数がどれだけスレッド数に対してスケールしてるかや、排他制御を無視したことでどれだけ情報が失われたかなどは計測していなかったのが非常に残念。

また、Fuegoを拡張してC++で書いているらしいけど、シミュレーションが19x19の盤で2750回/秒・コアできるらしい。結構思ったより高速なので、春休みにプログラム覗いてみたいなーと思う。