その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アルゴリズムを使う。
展開と評価
末端ノードLに到達したら、局面評価用キューに追加する。
キューに追加する際、8つの対称(反転、回転)な局面から1つランダムに選ぶ。
キューが8たまるとミニバッチを実行する。評価が完了するまで探索スレッドはロックする。
評価が完了すると、ノードを展開し、以下の値で初期化する。
はpolicyの出力値。
バックアップ
末端ノードからルートノードまで、訪問した順を逆にたどって、以下の通り各ノードを更新する。
訪問回数N(s,a)をインクリメントする。
行動価値を更新する。
vは、末端局面の評価で出力されたvalue。
行動価値の平均を更新する。
なお、訪問回数は、複数スレッドで同一局面を探索しないように、バーチャルロス(訪問回数を先にインクリメントしておく)を使用する。
打ち手決定
探索終了後、ルートノードの訪問回数から遷移確率を計算する。
は温度パラメータ。温度が低いと差が開き、温度が高いと均一になる。0の場合は常に最大の手を選択する。
選択したノードの子ノードは次のステップで再利用する。
それ以外のノードとその子ノードは破棄する。
以前の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の方が正しい初期化の気がしました。
打ち手の決定は、最大の訪問回数の手を選択しないで、遷移確率に従っているのは自己対局で訓練データを生成する際はより適切と思いました。
プレイヤーとの対局時は、最大の訪問回数の手を選んでもよいと思います。
続く