AlphaGo では、畳み込みニューラルネットワークでモデル化した状態価値関数、および方策関数を用いることで、探索の深さと幅を減らしている。

学習

1. SL 方策ネットワーク（SL: 教師あり学習）

プロの手を教師データとして学習する。
入力は盤面、出力はそれぞれ合法的な手を選ぶべき確率 \(p_{\sigma}(a \vert s)\)
パラメータの更新は以下の式で行う

\[\Delta \sigma = \frac{\alpha}{m} \sum_{k=1}^{m} \frac{\partial \log p_{\partial}(a^k|s^k)}{\partial \sigma}\]

2. RL 方策ネットワーク（RL: 強化学習）

SL ネットワークで学習させた初期値を利用し、今度はランダムに選択された手同士を戦わせる。
ランダムに選択する理由は、現在の方策に対して過剰適合しないようにするため。
パラメータの更新は以下の式で行う。

\[\Delta \rho = \frac{\alpha}{n} \sum_{i=1}^{n} \sum_{t=1}^{T^i} \frac{\partial \log p_{\rho}(a_t^i|s_t^i)}{\partial \rho}(z_t^i - v(s_t^i))\]

3. 盤面に関する価値関数を評価

盤面 s における価値関数 \(v^p(s)\) は、両方のプレイヤーが方策 p を用いた場合、

\(v^p(s) = E[z_t|s_t = s, a_t, ..., a_T ~ p]\) ただ、最適な方策は分からないため、 RL 方策ネットワーク p_{\rho} に対する価値関数を評価する。
また、価値関数をパラメータ \(\theta\) の価値ネットワーク \(v_{\theta}(s)\) でモデル化する。
パラメータの更新は以下の式で行う。

\[\Delta \theta = \frac{\alpha}{m} \sum_{k=1}^{m} (z^k - v_{\theta}(s^k)) \frac{\partial v_{\theta}(s^k)}{\partial \theta}\]

目標出力 z を得るための大戦では、 t < U-1 の時間ステップでは SL 方策ネットワークから、 t > U+1 の時間ステップは RL 方策ネットワーク \(p_{\rho}\) から差し手を選ぶ。
t=T の時はランダムに指し手を選択する。

実戦(モンテカルロ木探索)

AlphaGoは、モンテカルロ木探索で選択肢を評価する「勝率」と「バイアス」に深層学習モデルを使った補正をしている。
打った手の勝率の予測を勝率の補正に使い、次の一手の予測をバイアスの補正に使う。
勝敗のカウントは、計算の速いロジスティック回帰が手を進めた結果を数える。

選択

探索木のルートからシュミレーションを始め、葉（木の末端）に到達した時点で終える。
終了時点のタイムステップを L とする。
各時間ステップ t < L で、行動を \(a_t = argmax_a(Q(s_t, a) + u(s_t, a))\) のように選ぶ。
ここで、

\[u(s_t, a) = C_{PUCT}P(s, a) \frac{\sqrt{\sum_b N_r (s, b)}}{1 + N_r (s, a)}\]

これは PUCT アルゴリズムに基づくボーナス項目であり、多く訪問した手については採用確率を低くし、広い探索を促進する役割がある。
\(C_{PUCT}\) は定数。

展開

訪問回数が閾値を超えたら、 s から行動選択した結果の状態 s’ を探索木に追加する。

評価

葉 \(s_L\) を 2 つの方法で評価する。
1 つ目は価値ネットワーク \(v_{\theta}(s_L)\) による評価。
2 つ目は、ロールアウトによる評価。
葉 \(s_L\) からロールアウトをゲームが終了するまで行う。
ロールアウトの時間ステップ \(t \geq L\) では、双方のプレイヤーの行動はロールアウト方策 \(p_{\pi}(a|s)\) を使って選択する。
ゲームが終わったら、報酬 \(z_t = r(s_T)\) を計算する。
\(r(s_T)\) は最終タイムステップ T における報酬であり、買ったら 1、負けたら -1 である。

記録

時間ステップ \(t \leq L\) では、ロールアウトの統計をあたかも \(n_rl\) 回負けたかのように更新しておく。
こうすることで、並列で走っている計算が同じノードをシュミレートする可能性を下げることができる。
1 回のシュミレーションが終了したら、負け分は元に戻しておく。

各状態、行動の評価値はモンテカルロ平均で与えることとし、

\[Q(s, a) = (1 - \lambda) \frac{W_v (s, a)}{N_v (s, a)} + \lambda \frac{W_r (s, a)}{N_r (s, a)}\]

以上の操作が終われば、再びルートからシュミレーションを繰り返す。
与えられた時間内でシュミレーションを繰り返し、探索が終了したら 最も訪問回数が多い 行動を次の指し手として採用する。

AlphaStar

2019 年 1 月に、 StarCraft2 というゲームでプロプレイヤーを破った AI。
Transformer、 LSTM、 ResNet などの構造を採用している。