TadaoYamaokaの日記

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

AlphaGo Zeroの論文を読む その3(探索アルゴリズム)

その2の続き

今回は対局時の探索アルゴリズムについてです。

探索アルゴリズム

対局時はpolicyとvalueを使ったモンテカルロ木探索(APV-MCTS)を使用する。
探索は複数スレッドで並列に行う。

探索木の各ノードsは以下の情報を持つ。

N(s,a) 行動aの訪問回数
W(s,a) 行動aの行動価値の合計
Q(s,a) 行動aの行動価値の平均
P(s,a) 行動aの事前確率

選択

展開済みノードの選択は、以前のAlphaGo(Fan Huiバージョン)と同じPUCTアルゴリズムを使う。

PUCTアルゴリズム

UCTアルゴリズムをpolicyを使って拡張したアルゴリズム
UCB1に代わって以下の式を使用する。
Q(s_t,a)+U(s_t,a)
この値が最大となる行動aを選択する。
Q(s,a)valueから算出される(後述)。
U(s,a)は、policyの遷移確率P(s,a)を事前確率として使用した以下の式で計算される。
U(s,a)=c_{puct} P(s,a) \frac{\sqrt{\sum_b N(s,b)}}{1+N(s,a)}
c_{puct}は定数で、具体的な値は記載されていない。
以前のAlphaGoでは5が使われていた。

展開と評価

末端ノードLに到達したら、局面評価用キューに追加する。
キューに追加する際、8つの対称(反転、回転)な局面から1つランダムに選ぶ。

キューが8たまるとミニバッチを実行する。評価が完了するまで探索スレッドはロックする。
評価が完了すると、ノードを展開し、以下の値で初期化する。
N(s_L,a)=0, W(s_L,a)=0, Q(s_L, a)=0, P(s_L,a)=p_a
p_aはpolicyの出力値。

バックアップ

末端ノードからルートノードまで、訪問した順を逆にたどって、以下の通り各ノードを更新する。

訪問回数N(s,a)をインクリメントする。
N(s_t,a_t)=N(s_t,a_t)+1

行動価値を更新する。
W(s_t,a_t)=W(s_t,a_t)+v
vは、末端局面の評価で出力されたvalue

行動価値の平均を更新する。
Q(s_t,a_t)=\frac{W(s_t,a_t)}{N(s_t,a_t)}

なお、訪問回数は、複数スレッドで同一局面を探索しないように、バーチャルロス(訪問回数を先にインクリメントしておく)を使用する。

打ち手決定

探索終了後、ルートノードの訪問回数から遷移確率を計算する。
\pi(a|s_0)=\frac{N(s_0,a)^{1/\tau}}{\sum_b N(s_0,b)^{1/\tau}}
\tauは温度パラメータ。温度が低いと差が開き、温度が高いと均一になる。0の場合は常に最大の手を選択する。

選択したノードの子ノードは次のステップで再利用する。
それ以外のノードとその子ノードは破棄する。

ルートノードのvalueと最善手を選んだ後の局面のvalue閾値以下の場合、投了する。

以前のAlphaGoとの比較

以前のAlphaGoと比較して、rolloutを使用しないことが主要な違い。

以前のAlphaGoでは、policyの計算中に線形関数を使用した軽量のtree policyを使用し、また、valueの計算中に軽量のrollout policyを使用してrolloutを行ってvalueとrolloutの平均を報酬としていましたが、単純にニューラルネットワークの実行を待つようになっています。

将棋AIに応用する際の考察

rolloutを使用しないPUCTアルゴリズムが将棋AIでもある程度有効であることは、同様アルゴリズムを使用しているdlshogiがfloodgateでrating 2700になっていることで確かめています。
policyとvalueの精度が高くなれば、PUCTアルゴリズムを使ってまだ強くなる余地があると考えています。

評価する局面を8対称からランダムで選んでいるのは面白いと思いました。
精度をあまり落とさずにランダム性を持たせることができます。
将棋の場合は初期局面に対称性がない(飛車、角の位置が違う)ので対称な局面を考慮してもあまり意味がないと思われるので、この手法は使えなさそうです。

末端局面の初期化の際、dlshogiでは、W(s_L,a)=v, Q(s_L, a)=vとしていましたが、vを行動価値ととらえるとAlphaGo Zeroの方が正しい初期化の気がしました。

打ち手の決定は、最大の訪問回数の手を選択しないで、遷移確率に従っているのは自己対局で訓練データを生成する際はより適切と思いました。
プレイヤーとの対局時は、最大の訪問回数の手を選んでもよいと思います。

続く