2016年DeepMind團隊（google旗下）的AlphaGo（一個圍棋的AI）以4:1戰(zhàn)勝頂尖人類職業(yè)棋手李世石。她到底是怎么下棋的？

AlphaGo在面對當前棋局時，她會模擬(推演棋局)N次，選取“模擬”次數(shù)最多的走法，這就是AlphaGo認為的最優(yōu)走法。

例如圖中，所有沒有落子的地方都是可能下子的，但在模擬中，右下那步走了79%次，就選那一步了，就那么簡單。后面你會發(fā)現(xiàn)，“模擬”次數(shù)“最多”的走法就是統(tǒng)計上“最優(yōu)”的走法。

1、啥是模擬？

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

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

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

注意，這里的模擬是下棋（線上）時的模擬，后面還會有個學(xué)習(xí)時的模擬，不要混淆了。

2、AlphaGo怎么模擬的？

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

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

3、那個函數(shù)是啥，好神奇？

這個函數(shù)，分為兩個部分。

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

4、Q（action value）具體是什么？

Q看上去有點復(fù)雜，其實就是模擬N次以后，AlphaGo認為她模擬這步贏得平均概率。

分母N是模擬這步棋的次數(shù)。

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

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

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

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

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

5、u（bonus）具體是啥？

u中包括兩個部分。

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

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

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

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

6、為什么選模擬次數(shù)最多的一步？

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

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

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

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

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

8、AlphaGo是怎么打開這個死結(jié)的？

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

所以policy net是用在“每次模擬”中，搜索雙方可能的著法，而最優(yōu)步的判斷是“N次模擬”的任務(wù)，policy net不管。此外policy net還用來訓(xùn)練value net，也就是說，value net是從policy net 來的，先有policy 才有value。

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

9、第一神器policy net怎么工作的？

先大概看下這個圖?，F(xiàn)在輪到黑棋下，圖上的數(shù)字是AlphaGo認為黑棋應(yīng)該下這步的概率。我們還發(fā)現(xiàn)，只有幾步（2步在這個圖中）的概率比較大，其他步可能性都很小。這就像職業(yè)棋手了。學(xué)圍棋的人知道，初學(xué)者會覺得那里都可以走，就是policy（選點）不行，沒有選擇性。隨著棋力增長，選擇的范圍在縮小。職業(yè)棋手就會鎖定幾個最有可能的走法，然后去推演以后的變化。

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

policy net怎么學(xué)習(xí)的，學(xué)啥？？？

首先，policy net是一個模型。它的輸入時當前的棋局（19*19的棋盤，每個位置有3種狀態(tài)，黑，白，空），輸出是最可能（最優(yōu)）的著法，每個空位都有一個概率（可能性）。幸運的是，著法不像形勢判斷那么無跡可尋。我們?nèi)艘呀?jīng)下了千年的棋。policy net先向職業(yè)選手學(xué)習(xí)，她從KGS圍棋服務(wù)器，學(xué)習(xí)了3000萬個局面的下一步怎么走。也就是說，大概職業(yè)選手怎么走，AlphaGo她已經(jīng)了然于胸。學(xué)習(xí)的目的是，她不是單純的記住這個局面，而是相似的局面也會了。當學(xué)習(xí)的局面足夠多時，幾乎所有局面她都會了。這種學(xué)習(xí)我們叫做“監(jiān)督學(xué)習(xí)”（supervised learning）。以前的職業(yè)棋手的棋譜，就是她的老師（監(jiān)督）。

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

更加厲害的是，AlphaGo從職業(yè)棋手學(xué)完后，感覺沒什么可以從職業(yè)棋手學(xué)的了。為了超越老師和自己，獨孤求敗的她只能自己左右互搏，通過自己下自己，找到更好的policy。比如說，她從監(jiān)督學(xué)習(xí)學(xué)到了一個policy，P0。

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

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

總結(jié)一下policy。它是用來預(yù)測下一步“大概”該走哪里。它使用了深度學(xué)習(xí)，監(jiān)督學(xué)習(xí)，增強學(xué)習(xí)等方法。它主要用于每次模擬中的bonus的先驗（我大概該怎么走），和value net的學(xué)習(xí)（后面的重點）。

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

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

10、第二神器value net怎么工作的？

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

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

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

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

V*是這個評估的真值。

p*是正解（產(chǎn)生正解的policy）

p是AlphaGo前面所說學(xué)到的最強的policy net。

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

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

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

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

在講value的原理前，先看看定性看看value的結(jié)果。如圖，這是AlphaGo用value net預(yù)測的走下一步，她贏的概率?？盏牡胤蕉急凰{色標示了，越深說明AlphaGo贏的概率越高。這和我們學(xué)的棋理是相符的，在沒有戰(zhàn)斗時，1,2線（靠邊的地方）和中間的概率都低，因為它們效率不高。而且大多數(shù)地方的概率都接近50%。所以說贏棋難，輸棋也很難。這當然排除雙方激烈戰(zhàn)斗的情況。

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

value net也是一個監(jiān)督的深度學(xué)習(xí)的模型。多次的模擬的結(jié)果（誰贏）為它提供監(jiān)督信息。它的模型結(jié)構(gòu)和policy net相似，但是學(xué)的目標不同。policy是下步走哪里，value是走這后贏的概率。

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

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

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

11、AlphaGo用到哪些技術(shù)？

AlphaGo在樹搜索的框架下使用了深度學(xué)習(xí)，監(jiān)督學(xué)習(xí)和增強學(xué)習(xí)等方法。

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

AlphaGo可不是亂下，她是學(xué)了職業(yè)棋手著法的。所以AlphaGo的搜索叫beam search(只搜索幾條線，而不是掃一片)。前面也可以看到AlphaGo認為的可能著法就幾種可能性，而不是隨機的250種。這就是從250的150次方到幾（<10)的n(n<<150，可以提前終止搜索，因為有value net）次方，的計算量降低。雖然AlphaGo每次模擬的時間更長（因為要深度模型的預(yù)測policy和value，不是亂下），但是AlphaGo的模擬次數(shù)可以更少，是蒙特卡洛樹搜索的1/15000。就是說AlphaGo的搜索更有目的性了，她大概知道該走哪里。解說說她下棋更像人了。我會說她下棋更像職業(yè)棋手，甚至超過職業(yè)棋手。線下的學(xué)習(xí)使得她的行為（模擬）有了極強的目的性，從而完成最終目標（贏棋）。

12、什么是打劫？

打劫，是指黑白雙方都把對方的棋子圍住，這種局面下，如果輪白下，可以吃掉一個黑子；如果輪黑下，同樣可以吃掉一個白子。因為如此往復(fù)就形成循環(huán)無解，所以圍棋禁止“同形重復(fù)”。根據(jù)規(guī)則規(guī)定“提”一子后，對方在可以回提的情況下不能馬上回提，要先在別處下一著，待對方應(yīng)一手之后再回“提”。如圖中的情況：

打劫因為反復(fù)走同一個點，會使搜索樹的深度加大，而且因為其他位置劫才會影響劫的輸贏，劫才之間又相互影響，有可能打劫中又產(chǎn)生新的劫?？傊?，打劫規(guī)則會使圍棋的復(fù)雜度加大。

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

13、遇強則強，遇弱則弱？

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

14、AlphaGo下棋為什么花錢？

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

15、AlphaGo有漏洞嗎？

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

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

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

16、AlphaGo有哪些技術(shù)突破，使她能戰(zhàn)勝人類頂尖棋手？

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

⑵在學(xué)習(xí)policy中使用了監(jiān)督學(xué)習(xí)，有效的利用現(xiàn)有的棋手的棋譜，學(xué)到了他們的選點策略。

⑶在學(xué)習(xí)policy中使用了增強學(xué)習(xí)，從左右互搏中提高自己。

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

⑸在學(xué)習(xí)policy， value， rollout中使用深度學(xué)習(xí)模型。深度學(xué)習(xí)有非常強的學(xué)習(xí)能力。使得選點和形勢判斷前所未有的準（對比蒙特卡洛是隨機選點，現(xiàn)在是職業(yè)棋手幫她選點了）。因為在每次模擬中用到了這兩個“準”，使得在樹搜索（就是推演）的過程更有目的性（樹大量減枝，只模擬比較優(yōu)良的下法）

⑹當然還有機器一貫的優(yōu)勢，不疲勞，不受心理情緒影響，不會錯的記憶力等等。