AlphaGo Zero是如何工作的？——AlphaGo Zero背後的強化學習算法原理

  Deepmind公司的AlphaGo算法是第一個打敗人類選手的圍棋程式。2016年三月，打敗李世石的是AlphaGo Lee，一個靠大量人類圍棋專家的棋譜進行監督學習和自對弈強化學習進行訓練的AI程式。不久之後，deepmind的新論文展示了不同于之前AlphaGo的全新網絡結構——它僅僅用了三天的自對弈強化學習而無需人類的下棋經驗就以100-0的戰績打敗了AlphaGo。它就是大名鼎鼎的AlphaGo Zero。這篇文章将介紹AlphaGo Zero背後的算法原理。

其他資料可以參考我的另外兩篇

一張圖讀懂AlphaGo Zero背後的強化學習算法原理

AlphaGo Zero強化學習簡易教程

蒙特卡洛樹搜尋

  蒙特卡洛樹搜尋（Monte Carlo Tree Search）可以說是棋類遊戲機器人的入門級算法了。它适合處理離散的、确定性的、完全資訊的（perfect information，也就是雙方都能看到完全的棋局狀态）棋類遊戲。當一個機器人開始下棋，最簡單的方法就是把所有可能的結果全部嘗試一遍，這樣就能得到對手所有可能的應對措施，以及下一步應該走哪等等。但是像圍棋這樣的遊戲，動作搜尋空間将随着棋局的進行變得越來越龐大，以至于暴力窮舉變得極不現實。而蒙特卡洛樹搜尋可以有選擇地嘗試它覺得不錯的可選動作，如此就将大部分算力集中于最有可能性的走子方案上，使搜尋變得高效。

  我們來具體地看一下MCTS的工作原理，以一字棋(tic-tac-toe)為例來說明。假設遊戲的初始狀态是 s 0 s_0 s0​，輪到程式走子，走子的可選方案是一個動作集合 A A A。蒙特卡洛搜尋樹初始化為一個隻含有單結點 s 0 s_0 s0​的樹。下面，搜尋算法對狀态 s 0 s_0 s0​下的每一個可能的走子方案 a ∈ A a\in A a∈A都嘗試一次，建立了五個子結點，分别是 s 0 , 1 , s 0 , 2 , s 0 , 3 , s 0 , 4 , s 0 , 5 s_{0,1},s_{0,2},s_{0,3},s_{0,4},s_{0,5} s0,1​,s0,2​,s0,3​,s0,4​,s0,5​。

接着從每個子結點出發，采用随機走子政策完成目前棋局（rollout），确定 s 0 → s 0 , i s_0 \rightarrow s_{0,i} s0​→s0,i​的動作價值。若MCTS算法一方赢得棋局，這個子結點記為 + 1 +1 +1，輸掉為 − 1 -1 −1，平局記為 0 0 0。（多說一句，如果從 s 0 , i s_{0,i} s0,i​出發，經過足夠多次simulation，則累計回報的平均值就可以評價這個狀态 s 0 , i s_{0,i} s0,i​的好壞了）

  我們假設從 s 0 , 1 s_{0,1} s0,1​結點出發，赢得棋局，得到價值函數的估計值 + 1 +1 +1，但是這個值并不代表下一次走這個方案還會赢，它取決于從 s 0 , 1 s_{0,1} s0,1​出發的rollout采取什麼樣的走子政策完成棋局。從子結點出發，可以采用完全随機的、非智能的走子政策，也可以采取更優秀的随機政策，也可以從 s 0 , 1 s_{0,1} s0,1​直接估計價值函數（比如利用神經網絡）。

  上圖我們畫出來從 s 0 s_0 s0​根結點出發，探索了五個子結點的情況。每個結點存儲兩個變量：

• N N N表示通路該結點 s 0 , i s_{0,i} s0,i​或該結點的子結點 s 0 , i , j s_{0,i,j} s0,i,j​的次數。也就是說，在該結點 s 0 , i s_{0,i} s0,i​的子結點執行simulation的次數也要在資訊回傳過程中加到 N s 0 , i N_{s_{0,i}} Ns0,i​​上，我們之後會講到回傳是怎樣進行的。
• W W W代表累計回報值，将從該結點出發的所有simulation的回報值加起來就是 W W W。

  當探索完子結點，就需要把子結點記錄的資訊回傳給它的上級結點。如下圖所示，子結點 { s 0 , i , ∣   i = 1 , ⋯   , 5 } \{s_{0,i},\mid \ i=1,\cdots,5\} {s0,i​,∣ i=1,⋯,5}分别探索一次，獲得回報分别是 { + 1 , 0 , − 1 , − 1 , 0 } \{ +1,0,-1,-1,0 \} {+1,0,−1,−1,0}，則上級節點 s 0 s_0 s0​的通路次數加5，累計回報價值為 1 + 0 − 1 − 1 + 0 = − 1 1+0-1-1+0=-1 1+0−1−1+0=−1。

  蒙特卡洛樹搜尋的基本流程就是這樣：1)選擇一個結點，2)以上述方式擴充該結點——執行可能的動作，并将遊戲進行到底以獲得最終分數即回報價值，3)将該結點的資訊回傳給它的上級，并不斷地重複這一過程。但是MCTS不會擴充所有可能的子結點，這樣做的計算代價非常之大。是以搜尋算法在選擇哪個結點向下擴充的時候會平衡兩方面：選擇目前較優的結點向下拓展（W值高）和選擇較少探索過的結點（N值小），如果了解強化學習基本概念，就會發現這其實就是在平衡探索exploration和利用exploitation之間的關系。

  MCTS算法怎樣選擇子結點呢？假設目前結點共有 M M M個子結點可供拓展，搜尋樹會選擇具有最高上限置信區間（Upper Confidence Bound applied to Tree，UCT）的子結點：

U i = W i N i + c ln ⁡ N p N i ,   i = 1 , ⋯   , M U_i=\frac{W_i}{N_i}+c\sqrt{\frac{\ln N_p}{N_i}},\ i=1,\cdots,M Ui​=Ni​Wi​​+cNi​lnNp​​

​, i=1,⋯,M

式中， W i W_i Wi​是第 i i i個子結點的累計回報值， N i N_i Ni​是第 i i i個子結點的通路次數， N p N_p Np​是父節點的通路次數，其值等于所有子結點通路次數 N i N_i Ni​之和。參數 c c c是控制探索和利用的超參數： c c c值小，則偏重于選擇具有高平均回報值的子結點； c c c值大，則算法偏向于選擇通路次數少的子結點。當取 c = 1 c=1 c=1的時候，上圖的 U U U值計算如下：

  五個子結點中，第一個結點的 U U U值最高，是以我們選擇第一個結點 s 0 , 1 s_{0,1} s0,1​向下拓展。并将 s 0 , 1 s_{0,1} s0,1​結點之下的模拟結果反向傳播至樹的上層。

  這裡要注意，我們做rollout得到的 W W W值都是在反映 × \times ×棋的輸赢，在選擇結點時，如果輪到 ∘ \circ ∘棋，就需要将 W W W值取反，因為零和遊戲的雙方看待棋局的好壞是截然相反的。

  在時間沒有溢出的情況下，MCTS算法不斷地在 s 0 s_0 s0​的子結點下進行rollout模拟。最終搜尋樹被完全拓展開，理想狀态下，搜尋樹探索了所有可能的動作（導緻的子結點），于是就能反映出最值得采取的動作是什麼。假設搜尋了足夠多次後，樹的狀态如下，則應該選擇平均回報值最大(51/106=0.48)的第一個子結點，在那個位置上真實地下一個棋子，棋局的狀态也就随之轉移到 s 0 , 1 s_{0,1} s0,1​，這時我們完成了一步棋的搜尋，再走下一步時，就以 s 0 , 1 s_{0,1} s0,1​為根節點建立搜尋樹，搜尋足夠次數并選擇最優。

使用專家政策提升搜尋效率

  圍棋和象棋這樣的棋類遊戲在進行樹搜尋時有着非常龐大的分支，在某個狀态下可執行的動作也非常多，是以搜尋起來非常困難。據計算，在象棋中大約有 1 0 46 10^{46} 1046種狀态，而一個 19 × 19 19\times 19 19×19的圍棋棋盤上大約有 1 0 170 10^{170} 10170種狀态，相比之下，一字棋隻有5478個不同棋盤狀态。

  用普通的MCTS算法進行政策評估Policy Evaluation——或者叫走子評估Move Evaluation（即第一部分所述内容）——還是不夠高效，我們需要搜尋樹把搜尋精力盡量集中在更有價值的走子方案上。

  我們假設有一個專家政策 π \pi π，對于一個給定狀态 s s s，政策 π \pi π能給出專業水準的選手可能的走子方案。以一字棋為例：如下圖所示， P i = π ( a i ∣ s 0 ) P_i=\pi(a_i\mid s_0) Pi​=π(ai​∣s0​)是在狀态 s 0 s_0 s0​下采取第 i i i個動作 a i a_i ai​的條件機率。

  如果這個專家政策足夠強大，我們就可以直接根據政策 π \pi π的指導走下一步棋，或者說，選擇 arg ⁡ m a x a i { P i = π ( a i ∣ s ) } \arg max_{a_i}\{ P_i=\pi(a_i\mid s) \} argmaxai​​{Pi​=π(ai​∣s)}作為下一步棋。但是，要得到專家政策 π \pi π也是蠻困難的事，要确定一個政策是最優的也幾乎是不可能的。

  幸運的是，我們可以用一種改進的MCTS算法逐漸地優化一個政策。改進MCTS算法會在搜尋樹的每個結點額外存儲動作條件機率，也就是上述 P i P_i Pi​，機率值将在選擇結點時起到作用。是以，Deepmind論文中采用的機率化的上限置信區間公式為

U i = W i N i + c ⋅ P i ln ⁡ N p 1 + N i U_i=\frac{W_i}{N_i}+c\cdot P_i\sqrt{\frac{\ln N_p}{1+N_i}} Ui​=Ni​Wi​​+c⋅Pi​1+Ni​lnNp​​

​

  與之前的UCT公式一樣， U U U值在高回報值和低通路次數之間取平衡。但是在上式中，探索這一項還受到機率值的影響，也就是說，如果一個子結點沒有或很少通路到，而且政策 π \pi π認為采取動作（從父結點轉移到該子結點）的機率值較高，那它則更有可能被選中。如果專家政策 π \pi π下棋水準很高，那麼搜尋樹就可以高效地估計目前棋盤狀态。但如果這個專家政策水準不太高，那麼搜尋樹對狀态的估計就有偏差了。不管怎樣，隻要模拟的次數足夠多，每個結點的通路次數足夠多，結點的 U U U值就主要受輸赢比率 W i N i \frac{W_i}{N_i} Ni​Wi​​的控制，這和上一個公式是一樣的。

提高 值估計 的效率

  在上文說到，搜尋樹對每個結點進行 W W W值估計的時候，采用的方法是：從該結點出發，采用随機走子政策，完成一盤棋局（這個方法叫rollout），赢了記1分，輸了記-1分，平局記0分。這個完全随機的方法看起來并不高效，也不準确。我們的第二個改進措施就從 随機rollout 着手。

  第一個方案是采用之前所述的專家政策 π ( a ∣ s ) \pi(a\mid s) π(a∣s)，去指導rollout的走子。即走子政策不再完全随機。如果 π \pi π比較優秀，rollout就能反應更多的真實情況，正确的估計狀态的好壞；如果 π \pi π水準不高，在它的指導下從狀态 s s s出發進行的模拟也就很難反映 s s s的好壞情況。

  第二個方案是不直接進行rollout，而是采用值估計函數 W ^ ( s ) \hat{W}(s) W^(s)直接估計state value，不再将棋局從狀态 s s s下完。 W ^ ( s ) \hat{W}(s) W^(s)采取目前狀态 s s s作為輸入，傳回一個 [ − 1 , 1 ] [-1,1] [−1,1]的實數，反映了目前狀态的好壞。如果 W ^ ( s ) \hat{W}(s) W^(s)對真實值的估計能力不錯，那我們就可以在不執行rollout的情況下保持預測精度，提高值估計value estimate的效率。

  事實上，這兩個方法可以同時運用，比如使用expert policy先模拟幾個回合，到達狀态 s ′ s' s′，而後再用 W ^ ( s ′ ) \hat{W}(s') W^(s′)得到狀态 s s s的值估計。但是這兩個方法都存在一個問題沒有解決，那就是如何得到一個優秀的政策或是值估計函數？或者說，有沒有一個算法能夠對政策 π \pi π或函數 W ^ ( s ) \hat{W}(s) W^(s)進行訓練呢？

AlphaZero中的神經網絡

  我們已經知道，AlphaZero采用改進的MCTS算法，通過自對弈的方式進行學習，可以一步一步地得到越來越好的政策 π \pi π和值估計函數 W ^ \hat{W} W^。在AlphaZero中，政策和值估計函數都是以深度神經網絡的形式存在的。實際上，為了提高效率，AlphaZero采用了一個神經網絡，同時給出下一步棋的動作機率和目前狀态的價值。 p \bm{p} p形如 [ 0 , 0 , 0.1 , 0 , 0.3 , 0.4 , 0.2 , 0 ] [0,0,0.1,0,0.3,0.4,0.2,0] [0,0,0.1,0,0.3,0.4,0.2,0]。

f ( s ) → [ p , W ] f(s)\rightarrow[{\rm \bm{p}} ,\bm{W}] f(s)→[p,W]

值得注意的是，神經網絡将最後8個回合的棋盤狀态拆成黑白雙方（ 8 × 2 = 16 8\times2=16 8×2=16個 19 × 19 19\times19 19×19的棋局矩陣）和一個 19 × 19 19\times19 19×19的全0或全1矩陣（訓示輪到黑白哪方）作為輸入，輸入的次元是 19 × 19 × 17 19\times19\times17 19×19×17。

  估計結點 s 0 s_0 s0​的價值 W W W的rollout方法被神經網絡 f ( s ) f(s) f(s)代替了。首先，初始化 s 0 s_0 s0​的每個子結點的 N = 0 N=0 N=0和 W = 0 W=0 W=0。其次，走子機率 P P P由神經網絡進行預測，如下圖所示。五個可選動作的機率分别是 0.9 , 0.02 , 0.03 , 0.01 , 0.04 0.9,0.02,0.03,0.01,0.04 0.9,0.02,0.03,0.01,0.04。然後，狀态 s 0 s_0 s0​的 W W W值也由 f ( s 0 ) f(s_0) f(s0​)得到。最後，根據 U U U值計算公式選擇子結點向下擴充。結點資訊的回傳機制和之前一樣。

  随後，搜尋樹開始下一輪的子節點選擇和資訊回傳。

  我們說完了AlphaZero是怎麼引入神經網絡來完成前述的MCTS算法的。下面就來說一說AlphaZero的神經網絡是怎麼訓練的。

  AlphaZero的核心思想就是一個不斷疊代、不斷優化的神經網絡。并且，利用MCTS算法進行的棋局走子資料也會作為網絡訓練的資料而收集起來。

  具體的訓練是這樣的：網絡的政策預測部分，狀态 s 0 s_0 s0​下，網絡的輸出 P s 0 ^ \hat{P_{s_0}} Ps0​​^​被要求拟合MCTS算法經過搜尋得到的機率 π s 0 \pi_{s_0} πs0​​，即

π i = N i 1 / τ \pi_i=N^{1/\tau}_i πi​=Ni1/τ​

τ \tau τ是溫度系數， τ → 0 \tau\rightarrow0 τ→0表示選擇狀态 s 0 s_0 s0​的通路次數最多（best move）的子結點， τ → ∞ \tau\rightarrow \infin τ→∞則表示政策 π \pi π趨近于完全随機。

  值函數估計部分的訓練目标是逼近真實的棋局結果 Z Z Z（輸/赢/平），即從狀态 s 0 s_0 s0​預測這盤棋的輸赢可能性，可以認為這是一個回歸問題。

  加入正則化項的總損失函數如下，式中 ( W − Z ) 2 (W-Z)^2 (W−Z)2是值估計的損失， π T ln ⁡ P \pi^T\ln {\rm P} πTlnP是政策預測的交叉熵損失， λ ∥ θ ∥ 2 2 \lambda \| \theta \|^2_2 λ∥θ∥22​是網絡參數 θ \theta θ的正則化項。

( W − Z ) 2 + π T ln ⁡ P + λ ∥ θ ∥ 2 2 (W-Z)^2+\pi^T\ln {\rm P}+\lambda \| \theta \|^2_2 (W−Z)2+πTlnP+λ∥θ∥22​

  在自對弈(self-play)階段中，目前神經網絡已經完成參數的更新，網絡參數被固定住。（如果是第一次疊代，網絡的參數為随機初始化。）目前網絡被用來指導MCTS算法進行子結點的選擇和擴充、結點的 W W W值估計和走子政策的預測等。具體來說，在每一局棋中，每走一步都經過若幹次樹搜尋，得到政策 π ( a ∣ s ) \pi(a|s) π(a∣s)和棋局輸赢資訊 Z Z Z，這些資料以 ( s t , a t , r t ) (s_t,a_t,r_t) (st​,at​,rt​)的形式收集起來，用于在網絡訓練階段，做損失函數的随機梯度下降。