六一獻禮：這是迄今為止，AlphaGo演算法最清晰的解讀

作者：西樓，USC神經科學的PHD&圍棋業餘4段

最近DeepMind團隊（google旗下）的AlphaGo（一個圍棋的AI）以4:1戰勝頂尖人類職業棋手李世石。她到底是怎麼下棋的？

AlphaGo在面對當前棋局時，她會模擬(推演棋局)N次，選取「模擬」次數最多的走法，這就是AlphaGo認為的最優走法。

例如圖中，所有沒有落子的地方都是可能下子的，但在模擬中，右下那步走了79%次，就選那一步了，就那麼簡單。後面你會發現，「模擬」次數「最多」的走法就是統計上「最優」的走法。

1.啥是模擬？

模擬就是AlphaGo自己和自己下棋，相當於棋手在腦袋中的推演，就是棋手說的「計算」。

AlphaGo面對當前局面，會用某種（下面會講）策略，自己和自己下。其中有兩種策略：往後下幾步（提前終止，因為AlphaGo有一定判斷形勢的能力）；或者一直下到終局（終局形勢判斷相對簡單，對於棋手簡單，對於機器還有一定難度，但是這個問題已經基本解決）。對於棋手來說就是推演棋局。

AlphaGo會模擬多次，「不止一次」。越來越多的模擬會使AlphaGo的推演「越來越深」（一開始就1步，後來可能是幾十步），對當前局面的判斷「越來越准」（因為她知道了後面局面變化的結果，她會追溯到前面的局面，更新對前面局面的判斷），使後面的模擬「越來越強」（更接近於正解，她後面模擬出來的著法會越來越強）。怎麼做到的？看她怎麼模擬的。

注意，這裡的模擬是下棋（線上）時的模擬，後面還會有個學習時的模擬，不要混淆了。

2.AlphaGo怎麼模擬的？

每次模擬中，AlphaGo自己和自己下。每步中由一個函數決定該下哪一步。函數中包括了以下幾個方面：這個局面大概該怎麼下（選點：policy net），下這步會導致什麼樣的局面，我贏得概率是多少（形勢判斷：value net 和rollout小模擬），鼓勵探索沒模擬過的招法。這些英文名詞後面會有解釋。

模擬完一次後，AlphaGo會記住模擬到棋局，比如幾步以後的棋局。並且計算這時policy，value。因為這時已經更接近終局了，這時的值會更加準確（相對於前面的模擬或局面）。AlphaGo還會用這些更準的值更新這個函數，函數值就越來越准了，所以模擬的每一步越來越接近正解（最優的下法），整個模擬越來越接近黑白雙方的最優下法（主變化，principle variation），就像圍棋書上的正解圖一樣。到此為止，你已經大概了解AlphaGo她怎麼工作的了，下面只是一些細節和數學了。

3.那個函數是啥，好神奇？

這個函數，分為兩個部分。

Q是action value， u是bonus。Q其實就是模擬多次以後，AlphaGo計算走a這步贏的概率，其中會有對未來棋局的模擬（大模擬中的小模擬），和估計。u中包括兩個部分。一方面根據局面（棋形）大概判斷應該有那幾步可以走，另一方面懲罰模擬過多的招法，鼓勵探索其他招法，不要老模擬一步，忽略了其他更優的招法。

4.Q（action value）具體是什麼？

Q看上去有點複雜，其實就是模擬N次以後，AlphaGo認為她模擬這步贏得平均概率。

分母N是模擬這步棋的次數。

分子是每次模擬贏的概率（V)的加和。

其中V又包括兩部分，value net對形勢的判斷。和一個快速模擬到終局，她贏的概率。

value net是說她看這個這個局面，就要判斷贏的概率，「不準」往下幾步想了。value net下面詳細講。

快速模擬是說她看這個這個局面，自己和自己下完，看看黑白誰贏的概率高。快速模擬是我們這個大模擬中的一個小模擬。

Q就是看當下（value net），也看未來（快速模擬），來決定怎麼模擬（對人來說就是往哪裡想，對於棋手就是思考哪些可能的著法），下棋方（模擬中下棋方黑白都是AlphaGo）下那一步贏的概率高，從而決定模擬下那一步。

5.u（bonus）具體是啥？

u中包括兩個部分。

分子是AlphaGo根據當前局面判斷（policy net），不模擬，比如棋手根據棋形大概知道應該有哪幾步可以走。

分母是模擬到現在走當前步的累加，越大下次模擬越不會走這了。

一句話，（Q+u）就是決定模擬中，下棋方會走（模擬）哪裡。

到此，我們大概了解了AlphaGo的兩大神器：value net（形勢判斷：模擬中，我走這步，我贏的概率是多少）和policy net（選點：模擬中，這個局面我走那幾步最強）。下面會揭開他們神秘的面紗。

6.為什麼選模擬次數最多的一步？

根據以上的函數可知，模擬次數最多一步，其實就是在多次模擬中，AlphaGo認為那一步最可能贏的次數的累加（或平均，除以總模擬次數）。

7.為什麼要分為policy net（選點）和value net（形勢判斷）呢，選點和形勢判斷不是一個東西嗎？

確實，選點和形勢判斷是互相嵌套的。首先，圍棋的形勢判斷是非常困難的。在圍棋直播中我們經常看到，職業9段也不能準確判斷當前局面，除非地域已經確定，沒有什麼可以繼續戰鬥的地方，一般也就是接近終局（官子階段）。即使職業棋手，選點和判斷也是定性的成分偏多，定量的成分偏少。以前說中國頂級棋手古力能推演到50步，已經非常強了。

再說嵌套問題，準確的定量的選點和判斷，就要計算（對於棋手是在腦子裡推演，對於機器就是模擬）才行。在推演中，我選點走那步決定於，走這步後我贏的概率，而這個概率又決定於對手走那一步（我會假設對手弈出她最強的一步，對我最不利），對手走那一步決定於，她走那步後，她對形勢的判斷要對她最好，這又取決於我的下下步（第3步了）走哪裡（對手她也會假設我會下出對她最不利的一步，自然對我最優），從而不斷的嵌套，這個「死結」要到終局（或者接近）才能解開（終局形勢判斷比較簡單）。所以不到終局，判斷形勢是非常困難的，即使職業的9段也不行。這就是圍棋比象棋難的關鍵所在，它沒有簡單的形勢判斷的方法，而象棋有。

要回答這個問題7還要看下面了。

8.AlphaGo是怎麼打開這個死結的？

AlphaGo沒有進行直接的形勢判斷，就是沒有直接學習value net，而是先做一個選點（policy net）程序。選點可以認為是一個時序（走棋）的一個局部問題，就是從當前局面大概判斷，有哪幾步可能走，暫時不需要推演（那是模擬的工作）。棋手的選點是會推演的，這裡的基礎policy net是不推演的，前已經看到AlphaGo線上模擬中選點（Q+u）是有推演的。

所以policy net是用在「每次模擬」中，搜索雙方可能的著法，而最優步的判斷是「N次模擬」的任務，policy net不管。此外policy net還用來訓練value net，也就是說，value net是從policy net 來的，先有policy 才有value。

選點（policy net）能成立嗎？如果不成立，也是沒用。

9.第一神器policy net怎麼工作的？

先大概看下這個圖。現在輪到黑棋下，圖上的數字是AlphaGo認為黑棋應該下這步的概率。我們還發現，只有幾步（2步在這個圖中）的概率比較大，其他步可能性都很小。這就像職業棋手了。學圍棋的人知道，初學者會覺得那裡都可以走，就是policy（選點）不行，沒有選擇性。隨著棋力增長，選擇的範圍在縮小。職業棋手就會鎖定幾個最有可能的走法，然後去推演以後的變化。

AlphaGo通過學習，預測職業選手的著法有57%的準確率。提醒一下，這還是AlphaGo「一眼」看上去的效果，她沒開始推演（模擬）呢。而且她沒預測對的著法不一定比職業棋手差。

policy net怎麼學習的，學啥？？？

首先，policy net是一個模型。它的輸入時當前的棋局（19*19的棋盤，每個位置有3種狀態，黑，白，空），輸出是最可能（最優）的著法，每個空位都有一個概率（可能性）。幸運的是，著法不像形勢判斷那麼無跡可尋。我們人已經下了千年的棋。policy net先向職業選手學習，她從KGS圍棋伺服器，學習了3000萬個局面的下一步怎麼走。也就是說，大概職業選手怎麼走，AlphaGo她已經瞭然於胸。學習的目的是，她不是單純的記住這個局面，而是相似的局面也會了。當學習的局面足夠多時，幾乎所有局面她都會了。這種學習我們叫做「監督學習」（supervised learning）。以前的職業棋手的棋譜，就是她的老師（監督）。

AlphaGo強的原因之一是policy net這個模型是通過深度學習（deep learning）完成的。深度學習是近幾年興起的模擬人腦的機器學習方法。它使AlphaGo學習到的policy更加準確。以前的AI都沒有那麼強的學習能力。

更加厲害的是，AlphaGo從職業棋手學完後，感覺沒什麼可以從職業棋手學的了。為了超越老師和自己，獨孤求敗的她只能自己左右互搏，通過自己下自己，找到更好的policy。比如說，她從監督學習學到了一個policy，P0。

AlphaGo會例外做一個模型P1。P1一開始和P0一樣（模型參數相同）。稍微改變P1的參數，然後讓P1和P0下，比如，黑用P1，白用P0選點，直到下完（終局）。模擬多次後，如果P1比P0強（贏的多），則P1就用新參數，否則，重新再原來基礎上改變參數。我們會得到比P0強一點點的P1。注意，選點是按照policy的概率的，所以每次模擬是不同的。多次學習後AlphaGo會不斷超越自己，越來越強。這種學習我們叫做增強學習（reinforcement learning）。它沒有直接的監督信息，而是把模型發在環境中（下棋），通過和環境的互相作用，環境對模型完成任務的好壞給於反饋（贏棋還是輸），從而模型改變自己（更新參數），更好的完成任務（贏棋）。增強學習後，AlphaGo在80%的棋局中戰勝以前的自己。

最後，AlphaGo還有一個mini的policy net，叫rollout。它是用來上面所說的模擬中，快速模擬的終局的。它的輸入比正常policy net小，它的模型也小，所以它的耗時是2微妙，而一個policy要3毫秒。它沒有policy准，但是它快。

總結一下policy。它是用來預測下一步「大概」該走哪裡。它使用了深度學習，監督學習，增強學習等方法。它主要用於每次模擬中的bonus的先驗（我大概該怎麼走），和value net的學習（後面的重點）。

如果單純用policy預測的著法來作為最優著法，不通過value net的計算和上面說的模擬，對職業棋手那是不行的。但是，單純用policy預測已經足夠打敗以前的圍棋AI（大約有業餘5段實力）了。這說明了上面3種學習方法的強大威力。

AlphaGo就看了一眼，還沒有推演，你們就敗了。policy net為解開那個死結走出了第一步，下面我們就講講這第二個「神器」：value net。

10.第二神器value net怎麼工作的？

前面說了，形勢判斷是什麼無跡可尋，就連職業9段也做不到。有了policy net，整個世界都不一樣了。AlphaGo她的靈魂核心就在下面這個公式里。

V*（s）=Vp*（s）約等於Vp（s）。

s是棋盤的狀態，就是前面說的19*19，每個交叉3種狀態。

V是對這個狀態的評估，就是說黑贏的概率是多少。

V*是這個評估的真值。

p*是正解（產生正解的policy）

p是AlphaGo前面所說學到的最強的policy net。

如果模擬以後每步都是正解p*，其結果就是V*，這解釋了等號。

如果你知道V*這個函數，在當前局面，你要對走下一步（圍棋平均有250種可能性）後的狀態s進行評估，選最大的V*走就行。圍棋就完美解決了。但是，前面說了，V*不存在。同樣p*也不存在（理論上存在，實際因為搜索空間太大，計算量太大找不到。在5*5的棋盤中下棋可以做到）。

AlphaGo天才般的用最強poilicy，p來近似正解p*，從而可以用p的模擬Vp來近似V*。即使Vp只是一個近似，但已經比現在的職業9段好了。想想她的p是從職業選手的著法學來的，就是你能想到的棋她都想到了。而且她還在不斷使的p更准。頂尖職業棋手就想以後的20-40步，還會出錯（錯覺）。AlphaGo是模擬到終局，還極少出錯。天哪，這人還怎麼下。

圍棋問題實際是一個樹搜索的問題，當前局面是樹根，樹根長出分支來（下步有多少可能性，棋盤上的空處都是可能的），這是樹的廣度，樹不斷生長（推演，模擬），直到葉子節點（終局，或者後面的局面）。樹根到葉子，分了多少次枝（推演的步數）是樹的深度。樹的平均廣度，深度越大，搜索越難，要的計算越多。圍棋平均廣度是250，深度150，象棋平均廣度是35，深度80。如果要遍歷圍棋樹，要搜索250的150次方，是不實際的。這也是圍棋比象棋複雜的多的原因之一。但更重要的原因前面講了：是象棋有比較簡單的手工可以做出的value函數。比如，吃王（將）得正無窮分，吃車得100分，等等。1997年打敗當時國際象棋世界冠軍的DeepBlue就是人手工設計的value。而圍棋的value比象棋難太多了。手工根本沒法搞。又只能靠深度學習了。

在講value的原理前，先看看定性看看value的結果。如圖，這是AlphaGo用value net預測的走下一步，她贏的概率。空的地方都被藍色標示了，越深說明AlphaGo贏的概率越高。這和我們學的棋理是相符的，在沒有戰鬥時，1,2線（靠邊的地方）和中間的概率都低，因為它們效率不高。而且大多數地方的概率都接近50%。所以說贏棋難，輸棋也很難。這當然排除雙方激烈戰鬥的情況。

這裡講講怎麼通過policy net 得到value net。有了policy，value就不是那麼難以捉摸了，死結打開了。AlphaGo可以模擬（自己和自己下，黑白都用最強的policy），直到終局。注意，這裡的模擬和最初說的模擬有點不同。最初的模擬是AlphaGo在下棋（線上）中用的，用來預測。這裡的模擬是她還在學習（線下）呢。終局時V*（誰贏）就比較容易判斷了。當然，對機器來說也不是那麼容易的，但相對於中局來說是天淵之別。

value net也是一個監督的深度學習的模型。多次的模擬的結果（誰贏）為它提供監督信息。它的模型結構和policy net相似，但是學的目標不同。policy是下步走哪裡，value是走這後贏的概率。

總結一下，value net預測下一走這後，贏的概率。本身無法得到。但是通過用最強policy來近似正解，該policy的模擬來近似主變化（就圍棋書上那個，假設書上是對的），模擬的結果來近似準確的形勢判斷V*。value net用監督的深度學習去學模擬的得到的結果。value net主要用於模擬（在線，下棋的時候）時，計算Q值，就是平均的形勢判斷。

再回顧一下模擬，模擬的每一步是兼顧：模擬到現在平均的形勢判斷value net，快速rollout模擬到終局的形勢判斷，根據當前形勢的選點policy，和懲罰過多的模擬同一個下法（鼓勵探索）等方面。經過多次模擬，樹會搜索的越來越廣，越來越深。由於其回溯的機制，Q值越來越准，下面的搜索會越來越強。因為每次的Q值，都是當前模擬認為的最優（排除鼓勵探索，多次後會抵消），模擬最多的下法（樹分支）就是整個模擬中累積認為最優的下法。

到此為止，AlphaGo她神秘的面紗已經揭開。她的基本框架見下圖。下棋時的線上過程是圖中紅箭頭。線下的準備工作（學習過程）是藍箭頭。。再串一下。AlphaGo下棋（線上）靠模擬，每次模擬要選下那一步，不是簡單的選點policy就完了，而是要參考以前模擬的形勢判斷，包括：value net和快速模擬（小模擬）到終局，鼓勵探索，policy（先驗），就是（Q+u），它比單純的policy准。她選擇模擬最多的下法（就是平均最優）。這是線上，下著棋了。之前（線下），她要訓練好policy模型，rollout模型和value 模型。其中，policy，rollout可以從棋譜，和自己下棋中學到。value可以從用學好的policy下棋的模擬結果監督學到。從而完美解決value學不到的問題和policy和value互相嵌套的死結。從棋譜直接學value net現在還不行。

11.AlphaGo用到哪些技術？

AlphaGo在樹搜索的框架下使用了深度學習，監督學習和增強學習等方法。

以前最強的圍棋AI使用蒙特卡洛樹搜索的方法。蒙特卡洛演算法通過某種「實驗」的方法，等到一個隨機變數的估計，從而得到一個問題的解。這種實驗可以是計算機的模擬。讓我們看看蒙特卡洛樹搜索怎麼模擬的。演算法會找兩個圍棋傻子（計算機），他們只知道那裡可以下棋（空白處，和非打劫剛提子處），他們最終下到終局。好了，這就可以判斷誰贏了。演算法就通過模擬M（M>>N）盤，看黑贏的概率。可以看到這明顯的不合理。因為每步是亂下的。有些棋根本就不可能。即使如此，這個演算法可以達到業餘5段左右水平。

AlphaGo可不是亂下，她是學了職業棋手著法的。所以AlphaGo的搜索叫beam search(只搜索幾條線，而不是掃一片)。前面也可以看到AlphaGo認為的可能著法就幾種可能性，而不是隨機的250種。這就是從250的150次方到幾（<><150，可以提前終止搜索，因為有value>

12.什麼是打劫？

打劫，是指黑白雙方都把對方的棋子圍住，這種局面下，如果輪白下，可以吃掉一個黑子；如果輪黑下，同樣可以吃掉一個白子。因為如此往複就形成循環無解，所以圍棋禁止「同形重複」。根據規則規定「提」一子後，對方在可以回提的情況下不能馬上回提，要先在別處下一著，待對方應一手之後再回「提」。如圖中的情況：

打劫因為反覆走同一個點，會使搜索樹的深度加大，而且因為其他位置劫才會影響劫的輸贏，劫才之間又相互影響，有可能打劫中又產生新的劫。總之，打劫規則會使圍棋的複雜度加大。

因為前兩局棋沒有下出打劫，有人會懷疑DeepMind和李世石有不打劫協議。在後面的棋局中，AlphaGo確實下出了主動打劫。而且從演算法層面看，打劫也不會是她的模擬框架崩潰（可能會有一些小麻煩）。

13.遇強則強，遇弱則弱？

AlphaGo的表現似乎是遇強則強，遇弱則弱。這可能是由於她的學習監督信息決定的。policy和value學習時，和rollout模擬時，最後的結果是誰贏(的概率)，而不是誰贏「多少」（贏幾目）。所以在AlphaGo領先時（幾乎已經是常態了），她不會下出過分的棋，她只要保證最後贏就行了，而不是像人一樣要贏的多，贏的漂亮。即使有殺大龍（一大塊棋）的機會，她也不一定殺，而是走溫和的棋，讓你無疾而終。估計只有在AlphaGo判斷她大大落後的時候，她才會冒險走過分的棋（這好像不常見）。

14.AlphaGo下棋為什麼花錢？

AlphaGo有單機版，多機（分散式）。分散式明顯比單機強。去年的分散式有40個搜索線程，1202個CPU，176個GPU（顯卡）。和李世石下棋時可能更多。這麼多機器的運作和維護就是燒錢。

15.AlphaGo有漏洞嗎？

AlphaGo解決的是一個樹搜索問題，並不是遍歷所有著法的可能性，她的著法只是接近正解，不是一定正解。

最簡單的人戰勝AlphaGo的方法就是改規則，比如擴大棋盤。人類能比較簡單的適應，搜索空間增大，AlphaGo不一定能適應。

就現有狀況來說，棋手可以主要攻擊AlphaGo模擬中的著法選擇函數a。比如盡量下全局互相牽扯的棋（多劫，多塊死活），就是盡量是中盤局面複雜，不要搞一道本（一條路走到底）局部的著法，當然，這對職業選手也不簡單。

16.AlphaGo有哪些技術突破，使她能戰勝人類頂尖棋手？

1. 繼承了蒙特卡洛樹搜索的框架進行模擬。

2. 在學習policy中使用了監督學習，有效的利用現有的棋手的棋譜，學到了他們的選點策略。

3. 在學習policy中使用了增強學習，從左右互搏中提高自己。

4. 利用policy net（選點模型）近似正解，用policy net的對弈的結果模擬正解對弈的結果，即正確的形勢判斷，從而打破形勢判斷和選點相互嵌套的死結。就是先學policy，再學value。

5. 在學習policy， value， rollout中使用深度學習模型。深度學習有非常強的學習能力。使得選點和形勢判斷前所未有的准（對比蒙特卡洛是隨機選點，現在是職業棋手幫她選點了）。因為在每次模擬中用到了這兩個「准」，使得在樹搜索（就是推演）的過程更有目的性（樹大量減枝，只模擬比較優良的下法）

6. 當然還有機器一貫的優勢，不疲勞，不受心理情緒影響，不會錯的記憶力等等。

推薦閱讀：