AlphaGo全系列

AlphaGo算是這波AI浪潮的里程碑事件了。如果說AlexNet讓學術界重新認識了DL的話，AlphaGo則讓大眾都認識到了DL的威力。我也是在AlphaGo的感召之下，投身ML/DL領域的（2016.7）。因此，了解AlphaGo的原理，就成為了我一直以來的目標。豈料直到三年多之后（2019.11），我才能真正看懂AlphaGo。

歷史

我對人工智能的認識，始于1997年深藍大戰卡斯帕羅夫。然而，人工智能的歷史還可追溯到更早的時代。其中，最重要的地方是貝爾實驗室和MIT。

比如，C語言和Unix之父Ken Thompson，就寫過一個叫Belle的國際象棋程序。這也是第一個達到大師級水平的國際象棋程序。

這個時代，博弈系統的人工智能主要采用窮舉遍歷博弈樹的方式。Ken Thompson針對國際象棋殘局進行了計算機窮舉。他發現之前一些公認和局的殘局，實際上是有勝負的，只是勝負要在50步以上，其中的一些走法甚至看不出具體的含義。

窮舉法到深藍時代，達到了頂峰。此后的博弈研究逐漸轉向其他領域，圍棋就是其中一個熱點。

國內的圍棋軟件早期大概算“手談”（作者：陳志行）最為出名。我1996年的時候接觸過，但是它的棋力實在太差。我的一個手下敗將（可讓6子），居然也可讓軟件2子。總之，完全入門級的水平，只適合學棋4個月以內的人。

后來的GNUGo就好的多了，我最多只能讓它2子。

陳志行，1931～2008，廣東番禺人。中山大學化學系畢業（1952），中山大學教授。1991年退休后，從事電腦圍棋開發。從1993年起，共10次獲得電腦圍棋世界冠軍。

參考：

https://www.cnblogs.com/wiki3d/p/handtalk.html

陳志行：計算機圍棋程序手談作者

DarkForestGo

DarkForestGo是田淵棟2015年11月的作品，雖然棋力和稍后的AlphaGo相去甚遠，但畢竟也算是用到了RL和DNN了。

論文：

《Better Computer Go Player with Neural Network and Long-term Prediction》

代碼：

https://github.com/facebookresearch/darkforestGo

DarkForest中的一些規則借鑒了開源圍棋軟件Pachi：

http://pachi.or.cz/

以下是作者本人的講解：

https://zhuanlan.zhihu.com/p/20607684

AlphaGo的分析

上圖是DarkForest的網絡結構圖。其中的細節，我們將在講解AlphaGo的時候，再細說。

AlphaGo

論文：

《Mastering the game of Go with deep neural networks and tree search》

AlphaGo主要由幾個部分組成：

走棋網絡（Policy Network），給定當前局面，預測/采樣下一步的走棋。

快速走子（Fast rollout），目標和1一樣，但在適當犧牲走棋質量的條件下，速度要比1快1000倍。

估值網絡（Value Network），給定當前局面，估計是白勝還是黑勝。

蒙特卡羅樹搜索（Monte Carlo Tree Search，MCTS)，把以上這三個部分連起來，形成一個完整的系統。

以下是詳細的解說。

Policy Network

上圖是AlphaGo的Policy Network的網絡結構圖。

從結構來看，它與DarkForestGo是十分類似的：

都是1層5x5的conv+k層3x3的conv。

兩者的input plane都是手工構建的特征。

由于棋子的精確位置很重要，這些CNN中都沒有pooling。

它們的差異在于：

1.DarkForestGo訓練時，會預測三步而非一步，提高了策略輸出的質量。

Policy Network擺脫了之前的基于規則的圍棋軟件，長于局部，但大局較差的弱點，它的大局觀非常強，不會陷入局部戰斗中。例如，DarkForestGo的走棋網絡直接放上KGS就有3d的水平。

它的缺點是：會不顧大小無謂爭劫，會無謂脫先，不顧局部死活，對殺出錯，等等。有點像高手不經認真思考的隨手棋——只有“棋感”，而沒有計算。（其實更類似于計算力衰退的老棋手，比如聶棋圣。）

Value Network

AlphaGo的Value Network也是一個和Policy Network幾乎一樣的深度卷積網絡。

Fast rollout

有了走棋網絡，為什么還要做快速走子呢？

• 走棋網絡的運行速度是比較慢的（3毫秒），而快速走子能做到幾微秒級別，差了1000倍。

• 快速走子可以用來評估盤面。由于天文數字般的可能局面數，圍棋的搜索是毫無希望走到底的，搜索到一定程度就要對現有局面做個估分。在沒有估值網絡的時候，不像國象可以通過算棋子的分數來對盤面做比較精確的估值，圍棋盤面的估計得要通過模擬走子來進行，從當前盤面一路走到底，不考慮岔路地算出勝負，然后把勝負值作為當前盤面價值的一個估計。顯然，如果一步棋在快速走子之后，生成的N個結果中的勝率較大的話，那它本身是步好棋的概率也較大。

為了速度快，Fast rollout沒有使用神經網絡，而是使用傳統的局部特征匹配（local pattern matching）加線性回歸（logistic regression）的方法。

這種方法雖然沒有NN這么強，但還是比更為傳統的基于規則的方案適應性好。畢竟規則是死的，而傳統的機器學習，再怎么說也是可以自動學習規則的。當然了，這更比隨機走子的效率高了。

DarkForestGo的走子基于規則模板，且沒有快速走子，個人以為這才是它棋力差的主要原因。

由于Fast rollout既可以提供策略，又有一定的價值評估的手段，因此單獨使用它，比單獨使用Policy Network或者Value Network都要好。相當于是一個劣化版本的AlphaGo。

MCTS

AlphaGo的MCTS使用的是傳統的UCT算法，沒太多好講的。一個細節是Game Tree的結點并不是立即展開，而是要等到路過該結點的次數超過一定閾值，才進行展開，從而大大減小了搜索空間。

其他關鍵點

AlphaGo不是一個純粹的DRL，它還是使用了人類棋譜的先驗數據。

• 首先，從人類棋譜中學習rollout策略，并初始化Policy Network。

• 然后，使用自我博弈的方式，訓練Policy Network和Value Network。

由于很多人類的棋局都是因為中間偶然的失誤導致了全盤覆滅（所謂“一著不慎滿盤皆輸”），其中的偶然性非常大，局部的優劣往往和棋局的最終結果無關，因此Value Network并沒有用人類棋譜來訓練。

AlphaGo每更新一個“小版本”后，都要將這個版本和迄今最好的版本對比，如果新的版本勝率超過55%，才會用來取代以前最好的版本。這樣做的顯然的好處是防止AlphaGo自我博弈得“走火入魔”，陷入局部最優。

AlphaGo Zero

論文：

《Mastering the game of Go without human knowledge》

AlphaGo Zero對AlphaGo進行了全面提升：

• input plane去掉了手工特征，基本全由歷史信息組成。

• Policy Network和Value Network不再是兩個同構的獨立網絡，而是合并成了一個網絡，只是該網絡有兩個輸出——Policy Head和Value Head。

• 骨干結構采用了Resnet，層數大大增加。

• 完全采用自我博弈，去掉了人類棋譜。

• 取消了Fast rollout。AlphaGo Zero的實踐表明，如果有足夠好的Value函數的話，MCTS的采樣效率要遠遠高于傳統的alpha-beta剪枝。因此，rollout也不是必須的。

稍后的AlphaZero的實踐表明：AlphaZero搜索80000個節點的棋力，已經超過了Stockfish搜索70000000個節點的棋力。

• Policy Gradient vs. Policy Iteration

AlphaGo依賴快速走子的結果，獲得最終的結果信息。因此，它的獎勵來源比較單一：只有對局的最終結果。這種做法實際上就是通常說的Policy Gradient。

但正如之前指出的：棋下輸了，不意味著每步棋都是臭棋。因此，只使用最終結果，既會導致獎勵稀疏，也不利于實時評估走子的價值。

AlphaGo Zero轉而采用Policy Iteration方法，實時對盤面進行估計，不再依賴終局結果。

AlphaZero

論文：

《Mastering Chess and Shogi by Self-Play with aGeneral Reinforcement Learning Algorithm》

AlphaZero相對于AlphaGo Zero的改進不算大，畢竟也就只差2個月。它的貢獻在于，證明了DRL對于很多棋類都是有效的。

MuZero

MuZero是DeepMind 2019年11月的作品。

論文：

《Mastering Atari, Go, Chess and Shogi by Planning with a Learned Model》

參考代碼：

https://github.com/AppliedDataSciencePartners/DeepReinforcementLearning

基本結構

MuZero在不具備任何底層動態知識的情況下，通過結合基于樹的搜索和學得模型，在Atari 2600游戲中達到了SOTA表現，在國際象棋、日本將棋和圍棋的精確規劃任務中可以匹敵AlphaZero，甚至超過了提前得知規則的圍棋版AlphaZero。

傳統方法的局限：

• Model-based RL在Atari 2600游戲上表現不佳。這類游戲的Model很難刻畫，規則比較抽象。

• Model-Free RL在棋類游戲上表現不佳。棋類的規則十分明確。

上圖是MuZero和AlphaZero的網絡結構對比圖。從中可以看出：

1.AlphaZero只有一個網絡。（雖然有兩個用途：Policy和Value）

2.MuZero有三個網絡：

• Prediction Network。這個和AlphaZero相同。

• Dynamics Network。

• Representation Network。

Representation & Dynamics Network

Representation & Dynamics Network的主要思想來自如下論文：

1.《The Predictron: End-To-End Learning and Planning》

2.《Value Prediction Network》

上文已經指出Model-based方法的困難在于：有的時候Model是很難刻畫的，而環境本身也許并不如模擬器那么純粹、簡單。

一個很自然的思路就是：既然NN能表示Policy和Value，那么能不能表示Model呢？

參考論文1提出了Predictron框架，它的主要思路是：

• 構建一個abstract MDP model。雖然我們并不知道它的state，更不清楚它的transition，但是不要緊，假設它存在就好。

• 狀態表示。(即上圖中的$s^0,s^1,\dots$)

$$s=f(s)$$

這里用$s$表示系統的抽象狀態以區別其實際狀態s。也就是說，在系統模型中，預測的不是實際的狀態s, 而是抽象的狀態。即：建立real state space到abstract state space的映射。

• 模型預測，不只是狀態流的預測，還包括立即回報和折扣因子的預測。

$$s^{\prime },r,\gamma =m(s,\beta )$$

• 抽象狀態$s$處的值函數：

$$v=v(s)$$

• 由回報、折扣因子和值函數計算得到估計值。這里可以對這個abstract MDP model應用TD(n)和TD($\lambda$)算法，得到如上圖所示的k-step和$\lambda$-weighted的預測值。其中的g表示累計獎勵值。

這里的套路其實和DQN非常像，都是讓預測值（這里是g）盡可能接近真實值。區別在于：這里既然是Model-based方法，那么自然有利用Model生成模擬樣本的步驟，而DQN沒有這樣的步驟。

參考論文2的做法也是類似的。

$$\mathbf{E}\mathbf{n}\mathbf{c}\mathbf{o}\mathbf{d}\mathbf{i}\mathbf{n}\mathbf{g}{f}_{\theta }^{enc}:x\to s$$

$$\mathbf{V}\mathbf{a}\mathbf{l}\mathbf{u}\mathbf{e}{f}_{\theta }^{value}:s\to V_{\theta }(s)$$

$$\mathbf{O}\mathbf{u}\mathbf{t}\mathbf{c}\mathbf{o}\mathbf{m}\mathbf{e}{f}_{\theta }^{out}:s,o\to r,\gamma$$

$$\mathbf{T}\mathbf{r}\mathbf{a}\mathbf{n}\mathbf{s}\mathbf{i}\mathbf{t}\mathbf{i}\mathbf{o}\mathbf{n}{f}_{\theta }^{trans}:s,o\to s^{\prime }$$

x：觀測值（observation）。

s：abstract state。

o：abstract state上的option。

s’：下一個abstract state。

也是預測若干步的獎勵值。

實現細節

重新回到MuZero，下圖是MuZero的關鍵步驟圖。

A部分：Representation Network + Dynamics Network + MCTS

B部分：從policy:${\pi }_t$中采樣得到action：$a_{t+1}$，環境根據$a_{t+1}$得到observation：$o_{t+1}$、h和reward：$u_{t+1}$。這些樣本在用過后，被存入replay buffer。

C部分：訓練時，從replay buffer中，采樣得到$o_t$，通過h函數，得到$s_t$，然后執行K-step展開，得到p,v,r。

loss公式為：

$$l_t(\theta )=\sum _{k=0}^K{l}^r(u_{t+k},r_t^k)+l^v(z_{t+k},v_t^k)+l^p({\pi }_{t+k},p_t^k)+c\Vert \theta {\Vert }^2$$

其中，p,v,r分別是policy、value、reward的預測值。而$\pi$、z、u則是對應的target值。（參見《深度強化學習（2）》中DQN一節中的current Q-value和target Q-value的定義）

MuZero和VPN一樣，都是在abstract state space中用dynamics model做planning。MuZero的改進在于增加了對每個abstract state上policy的預測，因此效率比VPN要高一些。

最后需要澄清一點的是：模擬的Model永遠比不上確定的規則。MuZero在棋類上的表現并不如AlphaZero。對比數據中，圍棋項目的優勢，更多的在于MuZero使用了更寬的網絡。

總結

以上是生活随笔為你收集整理的深度学习（四十三）——深度强化学习（6）AlphaGo全系列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。