6
| 本文作者： Ticwear | 2016-03-11 14:39 | 專題：人工智能和李世石的世紀之戰(zhàn) |
【編者按】作者李理，出門問問NLP工程師。本文原標題：AlphaGo的棋局，與人工智能有關(guān)，與人生無關(guān)。
之前我們說了MCTS回避了局面估值的問題，但是人類下圍棋顯然不是這樣的，所以真正要下好圍棋，如此從模仿人類的角度來說，這個問題是繞不過去的。人類是怎么學習出不同局面的細微區(qū)別的呢？當然不能由人來提取特征或者需要人來編寫估值函數(shù)，否則還是回到之前的老路上了。我們的機器能自動學習而不需要領(lǐng)域的專家手工編寫特征或者規(guī)則來實現(xiàn)估值函數(shù)呢？
眼下最火熱的深度學習也許可以給我們一條路徑（當然可能還有其它路徑，但深度學習目前看起來解決feature的自動學習是最promising的方法之一）。
在機器學習流行之前，都是基于規(guī)則的系統(tǒng)，因此做語音的需要了解語音學，做NLP的需要很多語言學知識，做深藍需要很多國際象棋大師。
而到后來統(tǒng)計方法成為主流之后，領(lǐng)域知識就不再那么重要，但是我們還是需要一些領(lǐng)域知識或者經(jīng)驗來提取合適的feature，feature的好壞往往決定了機器學習算法的成敗。對于NLP來說，feature還相對比較好提取，因為語言本身就是高度的抽象；而對于Speech或者Image來說，我們?nèi)祟愖约阂埠茈y描述我們是怎么提取feature的。比如我們識別一只貓，我們隱隱約約覺得貓有兩個眼睛一個鼻子有個長尾巴，而且它們之間有一定的空間約束關(guān)系，比如兩種眼睛到鼻子的距離可能差不多。但怎么用像素來定義”眼睛“呢？如果仔細想一下就會發(fā)現(xiàn)很難。當然我們有很多特征提取的方法，比如提取邊緣輪廓等等。
但是人類學習似乎不需要這么復雜，我們只要給幾張貓的照片給人看，他就能學習到什么是貓。人似乎能自動”學習“出feature來，你給他看了幾張貓的照片，然后問題貓有什么特征，他可能會隱隱預約的告訴你貓有什么特征，甚至是貓?zhí)赜械奶卣鳎@些特征豹子或者老虎沒有。
深度學習為什么最近這么火，其中一個重要的原因就是不需要（太多）提取feature。
從機器學習的使用者來說，我們以前做的大部分事情是feature engineering，然后調(diào)一些參數(shù)，一般是為了防止過擬合。而有了深度學習之后，如果我們不需要實現(xiàn)一個CNN或者LSTM，那么我們似乎什么也不用干。
CNN最早是Yann Lecun提出用來解決圖像識別的問題的一種深度神經(jīng)網(wǎng)絡。由Yann LeCun提出，通過卷積來發(fā)現(xiàn)位置無關(guān)的feature，而且這些feature的參數(shù)是相同的，從而與全連接的神經(jīng)網(wǎng)絡相比大大減少了參數(shù)的數(shù)量。
CNN深度神經(jīng)網(wǎng)絡
因此CNN非常適合圍棋這種feature很難提取問題，比如圖像識別。用CNN來嘗試圍棋的局面評估似乎也是很自然的想法。
之前也分析過了，圍棋搜索如果不到游戲結(jié)束，深的局面并不比淺的容易評估，所以我們不需要展開搜索樹，而可以直接評估一個局面下不同走法的好壞。這樣做的好處是很容易獲得訓練數(shù)據(jù)。我們有大量人類圍棋高手的對局（海量中等水平的對局），每一個局面下“好”的走法直接就能夠從高手對局庫里得到，認為他們的對局都是“好”的走法。但是要得到一個局面的“絕對”得分卻很難，因為我們只知道一盤對局最終的結(jié)果。一盤游戲最終的勝負可能是因為布局就下得很好，也可能是因為最后的官子階段下得好，中間具體某個局面的好壞是很難判斷的（當然強化學習試圖解決這個問題，但是還是很難的，下面在討論AlphaGo的時候會有涉及）。對于一個局面，如果能知道這個局面下最好的走法（或者幾個走法），那么我們對弈時就直接選擇這個走法（當然這個最好的走法可能得分也很差，比如敗局已定的情況下怎么走都是輸）。
所以大部分研究都是用CNN來預測一個局面下最好的走法?！绢A測走法比估值一個局面容易，如果我們能夠準確估值局面，那么最佳走法就是從走之后的局面中選擇對自己最有利的走法。或者用我們做問答系統(tǒng)常用的比喻，預測走法是搜索引擎，局面評估是問答系統(tǒng)。搜索引擎只要把好的排前面就行了（甚至不一定要求排在第一，排在第一頁也就差不多了），而問答不僅要把好的排前面，而且還要知道這個最“好”的結(jié)果是否足夠“好”，因為排序的好是相對“好”，問答的好必須是絕對的“好”，是唯一正確答案】。
最早用CNN（當然還有用其它機器學習方法）來預測走法是2003年Van Der Werf等人的工作，他們用了很多手工構(gòu)造的feature和預處理方法，他們?nèi)〉昧?5%的預測準確率。沒有細看論文，在2006年Deep Learning火之前，所以估計網(wǎng)絡的層次很淺。
之后在2008年，這個時候Deep的神經(jīng)網(wǎng)絡已經(jīng)逐漸流行了。Sutskever & Nair用來2層的CNN，第一層有15個7*7的filter，第二層用了5*5的filter，最后用了一個softmax層，輸出19*19，表示每個可能走法的概率（當然需要后處理去掉不合法或者不合理的走法，比如違反棋規(guī)的打劫局面立即提回，或者在自己的眼里下棋）。他們得到了34%的預測準確率。不過有一點問題就是他們出來使用當前局面，還用了上一步走法（這個走子導致了當前局面，也就是對手的上一步走子），這個可能是有問題的，因為實際對局時對手的水平是不能確定的，用這個feature當然能提高“數(shù)字”上的準確率，但是對于下棋水平是否有負面影響是很難說的。
到了2015年，計算機的計算能力更強，深度神經(jīng)網(wǎng)絡的層次也越來越深，在圍棋領(lǐng)域也能看到這種趨勢。Clark & Storkey使用了8層的CNN，用的特征包括最原始的棋子（用了3個feature plane，表示361個點是黑棋/白棋/空白），ko（劫）的約束，一個group（塊）的氣。包括使用很多trick來保證symmetries（因為圍棋的局面旋轉(zhuǎn)90/180/270/360度后以及做180度的鏡像之后應該是一樣的）。他們在GoGoD數(shù)據(jù)上的預測準確率達到了41.1%，在KGS數(shù)據(jù)上的準確率達到44.4%。GoGoD上大部分是職業(yè)選手的對局，而KGS數(shù)據(jù)有很多業(yè)余高手的對局。
光是預測準確率，并不能說明下棋的水平。因此Maddison等人的工作把Move Prediction用到了實際的對弈當中。
他們的CNN增加到了12層，feature也有所增加，下面是他們使用的feature。
第一組feature是棋子（Stone）的顏色，和之前一樣。
第二組是棋子（所在group）的氣，用4個plane來表示，分別是1，2，3 >=4口氣。
第三組是走了這步棋之后的氣，用了6個plane，代表1，2，3，4，5，>=6口氣。
第四組表示這個走法在當前局面是否合法。
第五組表示這個棋子距離當前局面的輪次，比如上一步對手走的就是1，上上一步自己走的就是2。因為圍棋很多都是局部的戰(zhàn)役，所以這個feature應該是有用的。
第六組就是表示走這這后能吃對方多少個棋子。
第七組表示走這能否征子成功。
第八組feature比較有趣，按照作者的說法就是因為KGS的對弈水平參差不齊，如果只留下高手的對局數(shù)據(jù)太少，所以用這個feature。
他們在KGS數(shù)據(jù)上的預測準確率達到55%。相對于Clark等人的工作，Maddison的工作除了增加了CNN的層次（8到12），增加的feature應該是很有幫助的，比如Turns Since，Capture Size和Ladder Move。尤其是Ladder Move，下過圍棋的都知道征子能否成功對應是否要走這步棋已經(jīng)局部的計算非常重要。
根據(jù)他們的使用，人類6d的預測準確率也只有52%，所以從預測走法的角度來說，CNN的水平已經(jīng)達到了6d的水平。
另外他們還做了實驗，證明Clark那些用來保證symmetry的tricky并沒有什么卵用，直接簡單粗暴的把數(shù)據(jù)做symmetric變換后訓練就行了。
完全不用搜索直接用Move Prediction的結(jié)果下棋，能97%的比率戰(zhàn)勝GnuGo（這個是完全基于alpha-beta搜索的），作者并沒有說明只用Move Prediction的絕對水平，而只是和很差的GnuGo比較，所以應該水平不怎么樣。
加上MCTS之后他們的水平能達到主流MCTS的開源軟件如Pachi何Fuego的水平。當然CNN的預測相對于Simulation來說是很慢的，他們的GPU（4個GeForce GTX Titan Black）評估128個局面需要0.15s，而CPU（16 Intel Xeon E52643 v2 3.5GHz）每秒可以simulation 47,000個局面。所以他們使用了異步的策略，先用先驗知識給出一個節(jié)點的N(v),Q(v)，先搜索著，等GPU運算完了再用CNN預測的勝率更新這些統(tǒng)計量。因此CPU和GPU的速度需要能大致匹配。
和Google DeepMind進行圍棋競賽的主要就是Facebook Tian yuandong他們了。在Google宣布文章在Nature發(fā)表的前一天，他們在arxiv上發(fā)表了自己的工作。
下面我們來看看他們的工作（《Better Computer Go Player with Neural Network and Long-Term Prediction》）。
使用的feature：
除了使用之前工作的標準feature之外，他們增加了一些feature，比如是否邊界，距離中心的遠近，是否靠近自己與對手的領(lǐng)土（不清楚怎么定義領(lǐng)土的歸屬的）。此外對于之前的feature也進行了壓縮，之前都把特征分成黑棋或者白棋，現(xiàn)在直接變成己方和對手，這樣把模型從兩個變成了一個（之前需要給黑棋和白棋分別訓練一個模型）。此外的一個不同地方就是類似于Multi-task的learning，同時預測未來3步棋的走法（而不是1步棋走法）。
為了與Maddison的工作比較，這里只用了標準的features，比較的也是未來1步棋的準確率，可以發(fā)現(xiàn)這個方法還是有效的（不過我個人覺得作者應該自己復現(xiàn)Maddison的結(jié)果而不是直接用他的結(jié)果）
只使用DCNN的圍棋軟件（不用MCTS搜索）
darkforest: 標準的feature，一步的預測，使用KGS數(shù)據(jù)
darkforest1：擴展的feature，三步預測，使用GoGoD數(shù)據(jù)
darkforest2：基于darkforest1，fine-tuning了一下參數(shù)。
把它們放到KGS上比賽，darkforest能到1k-1d的水平，darkforest1能到2d的水平，darkforest2能到3d的水平【注：KGS的3d應該到不了實際的業(yè)余3段】，下面是具體的情況。
因此作者認為加入3步預測的訓練是有效的。
Tree Policy: 走法首先通過DCNN排序，然后按順序選擇，除非累計的概率超過0.8或者超過一定次數(shù)的top走法。Expansion使用的UCT算法。
Default Policy:參考的Pachi的tree policy，有3*3的pattern，對手打吃的點（opponent atari point），點眼的檢測（detection of nakade points）等。
這個版本的軟件叫darkforest3，在KGS上能到5d的水平。
DCNN預測的top3/5的走法可能不包含局部戰(zhàn)役的一個關(guān)鍵點，所以它的局部作戰(zhàn)能力還比較弱。
對于一些打劫點即使沒用，DCNN還是會給高分。
當局面不好的情況下，它會越走越差（這是MCTS的弱點，因為沒有好的走法，模擬出來都是輸棋，一些比較頑強的抵抗的走法不能走出來）。
從上面的分析可以看出：DCNN給出的走法大局觀還是不錯的，這正是傳統(tǒng)的方法很難解決的問題。局部的作戰(zhàn)更多靠計算，MCTS會有幫助。但是我個人覺得MCTS搜索到結(jié)束，沒有必要。一個局部的計算也許可以用傳統(tǒng)的alpha-beta搜索來解決，比如征子的計算，要看6線有沒有對手的棋子，另外即使有對手的棋子，也要看位置的高低，這樣的計算DCNN是沒法解決的，需要靠計算。
終于輪到主角上陣了，您可能不耐煩了。不過有了前面的基礎，理解AlphaGo就容易多了，這里我們主要分析AlphaGo的創(chuàng)新點。
上圖是AlphaGo所使用的兩個網(wǎng)絡以及訓練過程。和之前的工作比，除了Policy Network之外，AlphaGo多了一個Value Network。
Policy Network我們通過之前的介紹以及了解到了，它的作用是Tree Policy時候的Node Selection。（rollout階段不能使用Policy Network，因為DCNN的計算速度相對于Simulation來說太慢，所以AlphaGo又訓練了一個簡單的Rollout Policy，它基于一些local的pattern之類的feature訓練了一個線性的softmax）。
那么Value Network又是做什么用的呢？這個Value Network就是我們之前說的很多工作都“回避”的問題——給一個局面打分，就是之前在象棋和minimax部分討論的局面的估值函數(shù)，只不過AlphaGo是使用深度強化學習(deep reinforcment learning)學習出來，而不是像Deep Blue或者其它象棋程序那樣是人工提取的feature甚至手工調(diào)整權(quán)重（當然Deep Blue是很多年前的工作了，現(xiàn)在也有用深度強化學習來搞國際象棋的，比如這篇論文《Giraffe: Using Deep Reinforcement Learning to Play Chess》）。
前面在討論Tian等人的工作時我們也分析過了，光用Move Prediction的軟件大局觀還不錯，但是局部的戰(zhàn)術(shù)就比較差，因為局部的戰(zhàn)術(shù)更多靠計算，人類也是這樣。圍棋由于估值函數(shù)比較困難，所以大都是用MCTS搜索到游戲結(jié)束。但是MCTS如果盲目搜索（使用隨機的default policy去rollout/playout）肯定不好，使用各種領(lǐng)域知識來縮小rollout的范圍就非常重要。前面我們也看到，傳統(tǒng)的MCTS只能到2d的水平，而用DCNN的tree policy的MCTS就能到5d的水平（如果default policy如果能用DCNN指導肯定更好，可惜DCNN的速度太慢）。
這個和之前介紹的差不了太多。AlphaGo相比之前多了Rollout Policy，之前的Rollout Policy大多是使用手工編制的pattern，而AlphaGo用訓練Policy Network相同的數(shù)據(jù)訓練了一個簡單的模型來做Rollout。
訓練數(shù)據(jù)來自3千萬的KGS的數(shù)據(jù)，使用了13層的CNN，預測準確率是57%，這和之前Tian等人的工作是差不多的。
之前訓練的SL Policy Network優(yōu)化的目標是預測走法，作者認為人類的走法會在很多promising的走法里選擇，這不一定能提高AlphaGo的下棋水平。為什么？文中沒有解釋，我個人認為可能是一個局面（尤其是優(yōu)勢）的情況下有很多走法，有保守一點但是保證能贏一點點的走法，也有激進但需要算度準確的但能贏很多的走法。這取決于個人的能力（比如官子能力怎么樣）和當時的情況（包括時間是否寬裕等等）。
所以AlphaGo使用強化學習通過自己跟自己對弈來調(diào)整參數(shù)學習更適合自己的Policy。
具體的做法是當前版本跟之前的某一個版本（把之前所有版本都保留和不是用最近的一個可以避免overfitting）對弈，對弈的走法是根據(jù)Policy Network來選擇的，然后根據(jù)結(jié)果調(diào)整參數(shù)。這個公式用自然語言來描述就是最終得分z_t(獲勝或者失敗)，在t時刻局面是s_t我選擇了走法a_t，P(a_t|s_t)表示局面s_t時選擇走法a_t的概率，就像神經(jīng)網(wǎng)絡的反向傳播算法一樣，損失z_t(或者收益)是要由這個走法來負責的。我們調(diào)整參數(shù)的目的就是讓這個概率變小。再通俗一點說就是，比如第一步我們的模型說必須走馬(概率是1)，那么如果最終輸棋，我們復盤時可能會覺得下次走馬的概率應該少一點，所以我們調(diào)整參數(shù)讓走馬的概率小一點（就是這個梯度）。
RL Policy Network的初始參數(shù)就是SL Policy Network的參數(shù)。最后學到的RL Policy Network與SL Policy Network對弈，勝率超過80%。
另外RL Policy Network與開源的Pachi對弈（這個能到2d也就是業(yè)余兩段的水平），Pachi每步做100,000次Simulation，RL Policy Network的勝率超過85%，這說明不用搜索只用Move Prediction能超過2d的水平。這和Tian等人的工作的結(jié)論是一致的，他們的darkforest2也只用Move Prediction在KGS上也能到3d的水平。
一個局面在policy p下的估值公式。用通俗的話說就是：在t時刻的局面是s，然后我們用p來下棋直到游戲結(jié)束，我們重復很多次，然后求平均的得分。當然，最理想的情況是我們能知道雙方都是最優(yōu)策略下的得分，可惜我們并不知道，所以只能用我們之前學到的SL Policy Network或者RL Policy Network來估計一個局面的得分，然后訓練一個Value Network V(s)。前面我們也討論過了，RL Policy Network勝率更高，而我們學出來的Value Network是用于rollout階段作為先驗概率的，所以AlphaGo使用了RL Policy Network的局面評估來訓練V(s)。
V(s)的輸入時一個局面，輸出是一個局面的好壞得分，這是一個回歸問題。AlphaGo使用了和Policy Network相同的參數(shù)，不過輸出是一個值而不是361個值（用softmax歸一化成概率）。
上面的公式說明：V(s)的參數(shù)theta就是簡單的用梯度下降來訓練
不過用一盤對局的所有(s,v(s))訓練是有問題的，因為同一盤對局的相鄰的局面是非常相關(guān)的，相鄰的局面只差一個棋子，所有非常容易overfitting，導致模型“記住”了局面而不是學習到重要的feature。作者用這樣的數(shù)據(jù)訓練了一個模型，在訓練數(shù)據(jù)上的MSE只有0.19，而在測試數(shù)據(jù)上是0.37，這明顯overfitting了。為了解決這個問題，作者用RL Policy Network自己跟自己對局了3千萬次，然后每個對局隨機選擇一個局面，這樣得到的模型在訓練數(shù)據(jù)和測試數(shù)據(jù)上的MSE是0.226和0.234，從而解決了overfitting的問題。
上面花了大力氣訓練了SL Policy Network,Rollout Policy和Value Network，那么怎么把它們?nèi)诤系組CTS中呢？
一次MCTS的Simulation可以用上圖來說明，下文加黑的地方是這三個模型被用到的地方。
首先每個節(jié)點表示一個局面，每一條邊表示局面+一個合法的走法(s,a)。每條邊保存Q(s,a)，表示MCTS當前累計的reward，N(s,a)表示這條邊的訪問次數(shù)，P(s,a)表示先驗概率。
每次Simulation使用如下的公式從根節(jié)點開始一直選擇邊直到葉子節(jié)點（也就是這條邊對于的局面還沒有expand）。
Q(s_t,a)就是exploit term，而u(s_t,a)就是explore term，而且是于先驗概率P(s,a)相關(guān)的，優(yōu)先探索SL Policy Network認為好的走法。
對于葉子節(jié)點，AlphaGo不僅僅使用Rollout(使用Rollout Policy)計算得分，而且也使用Value Network打分，最終把兩個分數(shù)融合起來：
n次Simulation之后更新統(tǒng)計量（從而影響Selection），為什么是n次，這涉及到多線程并行搜索以及運行與GPU的Policy Network與Value Network與CPU主搜索線程通信的問題
一個邊的訪問次數(shù)超過一定閾值后展開這個邊對應的下一個局面。閾值會動態(tài)調(diào)整以是的CPU和GPU的速度能匹配，具體下一節(jié)我們討論AlphaGo的實現(xiàn)細節(jié)再說明
a圖是用分布式的AlphaGo，單機版的AlphaGo，CrazyStone等主流圍棋軟件進行比賽，然后使用的是Elo Rating的打分。
作者認為AlphaGo的水平超過了FanHui（2p)，因此AlphaGo的水平應該達到了2p（不過很多人認為目前Fanhui的水平可能到不了2p）。
b圖說明了Policy Network Value Network和Rollout的作用，做了一些實驗，去掉一些的情況下棋力的變化，結(jié)論當然是三個都很重要。
c圖說明了搜索線程數(shù)以及分布式搜索對棋力的提升，這些細節(jié)我們會在下一節(jié)再討論，包括AlphaGO的架構(gòu)能不能再scalable到更多機器的集群從而提升棋力。
因為3月份AlphaGo要挑戰(zhàn)李世石，所以大家都很關(guān)心AlphaGo到底到了什么水平。當然它的真實水平只有作者才能知道，我這里都是根據(jù)一些新聞的推測。而且從文章提交Nature審稿到3月份比賽還有一段不短的時間，AlphaGo能不能還有提高也是非常關(guān)鍵。這里我只是推測一下在文章提交Nature時候AlphaGo的棋力。至于AlphaGo棋力能否提高，我們下一節(jié)分析實現(xiàn)細節(jié)時再討論（假設整體架構(gòu)不變，系統(tǒng)能不能通過增加機器來提高棋力）。
網(wǎng)上很多文章試圖通過AlphaGo與fanhui的對局來估計AlphaGo的棋力，我本人不敢發(fā)表意見。我只是搜索了一些相關(guān)的資料，主要是在弈城上一個叫DeepMind的賬號的對局信息來分析的。
比如這篇《金燦佑分析deepmind棋譜認為99%與谷歌團隊相關(guān)》。作者認為這個賬號就是AlphaGo。如果猜測正確的話，AlphaGo當時的棋力在弈城8d-9d直接，換成我們常用的ranking system的話大概也就是6d-7d（業(yè)余6段到7段）的水平，如果發(fā)揮得好，最多也許能到1p的水平，戰(zhàn)勝fanhui也有一定合理性（很多人認為fanhui目前實際水平可能已經(jīng)沒有2p了，那算1p的話也差不多）。
知乎上也有很多討論，以及這篇《陳經(jīng)：谷歌圍棋算法存在缺陷》，都可以參考。
和之前類似，搜索樹的每個狀態(tài)是s，它包含了所有合法走法(s,a)，每條邊包含如下的一些統(tǒng)計量：
P(s,a)是局面s下走a的先驗概率。Wv(s,a)是simulation時value network的打分，Wr(s,a)是simulation時rollout的打分。Nv(s,a)和Nr(s,a)分別是simulation時value network和rollout經(jīng)過邊(s,a)的次數(shù)。Q(s,a)是最終融合了value network打分和rollout打分的最終得分。
rollout會模擬一個節(jié)點多次這比較好理解。為什么value network會給同一個節(jié)點打分多次呢？而且對于一個DCNN來說，給定一個固定的輸入(s,a) P(a|s)不應該是相同的值嗎，計算多次有什么意義嗎？
我剛開始看了半天也沒明白，后來看到Symmetries那部分才明白。原來AlphaGo沒有像之前的工作那樣除了對稱的問題，對于APV-MCTS（Asynchronous Policy and Value MCTS)算法，每次經(jīng)過一個需要rollout的(s,a)時，會隨機的選擇8個對稱方向中的一個，然后計算p(a|s)，因此需要平均這些value。計算Policy Network的機器會緩存這些值，所以Nv(s,a)應該小于等于8。
還是這個圖。
從根節(jié)點開始使用下面的公式選擇a直到葉子節(jié)點。
Q(s,a)初始值為0，后面Backup部分會講怎么更新Q(s,a)。
現(xiàn)在我們先看這個公式，第一部分Q(s,a)是exploit term，第二部分是explore term。這個公式開始會同時考慮value高的和探索次數(shù)少的走法，但隨著N(s,a)的增加而更傾向于value高的走法。
葉子節(jié)點sL被加到一個隊列中等到value network計算得分（異步的），然后從sL開始使用rollout policy模擬對局到游戲結(jié)束。
在Simulation開始之前，把從根一直到sL的所有的(s,a)增加virtual loss，這樣可以防止（準確的說應該是盡量不要，原文用的詞語是discourage，當然如果其它走法也都有線程在模擬，那也是可以的）其它搜索線程探索相同的路徑。
上面的給(s,a)增加virtual 的loss，那么根據(jù)上面選擇的公式，就不太會選中它了。
當模擬結(jié)束了，需要把這個virtual loss去掉，同時加上這次Simulation的得分。
此外，當GPU算完value的得分后也要更新：
最終算出Q(s,a):
當一條邊(s,a)的訪問次數(shù)Nr(s,a)【提個小問題，為什么是Nr(s,a)而不是Nv(s,a)？】超過一個閾值Nthr時會把這條邊的局面（其實就是走一下這個走法）s’=f(s,a)加到搜索樹里。
初始化統(tǒng)計量：Nv(s’,a)=0, Nr(s’,a)=0, Wv(s’,a)=0, Wr(s’,a)=0, P(s’,a)=P(a|s’)
由于計算P(a|s’)需要在GPU中利用SL Policy Network計算，比較慢，所以先給它一個place-holder的值，等到GPU那邊算完了再更新。
這個place-holder的值使用和rollout policy類似的一個tree policy計算出來的（用的模型了rollout policy一樣，不過特征稍微豐富一些，后面會在表格中看到），在GPU算出真的P(a|s’)之前的selection都是先用這個place-holder值，所以也不能估計的太差。因此AlphaGO用了一個比rollout feature多一些的模型。
Expansion的閾值Nthr會動態(tài)調(diào)整，目的是使得計算Policy Network的GPU能夠跟上CPU的速度。
一臺Master機器執(zhí)行主搜索（搜索樹的部分），一個CPU集群進行rollout的異步計算，一個GPU集群進行Policy和Value Network的異步計算。
整個搜索樹都存在Master上，它只負責Selection和Place-Holder先驗的計算以及各種統(tǒng)計量的更新。葉子節(jié)點發(fā)到CPU集群進行rollout計算，發(fā)到GPU集群進行Policy和Value Network的計算。
最終，AlphaGo選擇訪問次數(shù)最多的走法而不是得分最高的，因為后者對野點(outlier)比較敏感。走完一步之后，之前搜索過的這部分的子樹的統(tǒng)計量直接用到下一輪的搜索中，不屬于這步走法的子樹直接扔掉。另外AlphaGo也實現(xiàn)了Ponder，也就是對手在思考的時候它也進行思考。它思考選擇的走法是比較“可疑”的點——最大訪問次數(shù)不是最高得分的走法。AlphaGo的時間控制會把思考時間盡量留在中局，此外AlphaGo也會投降——當它發(fā)現(xiàn)贏的概率低于10%，也就是 MAXaQ(s,a) < -0.8。
AlphaGo并沒有想常見的圍棋那樣使用AMAF或者RAVE啟發(fā)，因為這些策略并沒有什么用處，此外也沒有使用開局庫，動態(tài)貼目(dynamic komi)等。
使用了兩大類pattern，一種是response的pattern，也就是上一步走法附近的pattern（一般圍棋很多走法都是為了“應付”對手的走子）；另一種就是非response的pattern，也就是將要走的那個走法附近的pattern。具體使用的特征見下表。Rollout Policy比較簡單，每個CPU線程每秒可以從空的局面（開局）模擬1000個對局。
橫線之上的feature用來rollout，所有的feature用來計算place-holder先驗概率。
前面在講Search Algorithm講過了。
SL Policy Network使用了29.4 million局面來訓練，這些局面來自KGS 6d-9d 的16萬個對局。使用了前1million用來測試，后面的28.4million用來訓練。此外進行了旋轉(zhuǎn)和鏡像，把一個局面變成8個局面。使用隨機梯度下降算法訓練，訓練的mini-batch大小是16。使用了50個GPU的DistBelief（并沒有使用最新的Tensorflow），花了3周的時間來訓練了340million次訓練步驟（每個mini-batch算一個步驟？）
每次用并行的進行n個游戲，使用當前版本(參數(shù))的Policy Network和之前的某一個版本的Policy Network。當前版本的初始值來自SL Policy Network。然后用 Policy Gradient來更新參數(shù)，這算一次迭代，經(jīng)過500次迭代之后，就認為得到一個新的版本把它加到Pool里用來和當前版本對弈。使用這種方法訓練，使用50個GPU，n=128，10,000次對弈，一天可以訓練完成RL Policy Network。
前面說了，訓練的關(guān)鍵是要自己模擬對弈然后隨機選擇局面而不是直接使用KGS的對局庫來避免overfitting。
AlphaGo生成了3千萬局面，也就是3千萬次模擬對弈，模擬的方法如下：
隨機選擇一個time-step U~unif{1,450}
根據(jù)SL Policy Network走1，2，… , U-1步棋
然后第U步棋從合法的走法中隨機選擇
然后用RL Policy Network模擬對弈到游戲結(jié)束
被作為一個訓練數(shù)據(jù)加到訓練集合里。
這個數(shù)據(jù)是
的一個無偏估計。
最后這個Value Network使用了50個GPU訓練了一周，使用的mini-batch大小是32。
其實和前面Tian的差不太多，多了兩個征子相關(guān)的feature，另外增加了一個常量1和常量0的plane。
最后一個feature 是value network用的，因為判斷局面得分時要知道是誰走的，這個很關(guān)鍵。
13層從CNN，輸入時19*19*48，第一個hidden層把輸入用零把輸入padding成23*23，然后用k個5*5的filter，stride是1。
2到12層首先用零把輸入padding成21*21，然后使用k個5*5的filter，stride依然是1。
最后一層用一個1*1的filter，然后用一個softmax。
比賽用的k=192，文章也做了一些實驗對比k=128,256,384的情況。
14層的CNN，前面12層和Policy Network一樣，第13層是一個filter的卷積層，第14層是全連接的Relu激活，然后輸出層是全連接的tanh單元。
不同分布式版本的水平比較，使用的是Elo rating標準。
從上面的細節(jié)來看，神經(jīng)網(wǎng)絡的訓練其實用的時間和機器不多，真正非資源的還是在搜索階段。
最強的AlphaGo使用了64個搜索線程，1920個CPU的集群和280個GPU的機器（其實也就二十多臺機器）
之前我們討論過分布式MCTS時說過，MCTS很難在多機上并行，所以AlphaGo還是在一臺機器上實現(xiàn)的LockFree的多線程并行，只不過Rollout和神經(jīng)網(wǎng)絡計算是在CPU和GPU集群上進行的。Google的財力肯定不只二三十臺機器，所以分布式MCTS的搜索才是最大的瓶頸。如果這個能突破，把機器堆到成百上千臺應該還是能提高不少棋力的。
我個人估計在3月與李世石的對弈中這個架構(gòu)可能還很難有突破，可以增強的是RL Policy的自對弈學習，不過這個提升也有限（否則不會只訓練一天就停止了，估計也收斂的差不多了）
所以我個人的觀點是3月份要戰(zhàn)勝李世石還是難度比較大的。
之前我們討論的都是完全信息的兩人的零和博弈游戲。用的minimax也是假設對手都是走最優(yōu)的走法，但實際比賽中可能并非如此。
比如為了爭勝，我們可能走一些冒險的策略，這個策略下如果對手走到最佳的走法我們可能會輸。但是由于局面復雜，稍有不慎可能就會走錯，那么我們的目的就達到了。
還有就是多人的博弈，比如斗地主，我們可能還得對多個對手或者隊友建模。比如地主最后一張牌是否要炸，還得看隊友的接牌能力。
又比如你陪領(lǐng)導玩斗地主，另外一個人明顯目的是來給領(lǐng)導送錢的，那么你的策略可能也需要調(diào)整。
這可能就是現(xiàn)實世界和人工智能的差別了。有些事情，機器永遠也不會懂，比如人生。
對于人生，每個人都像一顆棋子，那么誰是下棋者呢，他又是和誰在下棋呢？
我們在下棋的時候更多的考慮是全局的利益，比如用一個兵卒換一個馬炮我們會非常開心，但是作為要犧牲的兵卒來說呢？一將功成萬骨枯。
人生如棋，落子無悔。等到游戲結(jié)束的時候我們來復盤，才能發(fā)現(xiàn)當年犯下的錯誤，不過畢竟于事無補，只能給后人一些經(jīng)驗教訓罷了。
[1] D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. Van Den Driessche, J. Schrittwieser, I. Antonoglou, V. Panneershelvam, M. Lanctot, S. Dieleman, D. Grewe, J. Nham, N. Kalchbrenner, I. Sutskever, T. Lillicrap, M. Leach, K. Kavukcuoglu, T. Graepel, and D. Hassabis, Mastering the game of Go with deep neural networks and tree search, Nature, 2016
[2] M. Lai, Giraffe: Using Deep Reinforcement Learning to Play Chess, arXiv. 2015
[3] Reinforcement Learning: An Introduction. Richard S. Sutton and Andrew G. Barto MIT Press, Cambridge, MA, 1998 A Bradford Book
[4] C. Browne , E. Powley , D. Whitehouse , S. Lucas , P. Cowling , P. Rohlfshagen , S. Tavener , D. Perez , S. Samothrakis and S. Colton, “A survey of Monte Carlo tree search methods”, IEEE Trans. Comput. Intell. AI Games, vol. 4, no. 1, pp. 1-43, 2012
[5] H. Baier and P. D. Drake, “The power of forgetting: Improving the last-good-reply policy in Monte Carlo Go”, IEEE Trans. Comput. Intell. AI Games, vol. 2, no. 4, pp. 303-309, 2010
[6] A. Bourki , G. M. J.-B. Chaslot , M. Coulm , V. Danjean , H. Doghmen , J.-B. Hoock , T. Hérault , A. Rimmel , F. Teytaud , O. Teytaud , P. Vayssière and Z. Yu, “Scalability and parallelization of Monte-Carlo tree search”, Proc. Int. Conf. Comput. Games, pp. 48-58, 2010
[7] M. Enzenberger , M. Müller , B. Arneson and R. B. Segal, “Fuego—An open-source framework for board games and Go engine based on Monte Carlo tree search”, IEEE Trans. Comput. Intell. AI Games, vol. 2, no. 4, pp. 259-270, 2010
[8] M. Enzenberger and M. Müller, “A lock-free multithreaded Monte-Carlo tree search algorithm”, Proc. Adv. Comput. Games, vol. 6048, pp. 14-20, 2010
[9] L. Kocsis and C. Szepesvári, “Bandit based Monte-Carlo planning”, Proc. Eur. Conf. Mach. Learn., pp. 282-293, 2006
[10] Baudis, P. & Gailly, J.-L. Pachi: State of the art open source Go program. In ˇ Advances in Computer Games, 24–38 (Springer, 2012).
[11] Sutskever, I. & Nair, V. Mimicking Go experts with convolutional neural networks. In International Conference on Artificial Neural Networks, 101–110 (2008).
[12] G. M. J.-B. Chaslot , C. Fiter , J.-B. Hoock , A. Rimmel and O. Teytaud, “Adding expert knowledge and exploration in Monte-Carlo tree search”, Proc. Adv. Comput. Games, vol. 6048, pp. 1-13, 2010
[13] R. Coquelin , Pierre-Arnaud and Munos, “Bandit algorithms for tree search”, Proc. Conf. Uncertainty Artif. Intell., pp. 67-74, 2007
[14] https://en.wikipedia.org/wiki/Minimax
[15] https://en.wikipedia.org/wiki/Branching_factor
[16] https://en.wikipedia.org/wiki/Go_ranks_and_ratings#Kyu_and_dan_ranks
[17] https://en.wikipedia.org/wiki/Alpha–beta_pruning
[18] https://www.zhihu.com/topic/20038840
[19] http://sports.sina.cn/others/qipai/2016-02-01/detail-ifxnzanm3922928.d.html?vt=4&wm=4007&cid=69557&node_id=77160
[20] Better Computer Go Player with Neural Network and Long-term Prediction. Yuandong Tian, Yan Zhu. arXiv. 2015
[21] Sutskever, I. & Nair, V. Mimicking Go experts with convolutional neural networks. In International Conference on Artificial Neural Networks, 101–110 (2008).
[22] Maddison, C. J., Huang, A., Sutskever, I. & Silver, D. Move evaluation in Go using deep convolutional neural networks. 3rd International Conference on Learning Representations (2015).
[23] Clark, C. & Storkey, A. J. Training deep convolutional neural networks to play go. In 32nd International Conference on Machine Learning, 1766–1774 (2015).
[24] Sutton, R., McAllester, D., Singh, S. & Mansour, Y. Policy gradient methods for reinforcement learning with function approximation. In Advances in Neural Information Processing Systems,1057–1063 (2000).
本文首發(fā)CSDN
雷峰網(wǎng)原創(chuàng)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見轉(zhuǎn)載須知。
專題
