2016年3月，Alpha Go Master擊敗最強(qiáng)的人類圍棋選手之一李世石。擊敗李的版本，在訓(xùn)練過程中使用了大量人類棋手的棋譜。2017年10月19日，DeepMind公司在《自然》雜志發(fā)布了一篇新的論文，AlphaGo Zero——它完全不依賴人類棋手的經(jīng)驗(yàn)，經(jīng)過3天的訓(xùn)練，Alpha Go Zero擊敗了Master版本。AlphaGo Zero最重要的價值在于，它不僅僅可以解決圍棋問題，它可以在不需要知識預(yù)設(shè)的情況下，解決一切棋類問題，經(jīng)過幾個小時的訓(xùn)練，已擊敗最強(qiáng)國際象棋冠軍程序Stockfish。其應(yīng)用場景非常廣泛。
AlphaGo Zero 采用了蒙特卡洛樹搜索＋深度學(xué)習(xí)算法，本文將盡可能用簡單易懂的語言解釋其工作原理。
樹搜索
從一個棋盤的初始狀態(tài)，開始思考下一步如何走。我們可以回顧一下我們思考的過程，我們會思考自己可以有哪幾種走法，如果我走了這里，對手可能會走哪里，那么我還可以在哪里走。我和對手都會選擇最有利的走法，最終價值最大的那一手，就是我要選擇的下法。很明顯這個思維過程是一顆樹，為了尋找最佳的行棋點(diǎn)的過程，就是樹搜索。
圍棋第一手有361種下法，第二手有360種，第三手有359，依次類推，即一共有 361! 種下法，考慮到存在大量不合規(guī)則的棋子分布，合理的棋局約占這個數(shù)字的1.2%(Counting Legal Positions in Go). 約為2.081681994 * 10^170。這個一個天文數(shù)字，比目前可觀測宇宙的所有原子數(shù)還要多。要進(jìn)行完全樹搜索，是不可能的。因此我們必須進(jìn)行剪枝，并限制思考的深度。所謂剪枝，就是指沒必要考慮每種下法，我們只需考慮最有價值的幾手下法。所謂限制思考的深度，就是我們最多只思考5步，10步，20步。常見的算法是Alpha-beta剪枝算法。但是，剪枝算法也有它的缺陷，它很有可能過早的剪掉了后期價值很大走法。
蒙特卡洛方法
簡而言之，蒙特卡洛方法(Monte Carlo method)，是一種“統(tǒng)計(jì)模擬方法”。20世紀(jì)40年代，為建造核武器，馮.諾伊曼 等人發(fā)明了該算法。因賭城蒙特卡洛而得名，暗示其以概率作為算法的基礎(chǔ)。
假設(shè)我們要計(jì)算一個不規(guī)則形狀的面積，我們只需在包含這個不規(guī)則形狀的矩形內(nèi)，隨機(jī)的擲出一個點(diǎn)，每擲出一個點(diǎn)，則N+1，如果這個點(diǎn)在不規(guī)則圖形內(nèi)則W+1。落入不規(guī)則圖形的概率即為 W/N。當(dāng)擲出足夠多的點(diǎn)之后，我們可以認(rèn)為：不規(guī)則圖形面積＝矩形面積＊W/N。
要應(yīng)用蒙特卡洛算法的問題，首先要將問題轉(zhuǎn)化為概率問題，然后通過統(tǒng)計(jì)方法將其問題的解估計(jì)出來。
蒙特卡洛樹搜索（MCTS）
1987年Bruce Abramson在他的博士論文中提出了基于蒙特卡洛方法的樹搜索這一想法。這種算法簡而言之是用蒙特卡洛方法估算每一種走法的勝率。如果描述的再具體一些，通過不斷的模擬每一種走法，直至終局，該走法的模擬總次數(shù)N，與勝局次數(shù)W，即可推算出該走法的勝率為 W/N。
該算法的每個循環(huán)包含4個步驟：選擇、擴(kuò)展、仿真、反向傳播。一圖勝千言。
圖中N表示總模擬次數(shù)，W表示勝局次數(shù)。每次都選擇勝率最大的節(jié)點(diǎn)進(jìn)行模擬。但是這樣會導(dǎo)致新節(jié)點(diǎn)無法被探索到。為了在最大勝率和新節(jié)點(diǎn)探索上保持平衡，UCT（Upper Confidence Bound，上限置信區(qū)間算法）被引入。所謂置信區(qū)間，就是概率計(jì)算結(jié)果的可信度。打個比方，如果擲了3次硬幣，都是正面朝上，我們就認(rèn)為擲硬幣正面朝上概率是100%，那肯定是錯誤的，因?yàn)槲覀兊臉颖咎倭恕Ｋ訳CT就是用來修正這個樣本太少的問題。具體公式如下：
其中wi 是i節(jié)點(diǎn)的勝利次數(shù)，ni是i節(jié)點(diǎn)的模擬次數(shù)，Ni是所有模擬次數(shù)，c是探索常數(shù)，理論值為 √2，可根據(jù)經(jīng)驗(yàn)調(diào)整。公式的后半部分，探索次數(shù)越少，值會越大，所以，那些被探索比較少的點(diǎn)，會獲得更多的探索機(jī)會。
蒙特卡洛樹搜索算法因?yàn)槭侵苯幽M到游戲終局，所以這種算法更加的準(zhǔn)確，而且并不需要一個明確的“估值函數(shù)”，你只需要實(shí)現(xiàn)游戲機(jī)制就足夠了。而且，蒙特卡洛算法，可以隨時終止，根據(jù)其訓(xùn)練的時間給予近似的最優(yōu)結(jié)果。
但是對于圍棋這種游戲而言，它的選擇點(diǎn)依然太多，這棵樹會非常的大?？赡苡幸粋€分支早已被丟棄，那么它將不會被統(tǒng)計(jì)，這可能是李世石能夠在第四局擊敗AlphaGo的主要原因。對于這類情況，我們依然需要依賴一個好的估值函數(shù)來輔助。
深度學(xué)習(xí)
近年來，深度卷積神經(jīng)網(wǎng)絡(luò)在視覺領(lǐng)域取得很大的成功，如圖片分類，人臉識別等。深度學(xué)習(xí)的網(wǎng)絡(luò)結(jié)構(gòu)在此不贅述，簡而言之，深度學(xué)習(xí)是一個最優(yōu)化算法。
我們可以將深度神經(jīng)網(wǎng)絡(luò)理解為一個黑盒，這個黑盒接收一批輸入，得到一個輸出，并根據(jù)輸出計(jì)算出損失（誤差），這個誤差會反饋給黑盒，當(dāng)給了足夠多的數(shù)據(jù)之后，這個黑盒將具備一個特性，就是使誤差最小化。
如果這么說還是難以理解的話，可以打個比方：深度神經(jīng)網(wǎng)絡(luò)是一種生物，它喜歡吃糖，有學(xué)習(xí)的能力，你給它看一張圖片，它告訴你是貓還是狗，如果它猜對了，你就給它一顆糖，猜錯了，就不給糖，久而久之，它就有了分辨貓狗的能力。作為創(chuàng)造者，你甚至不知道它是如何分辨貓狗的，但是它做到了，看得越多，識別的就越準(zhǔn)。
這里至關(guān)重要的是——輸入是什么？輸出是什么？什么時候給糖的動作，也就是損失函數(shù)如何設(shè)計(jì)？在實(shí)際的操作過程中，網(wǎng)絡(luò)結(jié)構(gòu)的設(shè)計(jì)也很重要，這里不再細(xì)述。
對于圍棋來說，深度網(wǎng)絡(luò)可以用來評估下一步的主要選點(diǎn)（降低樹的寬度），以及評估當(dāng)前局面的值。
AlphaGo Zero
在AlphaGo Lee版本，有兩個神經(jīng)網(wǎng)絡(luò)，一個是策略網(wǎng)絡(luò)，是一個有監(jiān)督學(xué)習(xí)，它利用了大量的人類高手的對弈棋局來評估下一步的可能性，另一個是價值網(wǎng)絡(luò)，用來評價當(dāng)前局面的評分。而在AlphaGo Zero版本，除了圍棋規(guī)則外，沒有任何背景知識，并且只使用一個神經(jīng)網(wǎng)絡(luò)。
這個神經(jīng)網(wǎng)絡(luò)以19x19棋盤為輸入，以下一步各下法的概率以及勝率為輸出，這個網(wǎng)絡(luò)有多個batch normalization卷積層以及全連接層。
AlphaGo Zero的核心思想是：MCTS算法生成的對弈可以作為神經(jīng)網(wǎng)絡(luò)的訓(xùn)練數(shù)據(jù)。 還記得我們前面說過的深度學(xué)習(xí)最重要的部分嗎？輸入、輸出、損失！隨著MCTS的不斷執(zhí)行，下法概率及勝率會趨于穩(wěn)定，而深度神經(jīng)網(wǎng)絡(luò)的輸出也是下法概率和勝率，而兩者之差即為損失。隨著訓(xùn)練的不斷進(jìn)行，網(wǎng)絡(luò)對于勝率的下法概率的估算將越來越準(zhǔn)確。這意味著什么呢？這意味著，即便某個下法AGZ沒有模擬過，但是通過神經(jīng)網(wǎng)絡(luò)依然可以達(dá)到蒙特卡洛的模擬效果！也就是說，我雖然沒下過這手棋，但憑借我在神經(jīng)網(wǎng)絡(luò)中訓(xùn)練出的“棋感”，我可以估算出這么走的勝率是多少！
AlphaGo Zero的對弈過程只需應(yīng)用深度網(wǎng)絡(luò)計(jì)算出的下法概率、勝率、MCTS的置信區(qū)間等數(shù)據(jù)即可進(jìn)行選點(diǎn)。
AlphaGo Zero 論文節(jié)選
a:自我對弈過程s1，...，sT。 在每個狀態(tài)st, 使用最近一次的網(wǎng)絡(luò)fθ，執(zhí)行一次MCTS αθ （見圖2）。 下法根據(jù)MCTS計(jì)算的搜索概率而選擇，at ~ πt. 評價終止?fàn)顟B(tài)sT，根據(jù)游戲規(guī)則來計(jì)算勝利者z。
b: AlphaGo Zero的神經(jīng)網(wǎng)絡(luò)訓(xùn)練。網(wǎng)絡(luò)使用原始的棋盤狀態(tài)st作為輸入，通過數(shù)個卷積層，使用參數(shù)θ，輸出有向量 pt, 表示下法的分布概率，以及一個標(biāo)量vt，表示當(dāng)前玩家在st的勝率。網(wǎng)絡(luò)參數(shù)θ將自動更新，以最大化策略向量pt和搜索概率πt的相似性，并最小化預(yù)測贏家vt與實(shí)際贏家z的誤差。新參數(shù)將應(yīng)用于下一次自我對弈a的迭代。
a: 每次模擬選擇的分支，有最大Q+U, 其中Q是動作價值，U是上限置信，U依賴于一個存儲在分支上的優(yōu)先概率P和該分支的訪問次數(shù)N（每訪問一次N+1）。
b: 擴(kuò)展葉節(jié)點(diǎn)，神經(jīng)網(wǎng)絡(luò)（P(s, .), V(s)) = fθ(s)評估s; 將向量P的值被存儲在s的擴(kuò)展邊上。
c: 根據(jù)V更新動作價值（action-value)Q，反映所有該動作的子樹的平均值。
d: 一旦搜索結(jié)束，搜索概率π被返回，與 Ν^(1/τ) 成正比，N是每個分支的訪問次數(shù)，而τ是一個參數(shù)控制著溫度（temperature）。
AlphaGo Zero的應(yīng)用
AGZ算法本質(zhì)上是一個最優(yōu)化搜索算法，對于所有開放信息的離散的最優(yōu)化問題，只要我們可以寫出完美的模擬器，就可以應(yīng)用AGZ算法。所謂開放信息，就像圍棋象棋，斗地主不是開放信息，德?lián)潆m然不是開放信息，但本身主要是概率問題，也可以應(yīng)用。所謂離散問題，下法是一步一步的，變量是一格一格，可以有限枚舉的，比如圍棋361個點(diǎn)是可以枚舉的，而股票、無人駕駛、星際爭霸，則不是這類問題。Deepmind要攻克的下一個目標(biāo)是星際爭霸，因?yàn)樗遣煌耆畔ⅲB續(xù)性操作，沒有完美模擬器（隨機(jī)性），目前在這方面AI還是被人類完虐
所以看到AG打敗人類，AGZ打敗AG，就認(rèn)為人工智能要打敗人類了，這種觀點(diǎn)在未來可能成立，但目前還有點(diǎn)危言聳聽。距離真正打敗人類，AGZ還差得很遠(yuǎn)。
作者簡介
桂糊涂，多年從事服務(wù)端架構(gòu)工作，2015年開始機(jī)器學(xué)習(xí)相關(guān)研究，現(xiàn)任某互聯(lián)網(wǎng)公司CTO。長期招聘高可用架構(gòu)、機(jī)器學(xué)習(xí)、Go、node.js、移動端開發(fā)等優(yōu)秀工程師
