アルファゼロを構築しましょう

本文は、Sunrise：AlphaZero、MCTS、Self-Play、UCB を基礎から理解するなどの文章、動画チュートリアル、コード実装の消化と理解を目的としています。この記事では、AlphaGo の設計原理から出発し、MCTS と Self-Play という 2 つのコアメカニズムを深く理解することで、人間を超える AI 五子棋（Gomoku）システムを構築する方法を段階的に明らかにします。

AlphaGo：模倣から超越へ#

AlphaGo の進化の道筋#

囲碁の可能な局面数は宇宙の原子の数を超えており、従来の網羅的探索方法は完全に無効です。AlphaGo は段階的なアプローチでこの問題を解決しました：まず人間の知識を学び、その後 self-play を通じて進化を続けます。
Pasted image 20241116201853
この進化プロセスは 3 つの層に分けられます：

人間の高手を模倣する
自己対戦による向上
状況評価を学ぶ

コアコンポーネント#

Pasted image 20241115170343

高速手法戦略（Rollout Policy）#

最左の軽量な戦略ネットワークで、迅速な評価に使用され、精度は低いが計算効率が高いです。

SL 戦略ネットワーク#

監視学習戦略ネットワーク $P_{\sigma}$ は人間の棋譜を模倣して学習します：

入力：盤面状態
出力：人間の専門家の次の手の確率分布を模倣
トレーニングデータ：16 万局、約 3000 万の手のステップ

RL 戦略ネットワーク#

一定のレベルに達したときに自分で振り返り、自分自身と対戦し、新しい戦術やより深い戦略を発見するのに似ています。RL ネットワーク $P_{\rho}$ は SL ネットワークから初期化され、このネットワークはすでに人間を超えており、多くの人間が発見していない強力な戦略を見つけることができます。

この段階では大量の self-play データが生成され、入力は依然として盤面状態で、出力は強化学習によって改善された手の戦略です。
歴史的なバージョンの戦略ネットワーク $p_\pi$ と self-play を行い、ネットワークは「勝利」の信号を通じてパラメータを調整し、勝利をもたらす手を強化します：

\sum_{t} z(\tau) \log p(a_t \mid s_t; \rho)

ここで：

$\tau$ は対局のシーケンス $(s_0,a_0,s_1,a_1,...)$
$z(\tau)$ は勝敗ラベル（勝ちが正、負けが負）

価値ネットワーク#

価値ネットワーク $v_\theta$ は状況評価を学習し、CNN である可能性があります：

トレーニング目標：平均二乗誤差を最小化

\sum_{i} (z - v_\theta(s))^2

$z$ ：最終的な勝敗結果
$v_\theta(s)$ ：予測された勝利確率

補足説明#

$P_\rho$ と $v_\theta$ の関係について：

戦略ネットワーク $P_\rho$ は具体的な手の確率を提供し、探索をガイドします。
価値ネットワーク $v_\theta$ は局面評価を提供し、探索木の中で不必要なシミュレーションを減少させます。
両者が組み合わさることで、MCTS は高勝率のパスをより迅速に探索できるだけでなく、全体の棋力を大幅に向上させます。

AlphaGo の MCTS 実装#

Selection 段階#

探索と利用を組み合わせています：

a_t = \arg\max_a Q(s_t, a) + u(s_t, a)

u(s_t, a) \propto \frac{P(s_t, a)}{1 + N(s_t, a)}

ここで：

$Q(s_t, a)$ ：長期的なリターンの推定
$u(s_t, a)$ ：探索報酬
$P(s_t, a)$ ：戦略ネットワーク出力の事前確率
$N(s_t, a)$ ：訪問回数

Simulation と評価#

元の MCTS アルゴリズムでは、シミュレーション段階の役割は、迅速な rollout 戦略を使用して葉ノード（拡張された新しいノード）からランダムに対局を行い、ゲームが終了するまで続け、その結果に基づいて報酬を得ることです。この報酬は探索木のノードに戻され、これらのノードの値推定（すなわち $Q(s, a)$ ）を更新するために使用されます。

この実装はシンプルで直接的ですが、rollout 戦略は通常ランダムまたは単純なルールであり、シミュレーションの質が低い可能性があります。また、短期的な情報しか提供できず、全体的な戦略評価をうまく組み合わせることができません。

AlphaGo はシミュレーション段階で価値ネットワーク $v_\theta$ と rollout 戦略を組み合わせました。価値ネットワークはより効率的な葉ノードの推定と全体的な能力評価を提供し、rollout 戦略は迅速なシミュレーションを通じて局所的な短期効果を捉えます。

超パラメータ $\lambda$ を使用して $v_\theta(s_L)$ と $z_L$ のバランスを取り、局所的なシミュレーションと全体的な評価を両立させます。評価関数：

V(s_L) = (1 - \lambda)v_\theta(s_L) + \lambda z_L

Backpropagation#

n 回の MCTS でノードの訪問回数を更新します（ $\mathbb{I}$ は指示関数で、訪問時は 1）：

N(s_t, a) = \sum_{i=1}^{n} \mathbb{I}(s, a, i)

Q 値の更新、すなわちノード $s_t$ への手 a の長期的な期待リターンを実行します：

Q(s_t, a) = \frac{1}{N(s_t, a)} \sum_{i=1}^{n} \mathbb{I}(s, a, i) V(s_L^i)

まとめ#

構造的革新：
- 戦略ネットワークは事前知識を提供
- 価値ネットワークは全体評価を提供
- MCTS は戦術検証を提供
トレーニング革新：
- 監視学習からスタート
- 強化学習を通じて教師を超える
- 自己対戦によって新しい知識を生成
MCTS の改善：
- ニューラルネットワークを使用して探索をガイド
- ポリシーネットワークは探索方向の事前確率を提供し、価値ネットワークは葉ノードの評価の正確性を向上させました。
- 価値ネットワークと rollout の評価を組み合わせることで、探索の幅と深さを減少させるだけでなく、全体の性能を大幅に向上させました。
- 効率的な探索 - 利用のバランス

この設計により、AlphaGo は広大な探索空間の中で効率的な解決策を見つけ、最終的に人間のレベルを超えることができました。

ヒューリスティック探索と MCTS#

MCTS は、意思決定ツリーの中で最適なパスを探す進化し続ける探索者のようなものです。

コアアイデア#

MCTS の本質は何でしょうか？簡単に言えば、それは「遊びながら学ぶ」プロセスです。新しいボードゲームをプレイしていると想像してみてください：

最初は、さまざまな可能な手を試みます（探索）
次第に、特定の手がより良い結果をもたらすことに気づきます（利用）
新しい戦略を探索し、既知の良い戦略を利用する間でバランスを取ります

これが MCTS が行っていることです。ただし、数学的な方法でこのプロセスを体系化しています。これは rollout アルゴリズムであり、累積したモンテカルロシミュレーションの価値推定を通じて戦略選択を導きます。

アルゴリズムの流れ#

Monte Carlo Tree Search - YouTube この先生は MCTS の流れを非常にうまく説明しています。

MCTS の優雅さは、4 つのシンプルでありながら強力なステップにあります。ここでは A と B の 2 つの理解方法を用いて紹介します：

選択 (Selection)
- A：子供がどのように学ぶか知っていますか？彼らは常に既知と未知の間をさまよっています。MCTS も同様です：根ノードから始まり、UCB（Upper Confidence Bound）公式を使用して、既知の良いパスを選択するか、新しい可能性を探索するかを評価します。
- B：根ノードから出発し、特定の戦略に基づいて現在のノードから次のノードを選択します。この戦略は通常、ツリーの探索履歴に基づいており、最も潜在能力の高いパスを選択します。たとえば、各ノードで現在の戦略 $\pi(s)$ に基づいてアクション $a$ を実行し、探索と利用のバランスを取りながら徐々に深く進んでいきます。
拡張 (Expansion)
- A：探検家が地図上で新しい領域を開拓するように、葉ノードに到達したときに下に拡張し、新しい可能性を作成します。
- B：選択されたノードに未探索の子ノードがある場合、そのノードの下で行動可能なアクションセットに基づいて新しいノードを拡張します。このプロセスの目的は、意思決定ツリーの幅を増やし、可能な意思決定パスを徐々に生成することです。この拡張操作を通じて、探索がより多くの可能な状態アクションペア $(s,a)$ をカバーすることを保証します。
シミュレーション (Simulation)
- A：これは最も面白い部分です。新しいノードから始めて、「もし私がこう動いたら、相手がああ動く...」という形でゲームを「仮想的」に行います。
- B：現在拡張されたノードから出発し、ランダムシミュレーション（rollout）を実行し、MDP 環境内で現在の戦略 $\pi(s)$ に沿ってサンプリングを行い、終了状態まで進みます。このプロセスは、現在のノードから終点までの報酬推定を提供し、パスの優劣に数値的根拠を与えます。
バックプロパゲーション (Backpropagation)
- A：最後に、得られた結果をパスに沿って戻し、各ノードの統計情報を更新します。これは、「ねえ、私はこの道を試してみたけど、なかなか良かった（またはあまり良くなかった）」と言っているようなものです。
- B：シミュレーションが完了した後、そのシミュレーションの推定報酬を経由したすべてのノードに戻し、これらのノードの価値を更新します。このプロセスは、歴史的な報酬情報を蓄積し、将来の選択がより正確に高リターンのパスに向かうようにします。

Screenshot 2024-10-31 at 15.19.31

UCB1：探索と利用の完璧なバランス#

ここで特に UCB1 公式に言及する必要があります。これは MCTS の魂です：

UCB1 = X̄ᵢ + C × \sqrt{(ln(N)/nᵢ)}

これを分解してみましょう：

$X̄ᵢ$ は平均リターン（利用項）
$\sqrt{(ln(N)/nᵢ)}$ は不確実性の測定（探索項）
$C$ は探索パラメータ

優れた投資ポートフォリオのように、既知の良い機会に注意を払いながら、新しい機会に対してもオープンでいる必要があります（探索 - 利用のバランス）。

Best Multi-Armed Bandit Strategy? (feat: UCB Method) この動画は Multi-Armed Bandit と UCB Method について非常に良く説明しています。ここではこの先生が使った例を借りています：

食いしん坊が UCB を理解しようとする#

あなたが新しい都市に到着し、選べるレストランが 100 軒あると想像してみてください。あなたには 300 日間の時間があります。毎日、あなたはレストランを選んで食事をし、300 日間で平均して最も良い料理を食べたいと思っています。

ε-greedy 戦略：シンプルだが十分ではない#

これはサイコロを振って決めるようなものです：

90％の時間 (ε=0.1)：既知の最良のレストランに行く（利用）
10％の時間：ランダムに新しいレストランを試す（探索）

def epsilon_greedy(restaurants, ratings, epsilon=0.1):
    if random.random() < epsilon:
        return random.choice(restaurants)  # 探索
    else:
        return restaurants[np.argmax(ratings)]  # 利用

このような効果があります：

探索は完全にランダムで、既知の悪いレストランを繰り返し訪問する可能性があります
探索の割合は固定されており、時間とともに調整されません
訪問回数の影響を考慮しません

UCB 戦略：よりスマートな選択のバランス#

UCB 公式がレストラン選択において意味するところは次の通りです：

スコア = 平均スコア + C × \sqrt{ln(総訪問日数)/そのレストランの訪問回数}

例えば、100 日目の 2 つのレストランの状況を考えてみましょう：

A レストラン：

50 回訪問、平均スコア 4.5
UCB スコア = $4.5 + 2×\sqrt{ln(100)/50} ≈ 4.5 + 0.6 = 5.1$

B レストラン：

5 回訪問、平均スコア 4.0
UCB スコア = $4.0 + 2×\sqrt{ln(100)/5} ≈ 4.0 + 1.9 = 5.9$

B レストランは平均スコアが低いですが、訪問回数が少なく不確実性が高いため、UCB はより高い探索報酬を与えます。

Screenshot 2024-11-07 at 13.24.48

コード実装：

class Restaurant:
    def __init__(self, name):
        self.name = name
        self.total_rating = 0
        self.visits = 0
        
def ucb_choice(restaurants, total_days, c=2):
    # 各レストランを少なくとも1回訪問することを保証
    for r in restaurants:
        if r.visits == 0:
            return r
            
    # UCB公式を使用してレストランを選択
    scores = []
    for r in restaurants:
        avg_rating = r.total_rating / r.visits
        exploration_term = c * math.sqrt(math.log(total_days) / r.visits)
        ucb_score = avg_rating + exploration_term
        scores.append(ucb_score)
        
    return restaurants[np.argmax(scores)]

なぜ UCB が優れているのか？#

適応的探索
- 訪問回数が少ないレストランはより高い探索報酬を得る
- 総日数が増えるにつれて、探索項は徐々に減少し、より良い利用が行われる
時間投資のバランス
- 明らかに悪いレストランにあまり多くの時間を浪費しない
- 潜在能力が近いレストラン間で訪問回数を合理的に分配する
理論的保証
- Regret Bound（最適選択とのギャップ）は時間とともに対数的に増加する
- 300 日の探索で最良のレストランを見つけるのに十分です

MCTS に戻りましょう。

なぜ MCTS はこれほど強力なのか？#

特定の知識を必要としない
特定のゲーム戦略の知識を必要とせず、自己探索を通じて良い行動を見つけることができます。
いつでも停止可能
いつでも探索を中断しても、現在の最良の選択を提供できます。これはリアルタイムシステムに特に有用です。
自然な探索 - 利用のバランス
UCB メカニズムを通じて、新しい戦略を探索することと、既知の良い戦略を利用することの間で自動的にバランスを取ります。

AlphaZero：MCTS から自己進化へ#

Self-Play#

ここでは、schinger/alphazero.pyの優れた実装を学び、参考にします。

参考資料#

知乎 Sunrise：AlphaZero、MCTS、Self-Play、UCB を基礎から理解する