讓我們建立 AlphaZero

本文是對於 Sunrise：從頭理解 AlphaZero，MCTS，Self-Play，UCB 等文章、視頻教程和代碼實現的消化與理解。
本文將從 AlphaGo 的設計原理出發，通過深入理解 MCTS 和 Self-Play 這兩個核心機制，逐步揭示如何構建一個能超越人類的 AI 五子棋（Gomoku）系統。

AlphaGo：從模仿到超越#

AlphaGo 的進化路徑#

圍棋的可能局面數超過宇宙中的原子數量，使得傳統窮舉搜索方法完全失效。AlphaGo 通過一個分階段的方法解決這個問題：先學習人類知識，然後通過 self-play 不斷進化。
Pasted image 20241116201853
這個進化過程可以分為三層：

模仿人類高手
自我博弈提升
學習評估局勢

核心組件#

Pasted image 20241115170343

快速走子策略（Rollout Policy）#

最左邊的一個輕量級策略網絡，用於快速評估，準確性較低但計算效率高。

SL 策略網絡#

監督學習策略網絡 $P_{\sigma}$ 通過模仿人類棋譜學習下棋：

輸入：棋盤狀態
輸出：模仿人類專家的下一步走法概率分布
訓練數據：16 萬場對局，約 3000 萬個落子步驟

RL 策略網絡#

類似當你棋藝達到一定水平時，開始自己復盤，自我對戰，發現新的戰術和更深的策略。RL 網絡 $P_{\rho}$ 從 SL 網絡初始化，該網絡已經遠超人類，可以找到許多人類未曾發現的強力策略。

這個階段生成了大量 self-play 的數據，輸入依然是棋盤狀態，輸出是通過強化學習改進的走棋策略。
與歷史版本的策略網絡 $p_\pi$ 進行 self-play，網絡通過 “贏棋” 信號來調整參數，通過 Policy Gradiant 強化那些導致勝利的走法。：

\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 算法中，模擬階段 (Simulation) 的作用是通過快速 rollout 策略從葉子節點（擴展的新節點）進行隨機對弈，直至遊戲結束，然後根據對弈的勝負得到一個回報。這個回報被傳遞回搜索樹中的節點，用於更新這些節點的值估計（即 $Q(s, a)$ ）。

這樣的實現簡單直接，但是 rollout 策略通常是隨機或簡單的規則，模擬質量可能較差。且只能給出短期信息，無法很好地結合全局的戰略評估。

而 AlphaGo 在模擬階段結合了 Value Network $v_\theta$ 和 rollout 策略。Value Network 提供了更高效的葉子節點估計和全局能力評估，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 值更新，即執行 a 到節點 $s_t$ 的長期預期回報：

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 改進：
- 使用神經網絡指導搜索
- Policy Network 提了探索方向的先驗概率，Value Network 提升了葉子節点评估的準確性。
- 這樣結合價值網絡和 rollout 的評估，不僅減少了搜索寬度和深度，還顯著提高了整體性能。
- 高效的探索 - 利用平衡

這種設計使 AlphaGo 能在龐大的搜索空間中找到高效的解決方案，最終超越人類水平。

啟發式搜索與 MCTS#

MCTS 就像是一個不斷進化的探索者，在決策樹中尋找最佳路徑。

核心思想#

MCTS 的本質是什麼？簡單來說，它是一個 "邊玩邊學" 的過程。想像你在玩一盤全新的棋類遊戲：

開始時，你會嘗試各種可能的走法（探索）
慢慢發現某些走法效果更好（利用）
在探索新策略和利用已知好策略之間取得平衡

這正是 MCTS 所做的，只不過它用數學的方式來系統化這個過程。其是一種 rollout 算法，通過累積蒙特卡洛模擬的價值估計來引導策略選擇。

算法流程#

Monte Carlo Tree Search - YouTube這個老師對於 MCTS 的流程講的很好。

MCTS 的優雅之處在於它的四個簡單但強大的步驟，這裡我用 A、B 兩種理解方式來介紹：

選擇 (Selection)
- A：你知道小孩子是怎麼學習的嗎？他們總是在已知和未知之間徘徊。MCTS 也是如此：從根節點開始，使用 UCB (Upper Confidence Bound) 公式來權衡是選擇已知的好路徑，還是去探索新的可能。
- B：從根節點出發，依據特定策略從當前節點中選擇一個後續節點。該策略通常基於樹的搜索歷史，選取最具潛力的路徑。例如，我們在每個節點依據當前的策略 $\pi(s)$ 執行動作 $a$ ，以平衡探索與利用，逐步深入。
擴展 (Expansion)
- A：就像探險家在地圖上開闢新的區域，當我們到達一個葉節點時，我們會向下擴展，創建新的可能性。
- B：當選中的節點尚有未探索的子節點時，我們在此節點下依據可行動作集擴展新節點。這一過程的目的是增加決策樹的廣度，逐步生成可能的決策路徑。通過這一擴展操作，我們確保搜索涵蓋更多可能的 state action pair $(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 天時的情況：

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):
    # 確保每家餐廳至少訪問一次
    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 機制，自動在探索新策略和利用已知好策略之間取得平衡。

Nagi-ovo