6
| 本文作者： Ticwear | 2016-03-11 14:39 | 專(zhuān)題：人工智能和李世石的世紀(jì)之戰(zhàn) |
【編者按】作者李理，出門(mén)問(wèn)問(wèn)NLP工程師。本文原標(biāo)題：AlphaGo的棋局，與人工智能有關(guān)，與人生無(wú)關(guān)。
之前我們說(shuō)了MCTS回避了局面估值的問(wèn)題，但是人類(lèi)下圍棋顯然不是這樣的，所以真正要下好圍棋，如此從模仿人類(lèi)的角度來(lái)說(shuō)，這個(gè)問(wèn)題是繞不過(guò)去的。人類(lèi)是怎么學(xué)習(xí)出不同局面的細(xì)微區(qū)別的呢？當(dāng)然不能由人來(lái)提取特征或者需要人來(lái)編寫(xiě)估值函數(shù)，否則還是回到之前的老路上了。我們的機(jī)器能自動(dòng)學(xué)習(xí)而不需要領(lǐng)域的專(zhuān)家手工編寫(xiě)特征或者規(guī)則來(lái)實(shí)現(xiàn)估值函數(shù)呢？
眼下最火熱的深度學(xué)習(xí)也許可以給我們一條路徑（當(dāng)然可能還有其它路徑，但深度學(xué)習(xí)目前看起來(lái)解決feature的自動(dòng)學(xué)習(xí)是最promising的方法之一）。
在機(jī)器學(xué)習(xí)流行之前，都是基于規(guī)則的系統(tǒng)，因此做語(yǔ)音的需要了解語(yǔ)音學(xué)，做NLP的需要很多語(yǔ)言學(xué)知識(shí)，做深藍(lán)需要很多國(guó)際象棋大師。
而到后來(lái)統(tǒng)計(jì)方法成為主流之后，領(lǐng)域知識(shí)就不再那么重要，但是我們還是需要一些領(lǐng)域知識(shí)或者經(jīng)驗(yàn)來(lái)提取合適的feature，feature的好壞往往決定了機(jī)器學(xué)習(xí)算法的成敗。對(duì)于NLP來(lái)說(shuō)，feature還相對(duì)比較好提取，因?yàn)檎Z(yǔ)言本身就是高度的抽象；而對(duì)于Speech或者Image來(lái)說(shuō)，我們?nèi)祟?lèi)自己也很難描述我們是怎么提取feature的。比如我們識(shí)別一只貓，我們隱隱約約覺(jué)得貓有兩個(gè)眼睛一個(gè)鼻子有個(gè)長(zhǎng)尾巴，而且它們之間有一定的空間約束關(guān)系，比如兩種眼睛到鼻子的距離可能差不多。但怎么用像素來(lái)定義”眼睛“呢？如果仔細(xì)想一下就會(huì)發(fā)現(xiàn)很難。當(dāng)然我們有很多特征提取的方法，比如提取邊緣輪廓等等。
但是人類(lèi)學(xué)習(xí)似乎不需要這么復(fù)雜，我們只要給幾張貓的照片給人看，他就能學(xué)習(xí)到什么是貓。人似乎能自動(dòng)”學(xué)習(xí)“出feature來(lái)，你給他看了幾張貓的照片，然后問(wèn)題貓有什么特征，他可能會(huì)隱隱預(yù)約的告訴你貓有什么特征，甚至是貓?zhí)赜械奶卣?，這些特征豹子或者老虎沒(méi)有。
深度學(xué)習(xí)為什么最近這么火，其中一個(gè)重要的原因就是不需要（太多）提取feature。
從機(jī)器學(xué)習(xí)的使用者來(lái)說(shuō)，我們以前做的大部分事情是feature engineering，然后調(diào)一些參數(shù)，一般是為了防止過(guò)擬合。而有了深度學(xué)習(xí)之后，如果我們不需要實(shí)現(xiàn)一個(gè)CNN或者LSTM，那么我們似乎什么也不用干。
CNN最早是Yann Lecun提出用來(lái)解決圖像識(shí)別的問(wèn)題的一種深度神經(jīng)網(wǎng)絡(luò)。由Yann LeCun提出，通過(guò)卷積來(lái)發(fā)現(xiàn)位置無(wú)關(guān)的feature，而且這些feature的參數(shù)是相同的，從而與全連接的神經(jīng)網(wǎng)絡(luò)相比大大減少了參數(shù)的數(shù)量。
CNN深度神經(jīng)網(wǎng)絡(luò)
因此CNN非常適合圍棋這種feature很難提取問(wèn)題，比如圖像識(shí)別。用CNN來(lái)嘗試圍棋的局面評(píng)估似乎也是很自然的想法。
之前也分析過(guò)了，圍棋搜索如果不到游戲結(jié)束，深的局面并不比淺的容易評(píng)估，所以我們不需要展開(kāi)搜索樹(shù)，而可以直接評(píng)估一個(gè)局面下不同走法的好壞。這樣做的好處是很容易獲得訓(xùn)練數(shù)據(jù)。我們有大量人類(lèi)圍棋高手的對(duì)局（海量中等水平的對(duì)局），每一個(gè)局面下“好”的走法直接就能夠從高手對(duì)局庫(kù)里得到，認(rèn)為他們的對(duì)局都是“好”的走法。但是要得到一個(gè)局面的“絕對(duì)”得分卻很難，因?yàn)槲覀冎恢酪槐P(pán)對(duì)局最終的結(jié)果。一盤(pán)游戲最終的勝負(fù)可能是因?yàn)椴季志拖碌煤芎茫部赡苁且驗(yàn)樽詈蟮墓僮与A段下得好，中間具體某個(gè)局面的好壞是很難判斷的（當(dāng)然強(qiáng)化學(xué)習(xí)試圖解決這個(gè)問(wèn)題，但是還是很難的，下面在討論AlphaGo的時(shí)候會(huì)有涉及）。對(duì)于一個(gè)局面，如果能知道這個(gè)局面下最好的走法（或者幾個(gè)走法），那么我們對(duì)弈時(shí)就直接選擇這個(gè)走法（當(dāng)然這個(gè)最好的走法可能得分也很差，比如敗局已定的情況下怎么走都是輸）。
所以大部分研究都是用CNN來(lái)預(yù)測(cè)一個(gè)局面下最好的走法?！绢A(yù)測(cè)走法比估值一個(gè)局面容易，如果我們能夠準(zhǔn)確估值局面，那么最佳走法就是從走之后的局面中選擇對(duì)自己最有利的走法?；蛘哂梦覀冏鰡?wèn)答系統(tǒng)常用的比喻，預(yù)測(cè)走法是搜索引擎，局面評(píng)估是問(wèn)答系統(tǒng)。搜索引擎只要把好的排前面就行了（甚至不一定要求排在第一，排在第一頁(yè)也就差不多了），而問(wèn)答不僅要把好的排前面，而且還要知道這個(gè)最“好”的結(jié)果是否足夠“好”，因?yàn)榕判虻暮檬窍鄬?duì)“好”，問(wèn)答的好必須是絕對(duì)的“好”，是唯一正確答案】。
最早用CNN（當(dāng)然還有用其它機(jī)器學(xué)習(xí)方法）來(lái)預(yù)測(cè)走法是2003年Van Der Werf等人的工作，他們用了很多手工構(gòu)造的feature和預(yù)處理方法，他們?nèi)〉昧?5%的預(yù)測(cè)準(zhǔn)確率。沒(méi)有細(xì)看論文，在2006年Deep Learning火之前，所以估計(jì)網(wǎng)絡(luò)的層次很淺。
之后在2008年，這個(gè)時(shí)候Deep的神經(jīng)網(wǎng)絡(luò)已經(jīng)逐漸流行了。Sutskever & Nair用來(lái)2層的CNN，第一層有15個(gè)7*7的filter，第二層用了5*5的filter，最后用了一個(gè)softmax層，輸出19*19，表示每個(gè)可能走法的概率（當(dāng)然需要后處理去掉不合法或者不合理的走法，比如違反棋規(guī)的打劫局面立即提回，或者在自己的眼里下棋）。他們得到了34%的預(yù)測(cè)準(zhǔn)確率。不過(guò)有一點(diǎn)問(wèn)題就是他們出來(lái)使用當(dāng)前局面，還用了上一步走法（這個(gè)走子導(dǎo)致了當(dāng)前局面，也就是對(duì)手的上一步走子），這個(gè)可能是有問(wèn)題的，因?yàn)閷?shí)際對(duì)局時(shí)對(duì)手的水平是不能確定的，用這個(gè)feature當(dāng)然能提高“數(shù)字”上的準(zhǔn)確率，但是對(duì)于下棋水平是否有負(fù)面影響是很難說(shuō)的。
到了2015年，計(jì)算機(jī)的計(jì)算能力更強(qiáng)，深度神經(jīng)網(wǎng)絡(luò)的層次也越來(lái)越深，在圍棋領(lǐng)域也能看到這種趨勢(shì)。Clark & Storkey使用了8層的CNN，用的特征包括最原始的棋子（用了3個(gè)feature plane，表示361個(gè)點(diǎn)是黑棋/白棋/空白），ko（劫）的約束，一個(gè)group（塊）的氣。包括使用很多trick來(lái)保證symmetries（因?yàn)閲宓木置嫘D(zhuǎn)90/180/270/360度后以及做180度的鏡像之后應(yīng)該是一樣的）。他們?cè)贕oGoD數(shù)據(jù)上的預(yù)測(cè)準(zhǔn)確率達(dá)到了41.1%，在KGS數(shù)據(jù)上的準(zhǔn)確率達(dá)到44.4%。GoGoD上大部分是職業(yè)選手的對(duì)局，而KGS數(shù)據(jù)有很多業(yè)余高手的對(duì)局。
光是預(yù)測(cè)準(zhǔn)確率，并不能說(shuō)明下棋的水平。因此Maddison等人的工作把Move Prediction用到了實(shí)際的對(duì)弈當(dāng)中。
他們的CNN增加到了12層，feature也有所增加，下面是他們使用的feature。
第一組feature是棋子（Stone）的顏色，和之前一樣。
第二組是棋子（所在group）的氣，用4個(gè)plane來(lái)表示，分別是1，2，3 >=4口氣。
第三組是走了這步棋之后的氣，用了6個(gè)plane，代表1，2，3，4，5，>=6口氣。
第四組表示這個(gè)走法在當(dāng)前局面是否合法。
第五組表示這個(gè)棋子距離當(dāng)前局面的輪次，比如上一步對(duì)手走的就是1，上上一步自己走的就是2。因?yàn)閲搴芏喽际蔷植康膽?zhàn)役，所以這個(gè)feature應(yīng)該是有用的。
第六組就是表示走這這后能吃對(duì)方多少個(gè)棋子。
第七組表示走這能否征子成功。
第八組feature比較有趣，按照作者的說(shuō)法就是因?yàn)镵GS的對(duì)弈水平參差不齊，如果只留下高手的對(duì)局?jǐn)?shù)據(jù)太少，所以用這個(gè)feature。
他們?cè)贙GS數(shù)據(jù)上的預(yù)測(cè)準(zhǔn)確率達(dá)到55%。相對(duì)于Clark等人的工作，Maddison的工作除了增加了CNN的層次（8到12），增加的feature應(yīng)該是很有幫助的，比如Turns Since，Capture Size和Ladder Move。尤其是Ladder Move，下過(guò)圍棋的都知道征子能否成功對(duì)應(yīng)是否要走這步棋已經(jīng)局部的計(jì)算非常重要。
根據(jù)他們的使用，人類(lèi)6d的預(yù)測(cè)準(zhǔn)確率也只有52%，所以從預(yù)測(cè)走法的角度來(lái)說(shuō)，CNN的水平已經(jīng)達(dá)到了6d的水平。
另外他們還做了實(shí)驗(yàn)，證明Clark那些用來(lái)保證symmetry的tricky并沒(méi)有什么卵用，直接簡(jiǎn)單粗暴的把數(shù)據(jù)做symmetric變換后訓(xùn)練就行了。
完全不用搜索直接用Move Prediction的結(jié)果下棋，能97%的比率戰(zhàn)勝GnuGo（這個(gè)是完全基于alpha-beta搜索的），作者并沒(méi)有說(shuō)明只用Move Prediction的絕對(duì)水平，而只是和很差的GnuGo比較，所以應(yīng)該水平不怎么樣。
加上MCTS之后他們的水平能達(dá)到主流MCTS的開(kāi)源軟件如Pachi何Fuego的水平。當(dāng)然CNN的預(yù)測(cè)相對(duì)于Simulation來(lái)說(shuō)是很慢的，他們的GPU（4個(gè)GeForce GTX Titan Black）評(píng)估128個(gè)局面需要0.15s，而CPU（16 Intel Xeon E52643 v2 3.5GHz）每秒可以simulation 47,000個(gè)局面。所以他們使用了異步的策略，先用先驗(yàn)知識(shí)給出一個(gè)節(jié)點(diǎn)的N(v),Q(v)，先搜索著，等GPU運(yùn)算完了再用CNN預(yù)測(cè)的勝率更新這些統(tǒng)計(jì)量。因此CPU和GPU的速度需要能大致匹配。
和Google DeepMind進(jìn)行圍棋競(jìng)賽的主要就是Facebook Tian yuandong他們了。在Google宣布文章在Nature發(fā)表的前一天，他們?cè)赼rxiv上發(fā)表了自己的工作。
下面我們來(lái)看看他們的工作（《Better Computer Go Player with Neural Network and Long-Term Prediction》）。
使用的feature：
除了使用之前工作的標(biāo)準(zhǔn)feature之外，他們?cè)黾恿艘恍ゝeature，比如是否邊界，距離中心的遠(yuǎn)近，是否靠近自己與對(duì)手的領(lǐng)土（不清楚怎么定義領(lǐng)土的歸屬的）。此外對(duì)于之前的feature也進(jìn)行了壓縮，之前都把特征分成黑棋或者白棋，現(xiàn)在直接變成己方和對(duì)手，這樣把模型從兩個(gè)變成了一個(gè)（之前需要給黑棋和白棋分別訓(xùn)練一個(gè)模型）。此外的一個(gè)不同地方就是類(lèi)似于Multi-task的learning，同時(shí)預(yù)測(cè)未來(lái)3步棋的走法（而不是1步棋走法）。
為了與Maddison的工作比較，這里只用了標(biāo)準(zhǔn)的features，比較的也是未來(lái)1步棋的準(zhǔn)確率，可以發(fā)現(xiàn)這個(gè)方法還是有效的（不過(guò)我個(gè)人覺(jué)得作者應(yīng)該自己復(fù)現(xiàn)Maddison的結(jié)果而不是直接用他的結(jié)果）
只使用DCNN的圍棋軟件（不用MCTS搜索）
darkforest: 標(biāo)準(zhǔn)的feature，一步的預(yù)測(cè)，使用KGS數(shù)據(jù)
darkforest1：擴(kuò)展的feature，三步預(yù)測(cè)，使用GoGoD數(shù)據(jù)
darkforest2：基于darkforest1，fine-tuning了一下參數(shù)。
把它們放到KGS上比賽，darkforest能到1k-1d的水平，darkforest1能到2d的水平，darkforest2能到3d的水平【注：KGS的3d應(yīng)該到不了實(shí)際的業(yè)余3段】，下面是具體的情況。
因此作者認(rèn)為加入3步預(yù)測(cè)的訓(xùn)練是有效的。
Tree Policy: 走法首先通過(guò)DCNN排序，然后按順序選擇，除非累計(jì)的概率超過(guò)0.8或者超過(guò)一定次數(shù)的top走法。Expansion使用的UCT算法。
Default Policy:參考的Pachi的tree policy，有3*3的pattern，對(duì)手打吃的點(diǎn)（opponent atari point），點(diǎn)眼的檢測(cè)（detection of nakade points）等。
這個(gè)版本的軟件叫darkforest3，在KGS上能到5d的水平。
DCNN預(yù)測(cè)的top3/5的走法可能不包含局部戰(zhàn)役的一個(gè)關(guān)鍵點(diǎn)，所以它的局部作戰(zhàn)能力還比較弱。
對(duì)于一些打劫點(diǎn)即使沒(méi)用，DCNN還是會(huì)給高分。
當(dāng)局面不好的情況下，它會(huì)越走越差（這是MCTS的弱點(diǎn)，因?yàn)闆](méi)有好的走法，模擬出來(lái)都是輸棋，一些比較頑強(qiáng)的抵抗的走法不能走出來(lái)）。
從上面的分析可以看出：DCNN給出的走法大局觀還是不錯(cuò)的，這正是傳統(tǒng)的方法很難解決的問(wèn)題。局部的作戰(zhàn)更多靠計(jì)算，MCTS會(huì)有幫助。但是我個(gè)人覺(jué)得MCTS搜索到結(jié)束，沒(méi)有必要。一個(gè)局部的計(jì)算也許可以用傳統(tǒng)的alpha-beta搜索來(lái)解決，比如征子的計(jì)算，要看6線有沒(méi)有對(duì)手的棋子，另外即使有對(duì)手的棋子，也要看位置的高低，這樣的計(jì)算DCNN是沒(méi)法解決的，需要靠計(jì)算。
終于輪到主角上陣了，您可能不耐煩了。不過(guò)有了前面的基礎(chǔ)，理解AlphaGo就容易多了，這里我們主要分析AlphaGo的創(chuàng)新點(diǎn)。
上圖是AlphaGo所使用的兩個(gè)網(wǎng)絡(luò)以及訓(xùn)練過(guò)程。和之前的工作比，除了Policy Network之外，AlphaGo多了一個(gè)Value Network。
Policy Network我們通過(guò)之前的介紹以及了解到了，它的作用是Tree Policy時(shí)候的Node Selection。（rollout階段不能使用Policy Network，因?yàn)镈CNN的計(jì)算速度相對(duì)于Simulation來(lái)說(shuō)太慢，所以AlphaGo又訓(xùn)練了一個(gè)簡(jiǎn)單的Rollout Policy，它基于一些local的pattern之類(lèi)的feature訓(xùn)練了一個(gè)線性的softmax）。
那么Value Network又是做什么用的呢？這個(gè)Value Network就是我們之前說(shuō)的很多工作都“回避”的問(wèn)題——給一個(gè)局面打分，就是之前在象棋和minimax部分討論的局面的估值函數(shù)，只不過(guò)AlphaGo是使用深度強(qiáng)化學(xué)習(xí)(deep reinforcment learning)學(xué)習(xí)出來(lái)，而不是像Deep Blue或者其它象棋程序那樣是人工提取的feature甚至手工調(diào)整權(quán)重（當(dāng)然Deep Blue是很多年前的工作了，現(xiàn)在也有用深度強(qiáng)化學(xué)習(xí)來(lái)搞國(guó)際象棋的，比如這篇論文《Giraffe: Using Deep Reinforcement Learning to Play Chess》）。
前面在討論Tian等人的工作時(shí)我們也分析過(guò)了，光用Move Prediction的軟件大局觀還不錯(cuò)，但是局部的戰(zhàn)術(shù)就比較差，因?yàn)榫植康膽?zhàn)術(shù)更多靠計(jì)算，人類(lèi)也是這樣。圍棋由于估值函數(shù)比較困難，所以大都是用MCTS搜索到游戲結(jié)束。但是MCTS如果盲目搜索（使用隨機(jī)的default policy去rollout/playout）肯定不好，使用各種領(lǐng)域知識(shí)來(lái)縮小rollout的范圍就非常重要。前面我們也看到，傳統(tǒng)的MCTS只能到2d的水平，而用DCNN的tree policy的MCTS就能到5d的水平（如果default policy如果能用DCNN指導(dǎo)肯定更好，可惜DCNN的速度太慢）。
這個(gè)和之前介紹的差不了太多。AlphaGo相比之前多了Rollout Policy，之前的Rollout Policy大多是使用手工編制的pattern，而AlphaGo用訓(xùn)練Policy Network相同的數(shù)據(jù)訓(xùn)練了一個(gè)簡(jiǎn)單的模型來(lái)做Rollout。
訓(xùn)練數(shù)據(jù)來(lái)自3千萬(wàn)的KGS的數(shù)據(jù)，使用了13層的CNN，預(yù)測(cè)準(zhǔn)確率是57%，這和之前Tian等人的工作是差不多的。
之前訓(xùn)練的SL Policy Network優(yōu)化的目標(biāo)是預(yù)測(cè)走法，作者認(rèn)為人類(lèi)的走法會(huì)在很多promising的走法里選擇，這不一定能提高AlphaGo的下棋水平。為什么？文中沒(méi)有解釋?zhuān)覀€(gè)人認(rèn)為可能是一個(gè)局面（尤其是優(yōu)勢(shì)）的情況下有很多走法，有保守一點(diǎn)但是保證能贏一點(diǎn)點(diǎn)的走法，也有激進(jìn)但需要算度準(zhǔn)確的但能贏很多的走法。這取決于個(gè)人的能力（比如官子能力怎么樣）和當(dāng)時(shí)的情況（包括時(shí)間是否寬裕等等）。
所以AlphaGo使用強(qiáng)化學(xué)習(xí)通過(guò)自己跟自己對(duì)弈來(lái)調(diào)整參數(shù)學(xué)習(xí)更適合自己的Policy。
具體的做法是當(dāng)前版本跟之前的某一個(gè)版本（把之前所有版本都保留和不是用最近的一個(gè)可以避免overfitting）對(duì)弈，對(duì)弈的走法是根據(jù)Policy Network來(lái)選擇的，然后根據(jù)結(jié)果調(diào)整參數(shù)。這個(gè)公式用自然語(yǔ)言來(lái)描述就是最終得分z_t(獲勝或者失敗)，在t時(shí)刻局面是s_t我選擇了走法a_t，P(a_t|s_t)表示局面s_t時(shí)選擇走法a_t的概率，就像神經(jīng)網(wǎng)絡(luò)的反向傳播算法一樣，損失z_t(或者收益)是要由這個(gè)走法來(lái)負(fù)責(zé)的。我們調(diào)整參數(shù)的目的就是讓這個(gè)概率變小。再通俗一點(diǎn)說(shuō)就是，比如第一步我們的模型說(shuō)必須走馬(概率是1)，那么如果最終輸棋，我們復(fù)盤(pán)時(shí)可能會(huì)覺(jué)得下次走馬的概率應(yīng)該少一點(diǎn)，所以我們調(diào)整參數(shù)讓走馬的概率小一點(diǎn)（就是這個(gè)梯度）。
RL Policy Network的初始參數(shù)就是SL Policy Network的參數(shù)。最后學(xué)到的RL Policy Network與SL Policy Network對(duì)弈，勝率超過(guò)80%。
另外RL Policy Network與開(kāi)源的Pachi對(duì)弈（這個(gè)能到2d也就是業(yè)余兩段的水平），Pachi每步做100,000次Simulation，RL Policy Network的勝率超過(guò)85%，這說(shuō)明不用搜索只用Move Prediction能超過(guò)2d的水平。這和Tian等人的工作的結(jié)論是一致的，他們的darkforest2也只用Move Prediction在KGS上也能到3d的水平。
一個(gè)局面在policy p下的估值公式。用通俗的話說(shuō)就是：在t時(shí)刻的局面是s，然后我們用p來(lái)下棋直到游戲結(jié)束，我們重復(fù)很多次，然后求平均的得分。當(dāng)然，最理想的情況是我們能知道雙方都是最優(yōu)策略下的得分，可惜我們并不知道，所以只能用我們之前學(xué)到的SL Policy Network或者RL Policy Network來(lái)估計(jì)一個(gè)局面的得分，然后訓(xùn)練一個(gè)Value Network V(s)。前面我們也討論過(guò)了，RL Policy Network勝率更高，而我們學(xué)出來(lái)的Value Network是用于rollout階段作為先驗(yàn)概率的，所以AlphaGo使用了RL Policy Network的局面評(píng)估來(lái)訓(xùn)練V(s)。
V(s)的輸入時(shí)一個(gè)局面，輸出是一個(gè)局面的好壞得分，這是一個(gè)回歸問(wèn)題。AlphaGo使用了和Policy Network相同的參數(shù)，不過(guò)輸出是一個(gè)值而不是361個(gè)值（用softmax歸一化成概率）。
上面的公式說(shuō)明：V(s)的參數(shù)theta就是簡(jiǎn)單的用梯度下降來(lái)訓(xùn)練
不過(guò)用一盤(pán)對(duì)局的所有(s,v(s))訓(xùn)練是有問(wèn)題的，因?yàn)橥槐P(pán)對(duì)局的相鄰的局面是非常相關(guān)的，相鄰的局面只差一個(gè)棋子，所有非常容易o(hù)verfitting，導(dǎo)致模型“記住”了局面而不是學(xué)習(xí)到重要的feature。作者用這樣的數(shù)據(jù)訓(xùn)練了一個(gè)模型，在訓(xùn)練數(shù)據(jù)上的MSE只有0.19，而在測(cè)試數(shù)據(jù)上是0.37，這明顯overfitting了。為了解決這個(gè)問(wèn)題，作者用RL Policy Network自己跟自己對(duì)局了3千萬(wàn)次，然后每個(gè)對(duì)局隨機(jī)選擇一個(gè)局面，這樣得到的模型在訓(xùn)練數(shù)據(jù)和測(cè)試數(shù)據(jù)上的MSE是0.226和0.234，從而解決了overfitting的問(wèn)題。
上面花了大力氣訓(xùn)練了SL Policy Network,Rollout Policy和Value Network，那么怎么把它們?nèi)诤系組CTS中呢？
一次MCTS的Simulation可以用上圖來(lái)說(shuō)明，下文加黑的地方是這三個(gè)模型被用到的地方。
首先每個(gè)節(jié)點(diǎn)表示一個(gè)局面，每一條邊表示局面+一個(gè)合法的走法(s,a)。每條邊保存Q(s,a)，表示MCTS當(dāng)前累計(jì)的reward，N(s,a)表示這條邊的訪問(wèn)次數(shù)，P(s,a)表示先驗(yàn)概率。
每次Simulation使用如下的公式從根節(jié)點(diǎn)開(kāi)始一直選擇邊直到葉子節(jié)點(diǎn)（也就是這條邊對(duì)于的局面還沒(méi)有expand）。
Q(s_t,a)就是exploit term，而u(s_t,a)就是explore term，而且是于先驗(yàn)概率P(s,a)相關(guān)的，優(yōu)先探索SL Policy Network認(rèn)為好的走法。
對(duì)于葉子節(jié)點(diǎn)，AlphaGo不僅僅使用Rollout(使用Rollout Policy)計(jì)算得分，而且也使用Value Network打分，最終把兩個(gè)分?jǐn)?shù)融合起來(lái)：
n次Simulation之后更新統(tǒng)計(jì)量（從而影響Selection），為什么是n次，這涉及到多線程并行搜索以及運(yùn)行與GPU的Policy Network與Value Network與CPU主搜索線程通信的問(wèn)題
一個(gè)邊的訪問(wèn)次數(shù)超過(guò)一定閾值后展開(kāi)這個(gè)邊對(duì)應(yīng)的下一個(gè)局面。閾值會(huì)動(dòng)態(tài)調(diào)整以是的CPU和GPU的速度能匹配，具體下一節(jié)我們討論AlphaGo的實(shí)現(xiàn)細(xì)節(jié)再說(shuō)明
a圖是用分布式的AlphaGo，單機(jī)版的AlphaGo，CrazyStone等主流圍棋軟件進(jìn)行比賽，然后使用的是Elo Rating的打分。
作者認(rèn)為AlphaGo的水平超過(guò)了FanHui（2p)，因此AlphaGo的水平應(yīng)該達(dá)到了2p（不過(guò)很多人認(rèn)為目前Fanhui的水平可能到不了2p）。
b圖說(shuō)明了Policy Network Value Network和Rollout的作用，做了一些實(shí)驗(yàn)，去掉一些的情況下棋力的變化，結(jié)論當(dāng)然是三個(gè)都很重要。
c圖說(shuō)明了搜索線程數(shù)以及分布式搜索對(duì)棋力的提升，這些細(xì)節(jié)我們會(huì)在下一節(jié)再討論，包括AlphaGO的架構(gòu)能不能再scalable到更多機(jī)器的集群從而提升棋力。
因?yàn)?月份AlphaGo要挑戰(zhàn)李世石，所以大家都很關(guān)心AlphaGo到底到了什么水平。當(dāng)然它的真實(shí)水平只有作者才能知道，我這里都是根據(jù)一些新聞的推測(cè)。而且從文章提交Nature審稿到3月份比賽還有一段不短的時(shí)間，AlphaGo能不能還有提高也是非常關(guān)鍵。這里我只是推測(cè)一下在文章提交Nature時(shí)候AlphaGo的棋力。至于AlphaGo棋力能否提高，我們下一節(jié)分析實(shí)現(xiàn)細(xì)節(jié)時(shí)再討論（假設(shè)整體架構(gòu)不變，系統(tǒng)能不能通過(guò)增加機(jī)器來(lái)提高棋力）。
網(wǎng)上很多文章試圖通過(guò)AlphaGo與fanhui的對(duì)局來(lái)估計(jì)AlphaGo的棋力，我本人不敢發(fā)表意見(jiàn)。我只是搜索了一些相關(guān)的資料，主要是在弈城上一個(gè)叫DeepMind的賬號(hào)的對(duì)局信息來(lái)分析的。
比如這篇《金燦佑分析deepmind棋譜認(rèn)為99%與谷歌團(tuán)隊(duì)相關(guān)》。作者認(rèn)為這個(gè)賬號(hào)就是AlphaGo。如果猜測(cè)正確的話，AlphaGo當(dāng)時(shí)的棋力在弈城8d-9d直接，換成我們常用的ranking system的話大概也就是6d-7d（業(yè)余6段到7段）的水平，如果發(fā)揮得好，最多也許能到1p的水平，戰(zhàn)勝fanhui也有一定合理性（很多人認(rèn)為fanhui目前實(shí)際水平可能已經(jīng)沒(méi)有2p了，那算1p的話也差不多）。
知乎上也有很多討論，以及這篇《陳經(jīng)：谷歌圍棋算法存在缺陷》，都可以參考。
和之前類(lèi)似，搜索樹(shù)的每個(gè)狀態(tài)是s，它包含了所有合法走法(s,a)，每條邊包含如下的一些統(tǒng)計(jì)量：
P(s,a)是局面s下走a的先驗(yàn)概率。Wv(s,a)是simulation時(shí)value network的打分，Wr(s,a)是simulation時(shí)rollout的打分。Nv(s,a)和Nr(s,a)分別是simulation時(shí)value network和rollout經(jīng)過(guò)邊(s,a)的次數(shù)。Q(s,a)是最終融合了value network打分和rollout打分的最終得分。
rollout會(huì)模擬一個(gè)節(jié)點(diǎn)多次這比較好理解。為什么value network會(huì)給同一個(gè)節(jié)點(diǎn)打分多次呢？而且對(duì)于一個(gè)DCNN來(lái)說(shuō)，給定一個(gè)固定的輸入(s,a) P(a|s)不應(yīng)該是相同的值嗎，計(jì)算多次有什么意義嗎？
我剛開(kāi)始看了半天也沒(méi)明白，后來(lái)看到Symmetries那部分才明白。原來(lái)AlphaGo沒(méi)有像之前的工作那樣除了對(duì)稱(chēng)的問(wèn)題，對(duì)于APV-MCTS（Asynchronous Policy and Value MCTS)算法，每次經(jīng)過(guò)一個(gè)需要rollout的(s,a)時(shí)，會(huì)隨機(jī)的選擇8個(gè)對(duì)稱(chēng)方向中的一個(gè)，然后計(jì)算p(a|s)，因此需要平均這些value。計(jì)算Policy Network的機(jī)器會(huì)緩存這些值，所以Nv(s,a)應(yīng)該小于等于8。
還是這個(gè)圖。
從根節(jié)點(diǎn)開(kāi)始使用下面的公式選擇a直到葉子節(jié)點(diǎn)。
Q(s,a)初始值為0，后面Backup部分會(huì)講怎么更新Q(s,a)。
現(xiàn)在我們先看這個(gè)公式，第一部分Q(s,a)是exploit term，第二部分是explore term。這個(gè)公式開(kāi)始會(huì)同時(shí)考慮value高的和探索次數(shù)少的走法，但隨著N(s,a)的增加而更傾向于value高的走法。
葉子節(jié)點(diǎn)sL被加到一個(gè)隊(duì)列中等到value network計(jì)算得分（異步的），然后從sL開(kāi)始使用rollout policy模擬對(duì)局到游戲結(jié)束。
在Simulation開(kāi)始之前，把從根一直到sL的所有的(s,a)增加virtual loss，這樣可以防止（準(zhǔn)確的說(shuō)應(yīng)該是盡量不要，原文用的詞語(yǔ)是discourage，當(dāng)然如果其它走法也都有線程在模擬，那也是可以的）其它搜索線程探索相同的路徑。
上面的給(s,a)增加virtual 的loss，那么根據(jù)上面選擇的公式，就不太會(huì)選中它了。
當(dāng)模擬結(jié)束了，需要把這個(gè)virtual loss去掉，同時(shí)加上這次Simulation的得分。
此外，當(dāng)GPU算完value的得分后也要更新：
最終算出Q(s,a):
當(dāng)一條邊(s,a)的訪問(wèn)次數(shù)Nr(s,a)【提個(gè)小問(wèn)題，為什么是Nr(s,a)而不是Nv(s,a)？】超過(guò)一個(gè)閾值Nthr時(shí)會(huì)把這條邊的局面（其實(shí)就是走一下這個(gè)走法）s’=f(s,a)加到搜索樹(shù)里。
初始化統(tǒng)計(jì)量：Nv(s’,a)=0, Nr(s’,a)=0, Wv(s’,a)=0, Wr(s’,a)=0, P(s’,a)=P(a|s’)
由于計(jì)算P(a|s’)需要在GPU中利用SL Policy Network計(jì)算，比較慢，所以先給它一個(gè)place-holder的值，等到GPU那邊算完了再更新。
這個(gè)place-holder的值使用和rollout policy類(lèi)似的一個(gè)tree policy計(jì)算出來(lái)的（用的模型了rollout policy一樣，不過(guò)特征稍微豐富一些，后面會(huì)在表格中看到），在GPU算出真的P(a|s’)之前的selection都是先用這個(gè)place-holder值，所以也不能估計(jì)的太差。因此AlphaGO用了一個(gè)比rollout feature多一些的模型。
Expansion的閾值Nthr會(huì)動(dòng)態(tài)調(diào)整，目的是使得計(jì)算Policy Network的GPU能夠跟上CPU的速度。
一臺(tái)Master機(jī)器執(zhí)行主搜索（搜索樹(shù)的部分），一個(gè)CPU集群進(jìn)行rollout的異步計(jì)算，一個(gè)GPU集群進(jìn)行Policy和Value Network的異步計(jì)算。
整個(gè)搜索樹(shù)都存在Master上，它只負(fù)責(zé)Selection和Place-Holder先驗(yàn)的計(jì)算以及各種統(tǒng)計(jì)量的更新。葉子節(jié)點(diǎn)發(fā)到CPU集群進(jìn)行rollout計(jì)算，發(fā)到GPU集群進(jìn)行Policy和Value Network的計(jì)算。
最終，AlphaGo選擇訪問(wèn)次數(shù)最多的走法而不是得分最高的，因?yàn)楹笳邔?duì)野點(diǎn)(outlier)比較敏感。走完一步之后，之前搜索過(guò)的這部分的子樹(shù)的統(tǒng)計(jì)量直接用到下一輪的搜索中，不屬于這步走法的子樹(shù)直接扔掉。另外AlphaGo也實(shí)現(xiàn)了Ponder，也就是對(duì)手在思考的時(shí)候它也進(jìn)行思考。它思考選擇的走法是比較“可疑”的點(diǎn)——最大訪問(wèn)次數(shù)不是最高得分的走法。AlphaGo的時(shí)間控制會(huì)把思考時(shí)間盡量留在中局，此外AlphaGo也會(huì)投降——當(dāng)它發(fā)現(xiàn)贏的概率低于10%，也就是 MAXaQ(s,a) < -0.8。
AlphaGo并沒(méi)有想常見(jiàn)的圍棋那樣使用AMAF或者RAVE啟發(fā)，因?yàn)檫@些策略并沒(méi)有什么用處，此外也沒(méi)有使用開(kāi)局庫(kù)，動(dòng)態(tài)貼目(dynamic komi)等。
使用了兩大類(lèi)pattern，一種是response的pattern，也就是上一步走法附近的pattern（一般圍棋很多走法都是為了“應(yīng)付”對(duì)手的走子）；另一種就是非response的pattern，也就是將要走的那個(gè)走法附近的pattern。具體使用的特征見(jiàn)下表。Rollout Policy比較簡(jiǎn)單，每個(gè)CPU線程每秒可以從空的局面（開(kāi)局）模擬1000個(gè)對(duì)局。
橫線之上的feature用來(lái)rollout，所有的feature用來(lái)計(jì)算place-holder先驗(yàn)概率。
前面在講Search Algorithm講過(guò)了。
SL Policy Network使用了29.4 million局面來(lái)訓(xùn)練，這些局面來(lái)自KGS 6d-9d 的16萬(wàn)個(gè)對(duì)局。使用了前1million用來(lái)測(cè)試，后面的28.4million用來(lái)訓(xùn)練。此外進(jìn)行了旋轉(zhuǎn)和鏡像，把一個(gè)局面變成8個(gè)局面。使用隨機(jī)梯度下降算法訓(xùn)練，訓(xùn)練的mini-batch大小是16。使用了50個(gè)GPU的DistBelief（并沒(méi)有使用最新的Tensorflow），花了3周的時(shí)間來(lái)訓(xùn)練了340million次訓(xùn)練步驟（每個(gè)mini-batch算一個(gè)步驟？）
每次用并行的進(jìn)行n個(gè)游戲，使用當(dāng)前版本(參數(shù))的Policy Network和之前的某一個(gè)版本的Policy Network。當(dāng)前版本的初始值來(lái)自SL Policy Network。然后用 Policy Gradient來(lái)更新參數(shù)，這算一次迭代，經(jīng)過(guò)500次迭代之后，就認(rèn)為得到一個(gè)新的版本把它加到Pool里用來(lái)和當(dāng)前版本對(duì)弈。使用這種方法訓(xùn)練，使用50個(gè)GPU，n=128，10,000次對(duì)弈，一天可以訓(xùn)練完成RL Policy Network。
前面說(shuō)了，訓(xùn)練的關(guān)鍵是要自己模擬對(duì)弈然后隨機(jī)選擇局面而不是直接使用KGS的對(duì)局庫(kù)來(lái)避免overfitting。
AlphaGo生成了3千萬(wàn)局面，也就是3千萬(wàn)次模擬對(duì)弈，模擬的方法如下：
隨機(jī)選擇一個(gè)time-step U~unif{1,450}
根據(jù)SL Policy Network走1，2，… , U-1步棋
然后第U步棋從合法的走法中隨機(jī)選擇
然后用RL Policy Network模擬對(duì)弈到游戲結(jié)束
被作為一個(gè)訓(xùn)練數(shù)據(jù)加到訓(xùn)練集合里。
這個(gè)數(shù)據(jù)是
的一個(gè)無(wú)偏估計(jì)。
最后這個(gè)Value Network使用了50個(gè)GPU訓(xùn)練了一周，使用的mini-batch大小是32。
其實(shí)和前面Tian的差不太多，多了兩個(gè)征子相關(guān)的feature，另外增加了一個(gè)常量1和常量0的plane。
最后一個(gè)feature 是value network用的，因?yàn)榕袛嗑置娴梅謺r(shí)要知道是誰(shuí)走的，這個(gè)很關(guān)鍵。
13層從CNN，輸入時(shí)19*19*48，第一個(gè)hidden層把輸入用零把輸入padding成23*23，然后用k個(gè)5*5的filter，stride是1。
2到12層首先用零把輸入padding成21*21，然后使用k個(gè)5*5的filter，stride依然是1。
最后一層用一個(gè)1*1的filter，然后用一個(gè)softmax。
比賽用的k=192，文章也做了一些實(shí)驗(yàn)對(duì)比k=128,256,384的情況。
14層的CNN，前面12層和Policy Network一樣，第13層是一個(gè)filter的卷積層，第14層是全連接的Relu激活，然后輸出層是全連接的tanh單元。
不同分布式版本的水平比較，使用的是Elo rating標(biāo)準(zhǔn)。
從上面的細(xì)節(jié)來(lái)看，神經(jīng)網(wǎng)絡(luò)的訓(xùn)練其實(shí)用的時(shí)間和機(jī)器不多，真正非資源的還是在搜索階段。
最強(qiáng)的AlphaGo使用了64個(gè)搜索線程，1920個(gè)CPU的集群和280個(gè)GPU的機(jī)器（其實(shí)也就二十多臺(tái)機(jī)器）
之前我們討論過(guò)分布式MCTS時(shí)說(shuō)過(guò)，MCTS很難在多機(jī)上并行，所以AlphaGo還是在一臺(tái)機(jī)器上實(shí)現(xiàn)的LockFree的多線程并行，只不過(guò)Rollout和神經(jīng)網(wǎng)絡(luò)計(jì)算是在CPU和GPU集群上進(jìn)行的。Google的財(cái)力肯定不只二三十臺(tái)機(jī)器，所以分布式MCTS的搜索才是最大的瓶頸。如果這個(gè)能突破，把機(jī)器堆到成百上千臺(tái)應(yīng)該還是能提高不少棋力的。
我個(gè)人估計(jì)在3月與李世石的對(duì)弈中這個(gè)架構(gòu)可能還很難有突破，可以增強(qiáng)的是RL Policy的自對(duì)弈學(xué)習(xí)，不過(guò)這個(gè)提升也有限（否則不會(huì)只訓(xùn)練一天就停止了，估計(jì)也收斂的差不多了）
所以我個(gè)人的觀點(diǎn)是3月份要戰(zhàn)勝李世石還是難度比較大的。
之前我們討論的都是完全信息的兩人的零和博弈游戲。用的minimax也是假設(shè)對(duì)手都是走最優(yōu)的走法，但實(shí)際比賽中可能并非如此。
比如為了爭(zhēng)勝，我們可能走一些冒險(xiǎn)的策略，這個(gè)策略下如果對(duì)手走到最佳的走法我們可能會(huì)輸。但是由于局面復(fù)雜，稍有不慎可能就會(huì)走錯(cuò)，那么我們的目的就達(dá)到了。
還有就是多人的博弈，比如斗地主，我們可能還得對(duì)多個(gè)對(duì)手或者隊(duì)友建模。比如地主最后一張牌是否要炸，還得看隊(duì)友的接牌能力。
又比如你陪領(lǐng)導(dǎo)玩斗地主，另外一個(gè)人明顯目的是來(lái)給領(lǐng)導(dǎo)送錢(qián)的，那么你的策略可能也需要調(diào)整。
這可能就是現(xiàn)實(shí)世界和人工智能的差別了。有些事情，機(jī)器永遠(yuǎn)也不會(huì)懂，比如人生。
對(duì)于人生，每個(gè)人都像一顆棋子，那么誰(shuí)是下棋者呢，他又是和誰(shuí)在下棋呢？
我們?cè)谙缕宓臅r(shí)候更多的考慮是全局的利益，比如用一個(gè)兵卒換一個(gè)馬炮我們會(huì)非常開(kāi)心，但是作為要犧牲的兵卒來(lái)說(shuō)呢？一將功成萬(wàn)骨枯。
人生如棋，落子無(wú)悔。等到游戲結(jié)束的時(shí)候我們來(lái)復(fù)盤(pán)，才能發(fā)現(xiàn)當(dāng)年犯下的錯(cuò)誤，不過(guò)畢竟于事無(wú)補(bǔ)，只能給后人一些經(jīng)驗(yàn)教訓(xùn)罷了。
[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)載。詳情見(jiàn)轉(zhuǎn)載須知。
專(zhuān)題
