深挖圍棋AI技術：alphaGo在下一盤什麼棋？（上）
【編者按】作者李理，出門問問NLP工程師。本文原標題：AlphaGo的棋局，與人工智能有關，與人生無關。
CNN和Move Prediction之前我們說瞭MCTS回避瞭局面估值的問題，但是人類下圍棋顯然不是這樣的，所以真正要下好圍棋，如此從模仿人類的角度來說，這個問題是繞不過去的。人類是怎麼學習出不同局面的細微區別的呢？當然不能由人來提取特征或者需要人來編寫估值函數，否則還是回到之前的老路上瞭。我們的機器能自動學習而不需要領域的專傢手工編寫特征或者規則來實現估值函數呢？
眼下最火熱的深度學習也許可以給我們一條路徑（當然可能還有其它路徑，但深度學習目前看起來解決feature的自動學習是最promising的方法之一）。
深度學習和CNN簡介在機器學習流行之前，都是基於規則的系統，因此做語音的需要瞭解語音學，做NLP的需要很多語言學知識，做深藍需要很多國際象棋大師。
而到後來統計方法成為主流之後，領域知識就不再那麼重要，但是我們還是需要一些領域知識或者經驗來提取合適的feature，feature的好壞往往決定瞭機器學習算法的成敗。對於NLP來說，feature還相對比較好提取，因為語言本身就是高度的抽象；而對於Speech或者Image來說，我們人類自己也很難描述我們是怎麼提取feature的。比如我們識別一隻貓，我們隱隱約約覺得貓有兩個眼睛一個鼻子有個長尾巴，而且它們之間有一定的空間約束關系，比如兩種眼睛到鼻子的距離可能差不多。但怎麼用像素來定義”眼睛“呢？如果仔細想一下就會發現很難。當然我們有很多特征提取的方法，比如提取邊緣輪廓等等。
但是人類學習似乎不需要這麼復雜，我們隻要給幾張貓的照片給人看，他就能學習到什麼是貓。人似乎能自動”學習“出feature來，你給他看瞭幾張貓的照片，然後問題貓有什麼特征，他可能會隱隱預約的告訴你貓有什麼特征，甚至是貓特有的特征，這些特征豹子或者老虎沒有。
深度學習為什麼最近這麼火，其中一個重要的原因就是不需要（太多）提取feature。
從機器學習的使用者來說，我們以前做的大部分事情是feature engineering，然後調一些參數，一般是為瞭防止過擬合。而有瞭深度學習之後，如果我們不需要實現一個CNN或者LSTM，那麼我們似乎什麼也不用幹。
Deep Neural Network能自動學習出層次化的featureCNN最早是Yann Lecun提出用來解決圖像識別的問題的一種深度神經網絡。由Yann LeCun提出，通過卷積來發現位置無關的feature，而且這些feature的參數是相同的，從而與全連接的神經網絡相比汽車音響電容推薦大大減少瞭參數的數量。
CNN深度神經網絡
因此CNN非常適合圍棋這種feature很難提取問題，比如圖像識別。用CNN來嘗試圍棋的局面評估似乎也是很自然的想法。
Move Prediction using CNN之前也分析過瞭，圍棋搜索如果不到遊戲結束，深的局面並不比淺的容易評估，所以我們不需要展開搜索樹，而可以直接評估一個局面下不同走法的好壞。這樣做的好處是很容易獲得訓練數據。我們有大量人類圍棋高手的對局（海量中等水平的對局），每一個局面下“好”的走法直接就能夠從高手對局庫裡得到，認為他們的對局都是“好”的走法。但是要得到一個局面的“絕對”得分卻很難，因為我們隻知道一盤對局最終的結果。一盤遊戲最終的勝負可能是因為佈局就下得很好，也可能是因為最後的官子階段下得好，中間具體某個局面的好壞是很難判斷的（當然強化學習試圖解決這個問題，但是還是很難的，下面在討論AlphaGo的時候會有涉及）。對於一個局面，如果能知道這個局面下最好的走法（或者幾個走法），那麼我們對弈時就直接選擇這個走法（當然這個最好的走法可能得分也很差，比如敗局已定的情況下怎麼走都是輸）。
所以大部分研究都是用CNN來預測一個局面下最好的走法。【預測走法比估值一個局面容易，如果我們能夠準確估值局面，那麼最佳走法就是從走之後的局面中選擇對自己最有利的走法。或者用我們做問答系統常用的比喻，預測走法是搜索引擎，局面評估是問答系統。搜索引擎隻要把好的排前面就行瞭（甚至不一定要求排在第一，排在第一頁也就差不多瞭），而問答不僅要把好的排前面，而且還要知道這個最“好”的結果是否足夠“好”，因為排序的好是相對“好”，問答的好必須是絕對的“好”，是唯一正確答案】。
Van Der Werf等（2003）最早用CNN（當然還有用其它機器學習方法）來預測走法是2003年Van Der Werf等人的工作，他們用瞭很多手工構造的feature和預處理方法，他們取得瞭25%的預測準確率。沒有細看論文，在2006年Deep Learning火之前，所以估計網絡的層次很淺。
Sutskever Nair（2008）之後在2008年，這個時候Deep的神經網絡已經逐漸流行瞭。Sutskever Nair用來2層的CNN，第一層有15個7*7的filter，第二層用瞭5*5的filter，最後用瞭一個softmax層，輸出19*19，表示每個可能走法的概率（當然需要後處理去掉不合法或者不合理的走法，比如違反棋規的打劫局面立即提回，或者在自己的眼裡下棋）。他們得到瞭34%的預測準確率。不過有一點問題就是他們出來使用當前局面，還用瞭上一步走法（這個走子導致瞭當前局面，也就是對手的上一步走子），這個可能是有問題的，因為實際對局時對手的水平是不能確定的，用這個feature當然能提高“數字”上的準確率，但是對於下棋水平是否有負面影響是很難說的。
Clark Storkey（2015）到瞭2015年，計算機的計算能力更強，深度神經網絡的層次也越來越深，在圍棋領域也能看到這種趨勢。Clark Storkey使用瞭8層的CNN，用的特征包括最原始的棋子（用瞭3個feature plane，表示361個點是黑棋/白棋/空白），ko（劫）的約束，一個group（塊）的氣。包括使用很多trick來保證symmetries（因為圍棋的局面旋轉90/180/270/360度後以及做180度的鏡像之後應該是一樣的）。他們在GoGoD數據上的預測準確率達到瞭41.1%，在KGS數據上的準確率達到44.4%。GoGoD上大部分是職業選手的對局，而KGS數據有很多業餘高手的對局。
Maddison等（2015）光是預測準確率，並不能說明下棋的水平。因此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。因為圍棋很多都是局部的戰役，所以這個feature應該是有用的。
第六組就是表示走這這後能吃對方多少個棋子。
第七組表示走這能否征子成功。
第八組feature比較有趣，按照作者的說法就是因為KGS的對弈水平參差不齊，如果隻留下高手的對局數據太少，所以用這個feature。
他們在KGS數據上的預測準確率達到55%。相對於Clark等人的工作，Maddison的工作除瞭增加瞭CNN的層次（8到12），增加的feature應該是很有幫助的，比如Turns Since，Capture Size和Ladder Move。尤其是Ladder Move，下過圍棋的都知道征子能否成功對應是否要走這步棋已經局部的計算非常重要。
根據他們的使用，人類6d的預測準確率也隻有52%，所以從預測走法的角度來說，CNN的水平已經達到瞭6d的水平。
另外他們還做瞭實驗，證明Clark那些用來保證symmetry的tricky並沒有什麼卵用，直接簡單粗暴的把數據做symmetric變換後訓練就行瞭。
完全不用搜索直接用Move Prediction的結果下棋，能97%的比率戰勝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個局面。所以他們使用瞭異步的策略，先用先驗知識給出一個節點的N(v),Q(v)，先搜索著，等GPU運算完瞭再用CNN預測的勝率更新這些統計量。因此CPU和GPU的速度需要能大致匹配。
Yuandong Tian Yan Zhu（2015）和Google DeepMind進行圍棋競賽的主要就是Facebook Tian yuandong他們瞭。在Google宣佈文章在Nature發表的前一天，他們在arxiv上發表瞭自己的工作。
下面我們來看看他們的工作（《Better Computer Go Player with Neural Network and Long-Term Prediction》）。
使用的feature：
除瞭使用之前工作的標準feature之外，他們增加瞭一些feature，比如是否邊界，距離中心的遠近，是否靠近自己與對手的領土（不清楚怎麼定義領土的歸屬的）。此外對於之前的feature也進行瞭壓縮，之前都把特征分成黑棋或者白棋，現在直接變成己方和對手，這樣把模型從兩個變成瞭一個（之前需要給黑棋和白棋分別訓練一個模型）。此外的一個不同地方就是類似於Multi-task的learning，同時預測未來3步棋的走法（而不是1步棋走法）。
為瞭與Maddison的工作比較，這裡隻用瞭標準的features，比較的也是未來1步棋的準確率，可以發現這個方法還是有效的（不過我個人覺得作者應該自己復現Maddison的結果而不是直接用他的結果）
隻使用DCNN的圍棋軟件（不用MCTS搜索）
darkforest: 標準的feature，一步的預測，使用KGS數據
darkforest1：擴展的feature，三步預測，使用GoGoD數據
darkforest2：基於darkforest1，fine-tuning瞭一下參數。
把它們放到KGS上比賽，darkforest能到1k-1d的水平，darkforest1能到2d的水平，darkforest2能到3d的水平【註：KGS的3d應該到不瞭實際的業餘3段】，下面是具體的情況。
因此作者認為加入3步預測的訓練是有效的。
MCTS+DCNNTree Policy: 走法首先通過DCNN排序，然後按順序選擇，除非累計的概率超過0.8或者超過一定次數的top走法。Expansion使用的UCT算法。
Default Policy:參考的Pachi的tree policy，有3*3的pattern，對手打吃的點（opponent atari point），點眼的檢測（detection of nakade points）等。
這個版本的軟件叫darkforest3，在KGS上能到5d的水平。
弱點DCNN預測的top3/5的走法可能不包含局部戰役的一個關鍵點，所以它的局部作戰能力還比較弱。
對於一些打劫點即使沒用，DCNN還是會給高分。
當局面不好的情況下，它會越走越差（這是MCTS的弱點，因為沒有好的走法，模擬出來都是輸棋，一些比較頑強的抵抗的走法不能走出來）。
從上面的分析可以看出：DCNN給出的走法大局觀還是不錯的，這正是傳統的方法很難解決的問題。局部的作戰更多靠計算，MCTS會有幫助。但是我個人覺得MCTS搜索到結束，沒有必要。一個局部的計算也許可以用傳統的alpha-beta搜索來解決，比如征子的計算，要看6線有沒有對手的棋子，另外即使有對手的棋子，也要看位置的高低，這樣的計算DCNN是沒法解決的，需要靠計算。
AlphaGo終於輪到主角上陣瞭，您可能不耐煩瞭。不過有瞭前面的基礎，理解AlphaGo就容易多瞭，這裡我們主要分析AlphaGo的創新點。
Policy Network Value Network
上圖是AlphaGo所使用的兩個網絡以及訓練過程。和之前的工作比，除瞭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部分討論的局面的估值函數，隻不過AlphaGo是使用深度強化學習(deep reinforcment learning)學習出來，而不是像Deep Blue或者其它象棋程序那樣是人工提取的feature甚至手工調整權重（當然Deep Blue是很多年前的工作瞭，現在也有用深度強化學習來搞國際象棋的，比如這篇論文《Giraffe: Using Deep Reinforcement Learning to Play Chess》）。
前面在討論Tian等人的工作時我們也分析過瞭，光用Move Prediction的軟件大局觀還不錯，但是局部的戰術就比較差，因為局部的戰術更多靠計算，人類也是這樣。圍棋由於估值函數比較困難，所以大都是用MCTS搜索到遊戲結束。但是MCTS如果盲目搜索（使用隨機的default policy去rollout/playout）肯定不好，使用各種領域知識來縮小rollout的范圍就非常重要。前面我們也看到，傳統的MCTS隻能到2d的水平，而用DCNN的tree policy的MCTS就能到5d的水平（如果default policy如果能用DCNN指導肯定更好，可惜DCNN的速度太慢）。
SL Policy Network Rollout Policy的訓練這個和之前介紹的差不瞭太多。AlphaGo相比之前多瞭Rollout Policy，之前的Rollout Policy大多是使用手工編制的pattern，而AlphaGo用訓練Policy Network相同的數據訓練瞭一個簡單的模型來做Rollout。
訓練數據來自3千萬的KGS的數據，使用瞭13層的CNN，預測準確率是57%，這和之前Tian等人的工作是差不多的。
RL Policy Network Value Network的訓練之前訓練的SL Policy Network優化的目標是預測走法，作者認為人類的走法會在很多promising的走法裡選擇，這不一定能提高AlphaGo的下棋水平。為什麼？文中沒有解釋，我個人認為可能是一個局面（尤其是優勢）的情況下有很多走法，有保守一點但是保證能贏一點點的走法，也有激進但需要算度準確的但能贏很多的走法。這取決於個人的能力（比如官子能力怎麼樣）和當時的情況（包括時間是否寬裕等等）。
所以AlphaGo使用強化學習通過自己跟自己對弈來調整參數學習更適合自己的Policy。
具體的做法是當前版本跟之前的某一個版本（把之前所有版本都保留和不是用最近的一個可以避免overfitting）對弈，對弈的走法是根據Policy Network來選擇的，然後根據結果調整參數。這個公式用自然語言來描述就是最終得分z_t(獲勝或者失敗)，在t時刻局面是s_t我選擇瞭走法a_t，P(a_t|s_t)表示局面s_t時選擇走法a_t的概率，就像神經網絡的反向傳播算法一樣，損失z_t(或者收益)是要由這個走法來負責的。我們調整參數的目的就是讓這個概率變小。再通俗一點說就是，比如第一步我們的模型說必須走馬(概率是1)，那麼如果最終輸棋，我們復盤時可能會覺得下次走馬的概率應該少一點，所以我們調整參數讓走馬的概率小一點（就是這個梯度）。
RL Policy Network的初始參音響後級系統數就是SL Policy Network的參數。最後學到的RL Policy Network與SL Policy Network對弈，勝率超過80%。
另外RL Policy Network與開源的Pachi對弈（這個能到2d也就是業餘兩段的水平），Pachi每步做100,000次Simulation，RL Policy Network的勝率超過85%，這說明不用搜索隻用Move Prediction能超過2d的水平。這和Tian等人的工作的結論是一致的，他們的darkforest2也隻用Move Prediction在KGS上也能到3d的水平。
Value Network的強化學習訓練
一個局面在policy p下的估值公式。用通俗的話說就是：在t時刻的局面是s，然後我們用p來下棋直到遊戲結束，我們重復很多次，然後求平均的得分。當然，最理想的情況是我們能知道雙方都是最優策略下的得分，可惜我們並不知道，所以隻能用我們之前學到的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相同的參數，不過輸出是一個值而不是361個值（用softmax歸一化成概率）。
上面的公式說明：V(s)的參數theta就是簡單的用梯度下降來訓練
不過用一盤對局的所有(s,v(s))訓練是有問題的，因為同一盤對局的相鄰的局面是非常相關的，相鄰的局面隻差一個棋子，所有非常容易overfitting，導致模型“記住”瞭局面而不是學習到重要的feature。作者用這樣的數據訓練瞭一個模型，在訓練數據上的MSE隻有0.19，而在測試數據上是0.37，這明顯overfitting瞭。為瞭解決這個問題，作者用RL Policy Network自己跟自己對局瞭3千萬次，然後每個對局隨機選擇一個局面，這樣得到的模型在訓練數據和測試數據上的MSE是0.226和0.234，從而解決瞭overfitting的問題。
MCTS + Policy Value Networks上面花瞭大力氣訓練瞭SL Policy Network,Rollout Policy和Value Network，那麼怎麼把它們融合到MCTS中呢？
一次MCTS的Simulation可以用上圖來說明，下文加黑的地方是這三個模型被用到的地方。
首先每個節點表示一個局面，每一條邊表示局面+一個合法的走法(s,a)。每條邊保存Q(s,a)，表示MCTS當前累計的reward，N(s,a)表示這條邊的訪問次數，P(s,a)表示先驗概率。
Selection每次Simulation使用如下的公式從根節點開始一直選擇邊直到葉子節點（也就是這條邊對於的局面還沒有expand）。
Q(s_t,a)就是exploit term，而u(s_t,a)就是explore term，而且是於先驗概率P(s,a)相關的，優先探索SL Policy Network認為好的走法。
Evaluation對於葉子節點，AlphaGo不僅僅使用Rollout(使用Rollout Policy)計算得分，而且也使用Value Network打分，最終把兩個分數融合起來：
Backup
n次Simulation之後更新統計量（從而影響Selection），為什麼是n次，這涉及到多線程並行搜索以及運行與GPU的Policy Network與Value Network與CPU主搜索線程通信的問題
Expansion一個邊的訪問次數超過一定閾值後展開這個邊對應的下一個局面。閾值會動態調整以是的CPU和GPU的速度能匹配，具體下一節我們討論AlphaGo的實現細節再說明
AlphaGo的水平
a圖是用分佈式的AlphaGo，單機版的AlphaGo，CrazyStone等主流圍棋軟件進行比賽，然後使用的是Elo Rating的打分。
作者認為AlphaGo的水平超過瞭FanHui（2p)，因此AlphaGo的水平應該達到瞭2p（不過很多人認為目前Fanhui的水平可能到不瞭2p）。
b圖說明瞭Policy Network Value Network和Rollout的作用，做瞭一些實驗，去掉一些的情況下棋力的變化，結論當然是三個都很重要。
c圖說明瞭搜索線程數以及分佈式搜索對棋力的提升，這些細節我們會在下一節再討論，包括AlphaGO的架構能不能再scalable到更多機器的集群從而提升棋力。
AlphaGo的真實棋力因為3月份AlphaGo要挑戰李世石，所以大傢都很關心AlphaGo到底到瞭什麼水平。當然它的真實水平隻有作者才能知道，我這裡都是根據一些新聞的推測。而且從文章提交Nature審稿到3月份比賽還有一段不短的時間，AlphaGo能不能還有提高也是非常關鍵。這裡我隻是推測一下在文章提交Nature時候AlphaGo的棋力。至於AlphaGo棋力能否提高，我們下一節分析實現細節時再討論（假設整體架構不變，系統能不能通過增加機器來提高棋力）。
網上很多文章試圖通過AlphaGo與fanhui的對局來估計AlphaGo的棋力，我本人不敢發表意見。我隻是搜索瞭一些相關的資料，主要是在弈城上一個叫DeepMind的賬號的對局信息來分析的。
比如這篇《金燦佑分析deepmind棋譜認為99%與谷歌團隊相關》。作者認為這個賬號就是Alph汽車音響電容價錢aGo。如果猜測正確的話，AlphaGo當時的棋力在弈城8d-9d直接，換成我們常用的ranking system的話大概也就是6d-7d（業餘6段到7段）的水平，如果發揮得好，最多也許能到1p的水平，戰勝fanhui也有一定合理性（很多人認為fanhui目前實際水平可能已經沒有2p瞭，那算1p的話也差不多）。
知乎上也有很多討論，以及這篇《陳經：谷歌圍棋算法存在缺陷》，都可以參考。
AlphaGo的實現細節Search Algorithm和之前類似，搜索樹的每個狀態是s，它包含瞭所有合法走法(s,a)，每條邊包含如下的一些統計量：
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經過邊(s,a)的次數。Q(s,a)是最終融合瞭value network打分和rollout打分的最終得分。
rollout會模擬一個節點多次這比較好理解。為什麼value network會給同一個節點打分多次呢？而且對於一個DCNN來說，給定一個固定的輸入(s,a) P(a|s)不應該是相同的值嗎，計算多次有什麼意義嗎？
我剛開始看瞭半天也沒明白，後來看到Symmetries那部分才明白。原來AlphaGo沒有像之前的工作那樣除瞭對稱的問題，對於APV-MCTS（Asynchronous Policy and Value MCTS)算法，每次經過一個需要rollout的(s,a)時，會隨機的選擇8個對稱方向中的一個，然後計算p(a|s)，因此需要平均這些value。計算Policy Network的機器會緩存這些值，所以Nv(s,a)應該小於等於8。
還是這個圖。
Selection(圖a)從根節點開始使用下面的公式選擇a直到葉子節點。
Q(s,a)初始值為0，後面Backup部分會講怎麼更新Q(s,a)。
現在我們先看這個公式，第一部分Q(s,a)是exploit term，第二部分是explore term。這個公式開始會同時考慮value高的和探索次數少的走法，但隨著N(s,a)的增加而更傾向於value高的走法。
Evaluation(圖c)葉子節點sL被加到一個隊列中等到value network計算得分（異步的），然後從sL開始使用rollout policy模擬對局到遊戲結束。
Backup(圖d)在Simulation開始之前，把從根一直到sL的所有的(s,a)增加virtual loss，這樣可以防止（準確的說應該是盡量不要，原文用的詞語是discourage，當然如果其它走法也都有線程在模擬，那也是可以的）其它搜索線程探索相同的路徑。
上面的給(s,a)增加virtual 的loss，那麼根據上面選擇的公式，就不太會選中它瞭。
當模擬結束瞭，需要把這個virtual loss去掉，同時加上這次Simulation的得分。
此外，當GPU算完value的得分後也要更新：
最終算出Q(s,a):
Expansion(圖b)當一條邊(s,a)的訪問次數Nr(s,a)【提個小問題，為什麼是Nr(s,a)而不是Nv(s,a)？】超過一個閾值Nthr時會把這條邊的局面（其實就是走一下這個走法）s’=f(s,a)加到搜索樹裡。
初始化統計量：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會動態調整，目的是使得計算Policy Network的GPU能夠跟上CPU的速度。
Distributed APV-MCTS算法一臺Master機器執行主搜索（搜索樹的部分），一個CPU集群進行rollout的異步計算，一個GPU集群進行Policy和Value Network的異步計算。
整個搜索樹都存在Master上，它隻負責Selection和Place-Holder先驗的計算以及各種統計量的更新。葉子節點發到CPU集群進行rollout計算，發到GPU集群進行Policy和Value Network的計算。
最終，AlphaGo選擇訪問次數最多的走法而不是得分最高的，因為後者對野點(outlier)比較敏感。走完一步之後，之前搜索過的這部分的子樹的統計量直接用到下一輪的搜索中，不屬於這步走法的子樹直接扔掉。另外AlphaGo也實現瞭Ponder，也就是對手在思考的時候它也進行思考。它思考選擇的走法是比較“可疑”的點——最大訪問次數不是最高得分的走法。AlphaGo的時間控制會把思考時間盡量留在中局，此外AlphaGo也會投降——當它發現贏的概率低於10%，也就是 MAXaQ(s,a) -0.8。
AlphaGo並沒有想常見的圍棋那樣使用AMAF或者RAVE啟發，因為這些策略並沒有什麼用處，此外也沒有使用開局庫，動態貼目(dynamic komi)等。
Rollout Policy使用瞭兩大類pattern，一種是response的pattern，也就是上一步走法附近的pattern（一般圍棋很多走法都是為瞭“應付”對手的走子）；另一種就是非response的pattern，也就是將要走的那個走法附近的pattern。具體使用的特征見下表。Rollout Policy比較簡單，每個CPU線程每秒可以從空的局面（開局）模擬1000個對局。
橫線之上的feature用來rollout，所有的feature用來計算place-holder先驗概率。
Symmetries前面在講Search Algorithm講過瞭。
SL Policy NetworkSL Policy Network使用瞭29.4 million局面來訓練，這些局面來自KGS 6d-9d 的16萬個對局。使用瞭前1million用來測試，後面的28.4million用來訓練。此外進行瞭旋轉和鏡像，把一個局面變成8個局面。使用隨機梯度下降算法訓練，訓練的mini-batch大小是16。使用瞭50個GPU的DistBelief（並沒有使用最新的Tensorflow），花瞭3周的時間來訓練瞭340million次訓練步驟（每個mini-batch算一個步驟？）
RL Policy Network每次用並行的進行n個遊戲，使用當前版本(參數)的Policy Network和之前的某一個版本的Policy Network。當前版本的初始值來自SL Policy Network。然後用 Policy Gradient來更新參數，這算一次迭代，經過500次迭代之後，就認為得到一個新的版本把它加到Pool裡用來和當前版本對弈。使用這種方法訓練，使用50個GPU，n=128，10,000次對弈，一天可以訓練完成RL Policy Network。
Value Network前面說瞭，訓練的關鍵是要自己模擬對弈然後隨機選擇局面而不是直接使用KGS的對局庫來避免overfitting。
AlphaGo生成瞭3千萬局面，也就是3千萬次模擬對弈，模擬的方法如下：
隨機選擇一個time-step U~unif{1,450}
根據SL Policy Network走1，2，… , U-1步棋
然後第U步棋從合法的走法中隨機選擇
然後用RL Policy Network模擬對弈到遊戲結束
被作為一個訓練數據加到訓練集合裡。
這個數據是
的一個無偏估計。
最後這個Value Network使用瞭50個GPU訓練瞭一周，使用的mini-batch大小是32。
Policy/Value Network使用的Features
其實和前面Tian的差不太多，多瞭兩個征子相關的feature，另外增加瞭一個常量1和常量0的plane。
最後一個feature 是value network用的，因為判斷局面得分時要知道是誰走的，這個很關鍵。
神經網絡結構Policy Network13層從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的情況。
Value Network14層的CNN，前面12層和Policy Network一樣，第13層是一個filter的卷積層，第14層是全連接的Relu激活，然後輸出層是全連接的tanh單元。
不同分佈式版本的水平比較，使用的是Elo rating標準。
總結從上面的細節來看，神經網絡的訓練其實用的時間和機器不多，真正非資源的還是在搜索階段。
最強的AlphaGo使用瞭64個搜索線程，1920個CPU的集群和280個GPU的機器（其實也就二十多臺機器）
之前我們討論過分佈式MCTS時說過，MCTS很難在多機上並行，所以AlphaGo還是在一臺機器上實現的LockFree的多線程並行，隻不過Rollout和神經網絡計算是在CPU和GPU集群上進行的。Google的財力肯定不隻二三十臺機器，所以分佈式MCTS的搜索才是最大的瓶頸。如果這個能突破，把機器堆到成百上千臺應該還是能提高不少棋力的。
我個人估計在3月與李世石的對弈中這個架構可能還很難有突破，可以增強的是RL Policy的自對弈學習，不過這個提升也有限（否則不會隻訓練一天就停止瞭，估計也收斂的差不多瞭）
所以我個人的觀點是3月份要戰勝李世石還是難度比較大的。
人生的棋之前我們討論的都是完全信息的兩人的零和博弈遊戲。用的minimax也是假設對手都是走最優的走法，但實際比賽中可能並非如此。
比如為瞭爭勝，我們可能走一些冒險的策略，這個策略下如果對手走到最佳的走法我們可能會輸。但是由於局面復雜，稍有不慎可能就會走錯，那麼我們的目的就達到瞭。
還有就是多人的博弈，比如鬥地主，我們可能還得對多個對手或者隊友建模。比如地主最後一張牌是否要炸，還得看隊友的接牌能力。
又比如你陪領導玩鬥地主，另外一個人明顯目的是來給領導送錢的，那麼你的策略可能也需要調整。
這可能就是現實世界和人工智能的差別瞭。有些事情，機器永遠也不會懂，比如人生。
對於人生，每個人都像一顆棋子，那麼誰是下棋者呢，他又是和誰在下棋呢？
我們在下棋的時候更多的考慮是全局的利益，比如用一個兵卒換一個馬炮我們會非常開心，但是作為要犧牲的兵卒來說呢？一將功成萬骨枯。
人生如棋，落子無悔。等到遊戲結束的時候我們來復盤，才能發現當年犯下的錯誤，不過畢竟於事無補，隻能給後人一些經驗教訓罷瞭。
參考文獻[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).
本文首發CSDN
AUGI SPORTS｜重機車靴｜重機車靴推薦｜重機專用車靴｜重機防摔鞋｜重機防摔鞋推薦｜重機防摔鞋
AUGI SPORTS｜augisports｜racing boots｜urban boots｜motorcycle boots
留言列表
