AlphaGo原理淺析

論文筆記：Mastering the game of Go with deep neural networks and tree search

背景：完全資訊博弈與MCTS算法

要完全弄清AlphaGo背後的原理，首先需要了解一下AI在博弈遊戲中常用到的蒙特卡洛樹搜尋算法——MCTS。

在一個完全資訊下的博弈遊戲中，如果所有參與者都采取最優政策，那麼對于遊戲中的任意一個局面$s$，總有一個确定性的估值函數$v^*(s)$可以直接計算出最終的博弈結果。理論上，我們可以通過建構一棵博弈樹，遞歸地求解出$v^*(s)$。這就是Minimax算法。然而在有些問題中，這棵搜尋樹往往十分巨大（例如在圍棋遊戲中達到了$250^{150}$的搜尋空間），以至于窮舉的算法并不可行。

有兩種政策可以有效地降低搜尋空間的複雜度：1. 通過一個evalutaion function對目前局面進行價值的評估以降低搜尋的深度；2. 剪枝以降低搜尋的寬度。然而，這些政策都需要引入一些先驗的知識。

于是，人們提出了蒙特卡洛樹搜尋（MCTS）算法。MCTS是一類通用博弈算法——理論上，它不需要任何有關博弈的先驗知識。

想象一下，你站在一堆老虎機面前，每一台老虎機的reward都服從一個随機的機率分布。然而，一開始，你對這些機率分布一無所知。你的目标是尋找一種玩老虎機的政策，使得在整個遊戲的過程中你能獲得盡可能多的reward。很明顯，你的政策需要能夠在嘗試盡可能多的老虎機（explore）與選擇已知回報最多的老虎機（exploit）之間尋求一種平衡。

一種叫做UCB1的政策可以滿足這種需求。該政策為每台老虎機構造了一個關于reward的置信區間：

\[x_i\pm\sqrt{\frac{2\ln{n}}{n_i}}

其中，$x_i$是對第$i$台老虎機統計出來的平均回報；$n$是試驗的總次數；$n_i$是在第$i$台老虎機上試驗的次數。你要做的，就是在每一輪試驗中，選擇置信上限最大對應的那台老虎機。顯然，這個政策平衡了explore與exploit。你的每一次試驗，都會使被選中的那台老虎機的置信區間變窄，而使其他未被選中的老虎機的置信差別變寬——變相提升了這些老虎機在下一輪試驗中被選中的機率。

蒙特卡洛樹搜尋（MCTS）就是在UCB1基礎上發展出來的一種解決多輪序貫博弈問題的政策。它包含四個步驟：

Selection。從根節點狀态出發，疊代地使用UCB1算法選擇最優政策，直到碰到一個葉子節點。葉子節點是搜尋樹中存在至少一個子節點從未被通路過的狀态節點。
Expansion。對葉子節點進行擴充。選擇其一個從未通路過的子節點加入目前的搜尋樹。
Simulation。從2中的新節點出發，進行Monto Carlo模拟，直到博弈結束。
Back-propagation。更新博弈樹中所有節點的狀态。進入下一輪的選擇和模拟。

可以看出，通過Selection步驟，MCTS算法降低了搜尋的寬度；而通過Simulation步驟，MCTS算法又進一步降低了搜尋的深度。是以，MCTS算法是一類極為高效地解決複雜博弈問題的搜尋政策。

關于MCTS算法更多詳細的介紹，可參見部落格：Introduction to Monte Carlo Tree Search

AlphaGo的基本原理

圍棋是一類完全資訊的博弈遊戲。然而，其龐大的搜尋空間，以及局面棋勢的複雜度，使得傳統的剪枝搜尋算法在圍棋面前都望而卻步。在AlphaGo出現之前，MCTS算法算是一類比較有效的算法。它通過重複性地模拟兩個players的對弈結果，給出對局面$s$的一個估值$v(s)$（Monte Carlo rollouts）；并選擇估值最高的子節點作為目前的政策（policy）。基于MCTS的圍棋博弈程式已經達到了業餘愛好者的水準。

然而，傳統的MCTS算法的局限性在于，它的估值函數或是政策函數都是一些局面特征的淺層組合，往往很難對一個棋局有一個較為精準的判斷。為此，AlphaGo的作者訓練了兩個卷積神經網絡來幫助MCTS算法制定政策：用于評估局面的value network，和用于決策的policy network。（後面會看到，這兩個網絡的主要差別是在輸出層：前者是一個标量；後者則對應着棋盤上的一個機率分布。）

首先，Huang等人利用人類之間的博弈資料訓練了兩個有監督學習的policy network：$p_\sigma$（SL policy network）和$p_\pi$（fast rollout policy network）。後者用于在MCTS的rollouts中快速地選擇政策。接下來，他們在$p_\sigma$的基礎上通過自我對弈訓練了一個強化學習版本的policy network：$p_\rho$（RL policy network）。與用于預測人類行為的$p_\sigma$不同，$p_\rho$的訓練目标被設定為最大化博弈收益（即赢棋）所對應的政策。最後，在自我對弈生成的資料集上，Huang等人又訓練了一個value network：$v_\theta$，用于對目前棋局的赢家做一個快速的預估。

是以，用一句話簡單概括一下AlphaGo的基本原理：在MCTS的架構下引入兩個卷積神經網絡policy network和value network以改進純随機的Monte Carlo模拟，并借助supervised learning和reinforcement learning訓練這兩個網絡。

接下來将對AlphaGo的細節進行展開讨論。

有監督學習的Policy Networks

Huang等人首先訓練了一個有監督的Policy Network用來模拟人類專家的走子。SL policy network是一個卷積神經網絡；其輸出層是一個Softmax分類器，用來計算在給定的棋面狀态$s$下每一個位置的落子機率$p_\sigma(a|s)$。對一個棋面狀态$s$的描述如下：

（這裡的Features對應着卷積神經網絡裡的Channels。）

經過人類高手三千萬步圍棋走法的訓練後，SL policy network模拟人類落子的準确率已經達到了57%；相應地，網絡的棋力也得到大大的提升。但是，如果直接用這個網絡與人類高手，甚至是MCTS的博弈程式進行對弈，依然是輸面居多。而且，這個網絡的走子太慢了！平均每步$3ms$的響應時間，使得這個網絡很難被直接用于MCTS的rollout中進行政策的随機。是以，Huang等人通過提取一些pattern features又訓練了一個更快速（響應時間達到了$2\mu s$）但準确率有所降低（24.2%）的rollout policy network： $p_\pi$。

強化學習的Policy Networks

接下來，為了進一步提高policy network的對弈能力，Huang等人又采用一種policy gradient reinforcement learning的技術，訓練了一個RL policy network：$p_\rho$。這個網絡的結構與SL policy network的網絡結構相同，依然是一個輸出為給定狀态下落子機率的卷積神經網絡。網絡的參數被初始化為$p_\sigma$的參數；接下來，通過不斷地自我對弈（與曆史版本），網絡的權重向着收益最大化的方向進化。此時，網絡的學習目标不再是模拟人類的走法，而是更為終極的目标：赢棋。

具體來說，我們定義了一個reward function $r(s_t)$：對于非終止的時間步$t<T$，總有$r(s_t)=0$。每一步的收益$z(t)$被定義為$\pm r(s_T)$：即對目前玩家而言對弈的最終結果（$+1$代表赢棋；$-1$代表輸棋）。網絡的權重通過随機梯度上升法進行調整：

\[\Delta\rho\propto\frac{\partial\log{p_\rho(a_t|s_t)}}{\partial\rho}z_t

通過這種方式訓練出來的RL policy network，在與SL policy network對弈時已有80%的赢面。即便是與依賴Monte Carlo搜尋的圍棋博弈程式相比，不依賴任何搜尋的RL policy network，也已經達到了85%的赢面。

強化學習的Value Networks

最後，Huang等人又開始尋求一個能快速預估棋面價值（棋勢）的Value Network。一個棋面的價值函數$v^p(s)$，被定義為在給定的一組對弈政策$p$的情況下，從狀态$s$出發，最終的期望收益（也即赢棋的機率）：

\[v^p(s)=E[z_t|s_t=s,a_{t...T}\in p]

顯然，理想情況下，我們想知道的是在雙方均采用最優政策的條件下得到的最優期望收益$v^*(s)$。然而，我們并不知道什麼才是最優的政策。是以，在實際應用中，Huang等人采用了目前最強的政策函數$p_\rho$（RL policy network ）來計算一個棋面的價值$v^{p_\rho}(s)$，并訓練了一個value network $v_\theta(s)$來拟合這個價值函數：$v_\theta(s) \approx v^{p_\rho}(s) \approx v^*(s)$。

Value Network的網絡結構與前面的Policy Network類似，也是一個卷積神經網絡，隻是輸出層變成了一個單神經元的标量。我們可以通過構造一組$(s,z)$的訓練資料，并用随機梯度下降法最小化網絡的輸出$v_\theta(s)$與目标收益$z$的均方差，來調整網絡的參數：

\[\Delta\theta\propto\frac{\partial{v_\theta(s)}}{\partial\theta}(z-v_\theta(s))

在構造訓練資料時有一些技巧。如果我們從人類對弈的完整棋局中抽取足夠數量的訓練資料，很容易出現過拟合的問題。這是因為，在同一輪棋局中的兩個棋面的相關性很強（往往隻相差幾個棋子）；此時，網絡很容易記住這些棋面的最終結果，而對新棋面的泛化能力很弱。為了解決這個問題，Huang等人再次祭出強化學習的大殺器：通過RL policy network的自我對弈，産生了三千萬個從不同棋局中提取出來的棋面－收益組合的訓練資料。基于這份資料訓練出來的Value Network，在對人類對弈結果的預測中，已經遠遠超過了使用fast rollout policy network的MCTS的準确率；即便是與使用RL policy network的MCTS相比，也已是不遑多讓（而Value Network的計算效率更高）。

整合

到這裡，我們手頭上已經有一個牛逼但是巨慢的SL policy network；有一個不那麼牛逼但是很快的fast policy network；有一個一心隻想着如何赢棋的RL policy network；還有一個能一眼洞穿棋局的value network。那麼，将這些networks放在一起互相補足，會得到什麼呢？

答案就是AlphaGo。而把這些networks整合在一起的架構，就是MCTS算法。

與經典的MCTS算法類似，APV-MCTS（asynchronous policy and value MCTS）的每一輪模拟也包含四個步驟：

Selection：APV-MCTS搜尋樹中的每條連邊$(s,a)$都包含三個狀态：決策收益$Q(s,a)$，通路次數$N(s,a)$，和一個先驗機率$P(s,a)$。這三個狀态共同決定了對一個節點下行為的選擇：

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

其中，$u(s,a)\propto\frac{P(s,a)}{1+N(s,a)}$

2. Expansion：步驟1中的selection終止于葉子節點。此時，要對葉子節點進行擴充。這裡采用SL policy network $p_\sigma$計算出葉子節點上每個行為的機率，并作為先驗機率$P(s_L,a)$存儲下來。

3. Evaluation。使用value network $v_\theta(s)$和fast rollout policy network $p_\pi$模拟得到的博弈結果對目前通路到的葉子節點進行估值：$$V(s_L)=(1-\lambda)v_\theta(s_L)+\lambda z_L$$

4. Backup。更新這一輪模拟中所有通路到的路徑的狀态：

\[N(s,a)=\sum_{i=1}^n{1(s,a,i)}

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

其中，$n$是模拟的總次數；$1(s,a,i)$标示第$i$輪模拟中是否經過邊$(s,a)$；$s_L^i$是第$i$輪模拟中通路到的葉子節點。

下圖展示了一輪模拟的動态過程。

模拟結束後，算法會選擇通路次數$N(s,a)$最大的政策$a$作為目前的走子政策。

值得注意的是，在整個模拟的過程中，我們見到了SL policy network（用于Expansion中先驗機率的計算）；見到了fast rollout policy network（用于Evaluation中的快速走子）；見到了value network（用于Evaluation中對棋勢的預估）。等等，RL policy network去哪了？為什麼不用RL policy network替代SL policy network？明明RL policy network有着更強的棋力啊（85%的赢面）？

這是因為，與RL policy network相比，由人類專家走法訓練出來的SL policy network在政策上的多樣性更強；是以更适用于MCTS中的搜尋。但是，用RL policy network的自我對弈結果訓練出來的value network的泛化能力就要比SL policy network訓練出來的value network要強得多了。

結語

回顧一下，我們發現AlphaGo本質上是CNN、RL、MCTS三者相結合的産物。其中，MCTS是AlphaGo的骨骼，支撐起了整個算法的架構；CNN是AlphaGo的眼睛和大腦，在複雜的棋局面前尋找盡可能優的政策；RL是AlphaGo的血液，源源不斷地提供新鮮的訓練資料。三者相輔相成，最終4:1戰勝了人類圍棋世界冠軍李世石。其實還有很多細節我沒有詳細的展開，包括如何在分布式的機器上更高效地訓練；如何更新MCTS中的權重等等。然而，其背後的基本原理差不多就是這些了。