MCTS 與神經網路的結合

前面的文章中，我們分別介紹了神經網路（Policy Network 和 Value Network）以及強化學習的概念。現在，讓我們探討 AlphaGo 的核心創新——如何將蒙地卡羅樹搜索（MCTS）與神經網路完美結合。

這個結合是 AlphaGo 成功的關鍵：神經網路提供「直覺」，MCTS 提供「推理」，兩者相輔相成。

---

傳統 MCTS 回顧

什麼是 MCTS？

蒙地卡羅樹搜索（Monte Carlo Tree Search, MCTS） 是一種基於隨機採樣的搜索算法，特別適合用於遊戲 AI。

MCTS 的核心思想是：與其窮舉所有可能的走法，不如隨機模擬大量對局，用統計來估計每個走法的好壞。

四個階段

傳統的 MCTS 包含四個階段，不斷重複：

讓我們詳細了解每個階段：

1. Selection（選擇）

從根節點開始，沿著樹向下，選擇「最有希望」的子節點，直到到達葉節點。

選擇的標準是 UCB1（Upper Confidence Bound） 公式：

$\text{UCB1}(s, a) = \bar{X}_{s,a} + c \sqrt{\frac{\ln N_s}{N_{s,a}}}$

其中：

• $\bar{X}_{s,a}$：從節點 $(s, a)$ 出發的平均回報（利用項）
• $\sqrt{\frac{\ln N_s}{N_{s,a}}}$：探索加成（探索項）
• $N_s$：父節點的訪問次數
• $N_{s,a}$：子節點的訪問次數
• $c$：平衡探索與利用的常數

這個公式的智慧在於：

• 訪問次數少的節點會得到更高的探索加成
• 隨著訪問次數增加，選擇會越來越偏向實際價值高的節點

2. Expansion（展開）

到達葉節點後，選擇一個未被探索的動作，創建新的子節點。

3. Simulation（模擬/Rollout）

從新節點開始，用某種策略（通常是隨機或簡單啟發式）快速完成對局，得到結果。

這就是「蒙地卡羅」名稱的來源——用隨機模擬來估計結果。

傳統 MCTS 的 rollout 策略可能是：

• 純隨機：均勻隨機選擇合法走法
• 輕量級啟發式：用簡單規則過濾明顯的壞棋

4. Backpropagation（反向傳播）

將模擬的結果（勝/負）沿著路徑回傳，更新每個節點的統計資訊：

更新內容：
- 訪問次數：N(s, a) ← N(s, a) + 1
- 累積價值：W(s, a) ← W(s, a) + z
- 平均價值：Q(s, a) = W(s, a) / N(s, a)

其中 $z$ 是模擬結果（+1 或 -1）。

傳統 MCTS 的限制

傳統 MCTS 在圍棋上的表現有限，主要問題是：

1. Rollout 品質差：隨機模擬經常產生不合理的對局
2. 需要大量模擬：每步棋可能需要數萬次模擬
3. 評估不準確：單純靠勝負統計，資訊利用效率低
4. 無法利用模式：每次都重新搜索，不累積經驗

這些問題在 AlphaGo 中被神經網路優雅地解決了。

---

神經網路如何改進 MCTS

整體架構

AlphaGo 將兩個神經網路整合進 MCTS：

Policy Network 的角色

Policy Network 在 Expansion 階段發揮作用。

傳統 MCTS 在展開時，所有未探索的動作被視為同等重要。但 Policy Network 提供了先驗機率（prior probability）：

$P(s, a) = \pi_\theta(a|s)$

這讓 MCTS 優先探索那些「看起來更好」的走法，大幅提高搜索效率。

例如，在一個局面中：

• 「天元」可能只有 0.01% 的機率
• 「角部定式」可能有 15% 的機率
• 「大場」可能有 10% 的機率

MCTS 會優先探索高機率的走法，而不是浪費時間在明顯不好的選擇上。

Value Network 的角色

Value Network 在 Evaluation 階段發揮作用。

傳統 MCTS 需要完成整局模擬才能得到評估。但 Value Network 可以直接評估任何局面的勝率：

$v(s) = V_\phi(s)$

這就像請一位大師評估局面，而不是讓兩個初學者下完整局再看結果。

AlphaGo 原版混合使用 Value Network 和 Rollout：

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

其中：

• $v_\theta(s_L)$：Value Network 的評估
• $z_L$：Rollout 的結果
• $\lambda$：混合係數（AlphaGo 使用 $\lambda = 0.5$）

搜索樹視覺化

讓我們視覺化一個 MCTS 搜索樹：

載入中...

在這個視覺化中，你可以看到：

• 節點大小反映訪問次數
• 藍色路徑是 MCTS 選擇的最佳路徑
• 每個節點顯示訪問次數 N 和平均價值 Q

---

搜索過程詳解

完整流程

讓我們跟蹤一次完整的 MCTS 模擬：

演算法：AlphaGo MCTS 單次模擬

輸入：根節點 s_root，Policy Network π，Value Network V

1. Selection（選擇）
   s = s_root
   路徑 = []

   while s 不是葉節點:
       # 使用 PUCT 公式選擇動作
       a* = argmax_a [Q(s,a) + U(s,a)]

       其中 U(s,a) = c_puct · P(s,a) · √N(s) / (1 + N(s,a))

       路徑.append((s, a*))
       s = 執行動作 a* 後的狀態

2. Expansion（展開）
   如果 s 不是終局狀態:
       # 用 Policy Network 計算先驗機率
       P(s, ·) = π(·|s)

       # 為所有合法動作創建子節點
       for a in 合法動作:
           創建子節點 (s, a)
           設置 P(s,a), N(s,a)=0, W(s,a)=0

3. Evaluation（評估）
   # 混合 Value Network 和 Rollout
   v = V(s)                          # Value Network 評估
   z = rollout(s)                    # Rollout 結果
   value = (1-λ)·v + λ·z             # 混合

   # AlphaGo Zero 簡化為只用 Value Network
   # value = V(s)

4. Backpropagation（反向傳播）
   for (s', a') in 反向(路徑):
       N(s', a') += 1
       W(s', a') += value
       Q(s', a') = W(s', a') / N(s', a')
       value = -value                 # 切換視角

選擇階段詳解

選擇階段使用 PUCT 公式（將在下一篇詳細討論）：

$a^* = \arg\max_a \left[ Q(s,a) + c_{\text{puct}} \cdot P(s,a) \cdot \frac{\sqrt{N(s)}}{1 + N(s,a)} \right]$

這個公式平衡了：

• Q(s,a)：已知的平均價值（利用）
• U(s,a)：探索加成，結合先驗機率和訪問次數（探索）

展開階段詳解

當到達葉節點時，使用 Policy Network 初始化新節點：

def expand(state, policy_network):
    # 獲取所有合法動作的機率
    action_probs = policy_network(state)

    # 過濾非法動作並重新歸一化
    legal_actions = get_legal_actions(state)
    legal_probs = action_probs[legal_actions]
    legal_probs = legal_probs / legal_probs.sum()

    # 創建子節點
    for action, prob in zip(legal_actions, legal_probs):
        child = create_node(
            state=apply_action(state, action),
            prior=prob,
            visit_count=0,
            value_sum=0
        )
        add_child(current_node, action, child)

評估階段詳解

AlphaGo 原版混合使用兩種評估：

Value Network 評估：

• 直接輸入局面，輸出勝率
• 計算快速（一次神經網路推理）
• 提供全局視角的評估

Rollout 評估：

• 用快速策略（Fast Rollout Policy）完成對局
• 計算較慢但提供完整的對局結果
• 可以發現一些神經網路可能忽略的戰術

def evaluate(state, value_network, rollout_policy, lambda_mix=0.5):
    # Value Network 評估
    v = value_network(state)

    # Rollout 評估
    current = state
    while not is_terminal(current):
        action = rollout_policy(current)
        current = apply_action(current, action)
    z = get_result(current)

    # 混合
    return (1 - lambda_mix) * v + lambda_mix * z

AlphaGo Zero 移除了 Rollout，只使用 Value Network。這簡化了系統並提高了效率。

反向傳播詳解

將評估結果沿路徑回傳，更新統計：

def backpropagate(path, value):
    for state, action in reversed(path):
        # 更新訪問次數
        state.visit_count[action] += 1
        # 更新價值總和
        state.value_sum[action] += value
        # 更新平均價值
        state.Q[action] = state.value_sum[action] / state.visit_count[action]
        # 切換視角（對手的好處是我的壞處）
        value = -value

注意 value = -value 這一步：圍棋是零和遊戲，一方的勝利就是另一方的失敗。

---

計算資源分配

搜索次數

AlphaGo 在每步棋上執行大量的 MCTS 模擬：

版本	每步模擬次數	思考時間
AlphaGo Fan	~100,000	分鐘級
AlphaGo Lee	~100,000	分鐘級
AlphaGo Zero (訓練)	1,600	秒級
AlphaGo Zero (比賽)	~1,600	秒級

AlphaGo Zero 用更少的模擬達到更強的棋力，這是神經網路品質提升的結果。

時間分配策略

不同局面可能需要不同的思考時間：

def allocate_time(game_state, remaining_time):
    # 基本分配
    num_moves_remaining = estimate_remaining_moves(game_state)
    base_time = remaining_time / num_moves_remaining

    # 調整因素
    complexity = estimate_complexity(game_state)
    importance = estimate_importance(game_state)

    # 複雜或重要的局面給更多時間
    allocated_time = base_time * complexity * importance

    # 確保不超時
    return min(allocated_time, remaining_time * 0.3)

在實際比賽中，AlphaGo 會在關鍵局面（如接近勝負分界的時刻）投入更多思考時間。

並行搜索

MCTS 天然適合並行化：

虛擬損失（Virtual Loss） 技術：

當一個線程正在探索路徑 P 時：
1. 暫時假裝這條路徑已經輸了（virtual loss）
2. 其他線程會傾向探索其他路徑
3. 當結果回來時，更新真實統計並移除虛擬損失

這確保了多個線程不會重複探索相同的路徑。

def parallel_mcts_simulation(root, num_threads=8):
    virtual_losses = {}

    def simulate(thread_id):
        # 選擇階段（帶虛擬損失）
        path = []
        node = root
        while not node.is_leaf():
            action = select_with_virtual_loss(node, virtual_losses)
            add_virtual_loss(node, action, virtual_losses)
            path.append((node, action))
            node = node.children[action]

        # 展開和評估
        value = expand_and_evaluate(node)

        # 反向傳播並移除虛擬損失
        backpropagate(path, value)
        remove_virtual_losses(path, virtual_losses)

    # 並行執行多個模擬
    threads = [Thread(target=simulate, args=(i,)) for i in range(num_threads)]
    for t in threads:
        t.start()
    for t in threads:
        t.join()

GPU 批次處理

神經網路推理在 GPU 上最有效率的方式是批次處理。AlphaGo 使用批次評估：

不使用批次：
  模擬 1 → 評估 1 → 模擬 2 → 評估 2 → ...
  GPU 利用率低

使用批次：
  收集 32 個待評估的局面
  → 一次性送入 GPU 評估
  → 返回 32 個結果
  GPU 利用率高

這需要更複雜的調度，但大幅提高了吞吐量。

---

溫度與最終選擇

訓練時的溫度

在自我對弈訓練時，AlphaGo 使用溫度來控制探索：

$\pi(a) = \frac{N(s,a)^{1/\tau}}{\sum_{a'} N(s,a')^{1/\tau}}$

其中 $\tau$ 是溫度參數。

• $\tau = 1$：機率正比於訪問次數（保持多樣性）
• $\tau \to 0$：選擇訪問次數最多的動作（確定性選擇）

AlphaGo Zero 的策略：

• 前 30 手：$\tau = 1$，保持開局多樣性
• 之後：$\tau \to 0$，選擇最佳走法

比賽時的選擇

在實際比賽中，選擇通常是確定性的：

def select_move(root, temperature=0):
    if temperature == 0:
        # 選擇訪問次數最多的動作
        return argmax(root.visit_counts)
    else:
        # 按溫度調整的機率分佈採樣
        probs = root.visit_counts ** (1 / temperature)
        probs = probs / probs.sum()
        return np.random.choice(actions, p=probs)

考慮勝率

有時也會考慮平均價值而非僅訪問次數：

def select_move_with_value(root, temperature=0):
    # 混合訪問次數和價值
    scores = root.visit_counts * (1 + root.Q_values)
    scores = scores / scores.sum()

    if temperature == 0:
        return argmax(scores)
    else:
        probs = scores ** (1 / temperature)
        probs = probs / probs.sum()
        return np.random.choice(actions, p=probs)

---

與純神經網路的比較

為什麼需要搜索？

一個自然的問題是：既然神經網路已經可以預測好的走法，為什麼還需要搜索？

答案是：搜索可以修正神經網路的錯誤並發現更好的走法。

方法	優點	缺點
純神經網路	快速、直覺	可能有盲點
純 MCTS	可以深入分析	慢、需要評估
神經網路 + MCTS	結合兩者優點	計算量大

實驗證據

DeepMind 的實驗顯示：

純 Policy Network：約 3000 Elo
Policy + 少量 MCTS：約 3500 Elo
Policy + Value + MCTS：約 4500 Elo

搜索提供了顯著的棋力提升。

搜索的作用

搜索在以下情況特別有價值：

1. 戰術計算：讀出複雜的攻殺
2. 修正偏見：糾正神經網路的系統性錯誤
3. 處理罕見局面：神經網路訓練時可能沒見過
4. 驗證直覺：確認「好看」的棋確實是好棋

---

AlphaGo 各版本的差異

AlphaGo Fan/Lee

架構：
- SL Policy Network（監督學習）
- RL Policy Network（強化學習）
- Value Network
- Fast Rollout Policy

搜索時：
- 用 SL Policy Network 的先驗機率
- 混合 Value Network 和 Rollout 評估

AlphaGo Master

架構：
- 更大的神經網路
- 更多的訓練資料
- 改進的特徵

搜索時：
- 類似 AlphaGo Lee
- 更強的網路 = 更少的搜索需求

AlphaGo Zero

架構：
- 單一雙頭 ResNet
- 從零開始訓練
- 無 Rollout

搜索時：
- 策略頭提供先驗機率
- 價值頭直接評估
- 更簡潔、更強

演進總結

---

實作考量

記憶體管理

MCTS 樹可以變得很大：

假設：
- 每步平均 200 個合法動作
- 搜索深度 10
- 完全展開：200^10 ≈ 10^23 個節點（不可能）

實際做法：
- 只展開被訪問的節點
- 定期清理很少訪問的節點
- 重用上一步的搜索樹

樹的重用

當對手下棋後，可以重用部分搜索樹：

def reuse_tree(root, opponent_move):
    if opponent_move in root.children:
        new_root = root.children[opponent_move]
        # 清理不需要的其他分支
        for action in root.children:
            if action != opponent_move:
                delete_subtree(root.children[action])
        return new_root
    else:
        # 對手下了意外的棋，需要重新開始
        return create_new_root()

神經網路快取

同一局面可能被多次評估，使用快取避免重複計算：

class NeuralNetworkCache:
    def __init__(self, max_size=100000):
        self.cache = LRUCache(max_size)

    def evaluate(self, state, network):
        state_hash = hash(state)
        if state_hash in self.cache:
            return self.cache[state_hash]
        else:
            result = network(state)
            self.cache[state_hash] = result
            return result

對稱性利用

圍棋有 8 重對稱性，可以用來增強搜索：

def evaluate_with_symmetry(state, network):
    # 生成所有對稱變換
    symmetries = generate_symmetries(state)  # 8 個版本

    # 評估所有版本
    values = [network(s) for s in symmetries]

    # 平均（更穩定）
    return np.mean(values)

---

搜索深度與廣度

動態調整

MCTS 自動平衡深度與廣度：

• 廣度：由 Policy Network 的先驗機率控制
• 深度：由 Value Network 的準確度決定

當神經網路很好時：

• 高置信的走法會被深入探索
• 低置信的走法被快速排除
• 搜索自然聚焦在重要的分支

與傳統搜索的比較

方法	深度控制	廣度控制
Minimax	固定深度	Alpha-Beta 剪枝
傳統 MCTS	由模擬決定	UCB1
AlphaGo MCTS	Policy + Value 引導	PUCT + Policy

AlphaGo 的搜索更「智能」——它知道哪些地方值得深入，哪些可以快速略過。

---

動畫對應

本文涉及的核心概念與動畫編號：

編號	概念	物理/數學對應
🎬 C5	MCTS 四階段	樹搜索

---

總結

MCTS 與神經網路的結合是 AlphaGo 的核心創新。我們學習了：

1. 傳統 MCTS：Selection、Expansion、Simulation、Backpropagation
2. 神經網路改進：Policy Network 引導展開、Value Network 替代 Rollout
3. 搜索過程：PUCT 選擇、批次評估、反向傳播
4. 資源分配：模擬次數、時間管理、並行搜索
5. 溫度選擇：訓練與比賽的不同策略
6. 實作細節：記憶體管理、樹重用、快取

下一篇，我們將深入探討 PUCT 公式的數學細節。

---

延伸閱讀

• 下一篇：PUCT 公式詳解 — MCTS 選擇的數學原理
• 上一篇：自我對弈 — 自我對弈的機制與效果
• 相關：Policy Network 詳解 — 策略網路的架構

---

參考資料

1. Silver, D., et al. (2016). "Mastering the game of Go with deep neural networks and tree search." Nature, 529, 484-489.
2. Silver, D., et al. (2017). "Mastering the game of Go without human knowledge." Nature, 550, 354-359.
3. Coulom, R. (2006). "Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search." Computers and Games.
4. Kocsis, L., & Szepesvári, C. (2006). "Bandit based Monte-Carlo Planning." ECML.
5. Browne, C., et al. (2012). "A Survey of Monte Carlo Tree Search Methods." IEEE TCIAIG.
6. Rosin, C. D. (2011). "Multi-armed bandits with episode context." Annals of Mathematics and Artificial Intelligence.

---

📌 重點摘要

本文重點：

• MCTS 四階段（選擇、展開、評估、反向傳播）與神經網路結合，形成直覺與推理的完美整合
• Policy Network 提供先驗機率引導搜索方向，Value Network 直接評估局面取代隨機模擬
• 搜索可以修正神經網路盲點，純 Policy + Value + MCTS 比純神經網路提升約 1500 Elo

常見問題

為什麼需要 MCTS，不能只用神經網路嗎？

神經網路提供快速直覺但可能有盲點，MCTS 提供深入推理來修正錯誤。實驗顯示純神經網路約 3000 Elo，加入 MCTS 後提升到 4500 Elo，搜索對戰術計算和罕見局面特別有價值。

PUCT 公式如何平衡探索與利用？

PUCT 結合平均價值 Q(s,a) 和探索加成 U(s,a)。Q 值偏好已知好的走法（利用），U 值偏好訪問次數少的走法（探索）。Policy Network 的先驗機率進一步引導探索方向。

AlphaGo Zero 為什麼能移除隨機模擬？

因為 Value Network 的精度已足夠高，直接評估比隨機模擬更準確且更快。這簡化了系統架構，也說明神經網路品質的提升讓搜索次數從 100,000 降到 1,600 仍能更強。