遲蹭一個熱點：AlphaGo Zero 筆記

AlphaGo Zero [1] 已經出來一段時間了。本來 AlphaGo Zero 一出來就應該寫科普的，但自己實在懶。等到現在才更新。

AlphaGo Zero 最大的亮點是：完全沒有利用人類知識，就能夠獲得比之前版本更強大的棋力。主要的做法是: 1) 利用蒙特卡洛樹搜索建立一個模型提升器，2) 在自我對弈過程中，利用提升器指導模型提升，模型提升又進一步提高了提升器的能力。

1. 蒙特卡洛樹搜索簡介

蒙特卡洛樹搜索 (Monte Carlo Tree Search, MCTS) 是一種樹型搜索技術，具有如下所示的樹型結構。

樹中每一個節點 s 代表了一個圍棋盤面，並帶有兩個數字。一個是訪問次數N(s)，另一個質量度Q(s)。訪問次數 N(s)表示在搜索中節點被訪問的次數。面對一個盤面，MCTS 會進行重複搜索，所以一個節點可能會被反覆訪問，這個下面細說。質量度Q(s)表示這個節點下 AlphaGo 的優勢程度，其計算公式如下所示。

這個公式的意思是：1）對於非葉子節點，質量度等於該節點所有樹中已有子節點的質量度均值。2）對於葉子節點，質量度跟價值網路估計的獲勝概率vθ(sL)有關，還跟快速走子模擬後續比賽得到的勝負結果zL有關。葉子節點的質量度等於這兩者的加權混合，其中混合參數λ介於0和1之間。

有了 MCTS 的結構，我們就可以繼續介紹 MCTS 怎麼做搜索的。當對手落了一子，AlphaGo 迅速讀入當前盤面，將之當作搜索的根節點，展開搜索。MCTS 搜索的流程如下圖所示，一共分為四個步驟：

1. 選擇

從根節點 R 開始，遞歸選擇某個子節點直到達到葉子節點 L。當在一個節點s，我們怎麼選擇子節點 呢？我們選擇子節點不應該亂選，而是應該選擇那些優質的子節點。AlphaGo 中的選擇子節點的方式如下所示。 其中是策略網路的輸出。一個有意思的點在於一個節點被訪問次數越多，選擇它作為子節點的可能性越小，這是為了搜索多樣性考慮。

2. 擴展

如果 L 節點上圍棋對弈沒有結束，那麼可能創建一個節點 C。

3. 模擬

用價值網路和快速走子計算節點 C 的質量度。

4. 反向傳播

根據 C 的質量度，更新它爸爸爺爺祖先的質量度。

上述搜索步驟反覆進行，直到達到某個終止條件。搜索結束後，MCTS 選擇根節點的質量度最高的子節點作為 AlphaGo 的著法。

2. 網路結構和訓練方法

AlphaGo Zero 的網路結構和之前的版本不同。AlphaGo Zero 的網路結構採用了 resnet 網路，而之前的版本則採用了傳統的 CNN 網路。同時 AlphaGo Zero 將 policy 網路和 value 網路結合在一起，一個網路同時輸出不同動作概率和預估勝率，如下所示。

網路結構定義好了，我們來看下 AlphaGo Zero 是怎麼自我對弈 (Self-Play) 進行訓練的。將上面的模型接入 MCTS, MCTS 就能有策略地進行搜索，搜索結果是當前盤面不同動作的概率。由於 MCTS 經過了搜索，輸出的動作概率肯定要好於模型自身輸出的動作概率，因此可以將 MCTS 視作模型的提升器。自我對弈是從初始圍棋盤面開始；MCTS 輸入當前盤面 s1 輸出不同動作概率 p1，按照該概率採樣一個動作作為玩家落子；MCTS 作為對手輸入當前盤面 s2 輸出不同動作的概率 p2，按照該概率採樣一個動作作為對手的落子；不停執行，直到分出勝負 z。收集數據(s1,p1,z),..., 作為訓練數據訓練模型。整個訓練流程如下所示。

在這裡，我個人有點疑問。這種訓練方法明顯地和我們認知的基於馬爾科夫決策過程 (Markov Decision Process, MDP) 的強化學習有區別，但論文還是稱之為強化學習。難度強化學習有更廣義的定義嘛？

3. 實驗效果

3.1 不同網路結構的比較

AlphaGo Zero 網路結構有兩個改動:1) 用 resnet 替代了傳統 CNN, 2) 合併了 policy 網路和 value 網路。下圖可以看出這兩個改動能提高 AlphaGo Zero 的效果（sep 表示policy和value分開，dual 表示合在一起; res 表示 resnet 網路，cnn 表示傳統的CNN）。

3.2 不同版本 AlphaGo 的比較

從下圖可以看出，不用人類知識的 AlphaGo Zero 超過之前的版本。另外從下圖能看出來的是，訓練完成之後，MCTS 提升器 + 模型的能力還是要比模型要強。

4. 總結

大家以為圍棋都做到頭了，其他做圍棋的團隊在極力用舊方法提高棋力。沒有想到 DeepMind 以 「不需要人類知識」 為最大亮點，搞出這麼一個重磅研究工作。「不需要人類知識」 得以實現是因為模型+ MCTS 提升器的訓練方法。在利用模型的基礎上，MCTS 提升器總是強於模型本身，從而為模型提升指明了方向；模型的提升又進一步增強了 MCTS 提升器的能力；這就形成了正向循環。一個總是比模型強的提升器，是正向循環能夠建立的關鍵。

很多自媒體已經開始鼓吹，這是邁向通用智能的重要一步。這個是不對的。圍棋因為規則明確和完全信息，我們找到了 MCTS 這個總是比模型強的模型提升器。但在更多通用領域，這樣的模型提升器還是比較難找到的。

博客原文地址:AlphaGo Zero 筆記 | AlgorithmDog

參考文獻

1. Silver, David, et al. "Mastering the game of Go without human knowledge." Nature 550.7676 (2017): 354-359.