? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?Google DeepMind AlphaGO分析

AlphaGO是第一個(gè)擊敗人類職業(yè)圍棋選手、第一個(gè)戰(zhàn)勝圍棋世界冠軍的人工智能程序允蚣，由谷歌（Google）旗下DeepMind公司戴密斯·哈薩比斯領(lǐng)銜的團(tuán)隊(duì)開發(fā)于颖。其主要工作原理是深度學(xué)習(xí)。以下是對(duì)其實(shí)現(xiàn)過程及算法的簡(jiǎn)析嚷兔。

圍棋棋盤是19x19路森渐，所以一共是361個(gè)交叉點(diǎn)，每個(gè)交叉點(diǎn)有三種狀態(tài)冒晰，可以用1表示黑子同衣，-1表示白字，0表示無子壶运，考慮到每個(gè)位置還可能有落子的時(shí)間耐齐、這個(gè)位置的氣等其他信息，可以用一個(gè)361 * n維的向量來表示一個(gè)棋盤的狀態(tài)蒋情。將一個(gè)棋盤狀態(tài)向量記為s埠况。

當(dāng)狀態(tài)s時(shí)，在不考慮某位置無法落子的情況下棵癣，可供下一步落子的空間也是361個(gè)辕翰，因此將下一步的落子的行動(dòng)也用361維的向量來表示，記為a狈谊。

至此喜命，可將設(shè)計(jì)圍棋人工智能的程序轉(zhuǎn)換成為在任意給定一個(gè)s狀態(tài)下，尋找最好的應(yīng)對(duì)策略a河劝，使程序按照該策略可獲得棋盤上最大的地盤的程序壁榕。

一、深度卷積神經(jīng)網(wǎng)絡(luò)

深度卷積神經(jīng)網(wǎng)絡(luò)早在98年就攻克了手寫數(shù)字識(shí)別丧裁，近年在人臉識(shí)別、圖像分類含衔、天氣預(yù)報(bào)等領(lǐng)域亦有顯著突破煎娇，接連達(dá)到或超過人類的水平二庵。2015年，AlphaGO主要設(shè)計(jì)師黃士杰在ICLR的論文發(fā)表利用“深度神經(jīng)網(wǎng)絡(luò)”從圍棋對(duì)戰(zhàn)平臺(tái)KGS獲取人類選手的圍棋對(duì)弈的棋局進(jìn)行學(xué)習(xí)缓呛，實(shí)現(xiàn)人機(jī)交戰(zhàn)的論文催享。

在這些棋局中，每一個(gè)狀態(tài)s哟绊，都會(huì)有一個(gè)人類做出的落子a（訓(xùn)練樣本）因妙。將s看做一個(gè)19x19的二維圖像（實(shí)際為19x19 x n，其中n表示其他feature）票髓，輸入一個(gè)卷積神經(jīng)網(wǎng)絡(luò)進(jìn)行分類攀涵，分類的目標(biāo)是落子向量a’，不斷訓(xùn)練網(wǎng)絡(luò)洽沟，盡可能讓計(jì)算機(jī)得到的a’接近人類高手的落子結(jié)果a以故，既可得到了一個(gè)初步模擬人類棋手下圍棋的神經(jīng)網(wǎng)絡(luò)。

設(shè)置一可以模擬人類棋手的策略函數(shù)P_human裆操，對(duì)于給定的某個(gè)棋局狀態(tài)s怒详，計(jì)算出人類選手可能在棋盤上落子的概率分布a = P_human(s)，如下圖：

紅圈既P_human認(rèn)定的最好的落子方案踪区。每一步都選擇概率最高的落子昆烁，對(duì)方對(duì)子后再重新計(jì)算一遍，如此往復(fù)就可以得到一個(gè)棋風(fēng)類似人類的圍棋程序缎岗。經(jīng)檢測(cè)静尼，P_human方案達(dá)到的圍棋水平在人類選手業(yè)余6段左右，但未能超過彼時(shí)最強(qiáng)的電腦程序CrazyStone[1,5]（利用MCTS實(shí)現(xiàn)）密强。

二茅郎、蒙特卡洛搜索樹（MCTS）

蒙特卡洛搜索樹（Monte-Carlo Tree Search）由黃士杰的老師Remi Coulum于2006年提出，是圍棋AI史上的重大突破或渤。

面對(duì)一個(gè)空白棋盤S0系冗，假設(shè)所有落子方法分值都相等，設(shè)為1薪鹦。從361種落子方法中隨機(jī)選擇一個(gè)走法a0掌敬，落子之后，棋盤狀態(tài)變成S1池磁。假設(shè)對(duì)手進(jìn)行相同操作奔害，隨機(jī)落子，棋盤狀態(tài)變成S2地熄。至Sn時(shí)华临，分出勝負(fù)r，贏r記為1端考，輸則為0雅潭。

假設(shè)這第一次r=1揭厚。將上一次的落子方法（S0,a0）記錄下來，分值進(jìn)行以下修改：

新分?jǐn)?shù)=初始分+ r

此時(shí)r=1扶供，新分?jǐn)?shù)=2筛圆。將隨機(jī)出的局面所對(duì)應(yīng)落子方法(Si,ai)的分?jǐn)?shù)設(shè)為2。既除（S0, a0）的分值是2外椿浓，其他落子方法的分?jǐn)?shù)仍為1太援。再次選擇a0的概率比其他方法略高。

設(shè)置對(duì)手也用同樣的方法更新其新分?jǐn)?shù)扳碍，假設(shè)選擇一個(gè)a1作為應(yīng)對(duì)提岔，繼續(xù)第一次的操作。假設(shè)此次結(jié)果仍為贏左腔，繼續(xù)調(diào)整模擬路徑上相應(yīng)的分?jǐn)?shù)唧垦，將其均+1。隨著模擬棋局?jǐn)?shù)量增加液样，優(yōu)秀的落子方案分?jǐn)?shù)會(huì)越來越高振亮，而這些落子方案越是有前途，就會(huì)被更多的選中進(jìn)行推演鞭莽，既可得到最優(yōu)秀的落子方案坊秸。

蒙特卡洛搜索樹存在的兩個(gè)優(yōu)點(diǎn)：

1）沒有任何人工的feature，完全依靠規(guī)則本身澎怒，通過不斷想象自對(duì)弈來提高能力褒搔。

2）MCTS可以連續(xù)運(yùn)行，在對(duì)手思考對(duì)策的同時(shí)自己也可以思考對(duì)策喷面。在下完第一步后星瘾，不必要停下，可以繼續(xù)進(jìn)行模擬對(duì)弈惧辈，直到對(duì)手落子琳状，隨后從對(duì)手落子之后的狀態(tài)開始計(jì)算。因?yàn)閷?duì)手的落子可能出現(xiàn)在之前的模擬對(duì)弈中盒齿，所以之前的模擬對(duì)弈可以保留念逞。

蒙特卡洛搜索樹存在的缺點(diǎn)：

初始策略太簡(jiǎn)單，需要更高效地隨機(jī)落子边翁。

三翎承、深度卷積神經(jīng)網(wǎng)絡(luò)與蒙特卡洛搜索樹結(jié)合

改進(jìn)MCTS，先根據(jù)P_human的計(jì)算結(jié)果得到a可能的概率分布符匾，以此概率挑選下一步的動(dòng)作叨咖。新分?jǐn)?shù)按照如下方式更新：

新分?jǐn)?shù)=調(diào)整后的初始分+ 通過模擬得到的贏棋概率

如某一步被隨機(jī)到很多次，就應(yīng)該主要依據(jù)模擬得到的概率而非P_human，因此調(diào)整P_human的初始分算法：

調(diào)整后的初始分= P_human/（被隨機(jī)到的次數(shù)+ 1）

調(diào)整后可用P_human快速定位較好的落子方案甸各，并給其他位置一定的概率仰剿。

當(dāng)前問題為P_human()計(jì)算過慢。一次P_human()計(jì)算需要3ms痴晦，相對(duì)于隨機(jī)落子的不到1us，速度慢了3000倍琳彩。如果不能快速模擬對(duì)局誊酌，棋力就不能提高。

訓(xùn)練簡(jiǎn)化版的P_human_fast()露乏，把神經(jīng)網(wǎng)絡(luò)層數(shù)碧浊、輸入特征都減少，耗時(shí)下降到了2us瘟仿，基本滿足了要求箱锐。先以P_human()開局，落子越20步后劳较，使用P_human_fast()快速走到最后驹止，兼顧了準(zhǔn)確度和效率。

圍棋軟件所使用的神經(jīng)網(wǎng)絡(luò)和蒙特卡洛方法都可以隨著訓(xùn)練集的增長(zhǎng)和計(jì)算力的加強(qiáng)而同步增強(qiáng)观蜗，可以實(shí)現(xiàn)棋力的穩(wěn)步提升臊恋。

四、左右互搏墓捻，自我進(jìn)化

同年2月抖仅，由Deepmind團(tuán)隊(duì)在頂級(jí)學(xué)術(shù)期刊nature上發(fā)表的《用神經(jīng)網(wǎng)絡(luò)打游戲》一文中提出，為進(jìn)一步提高M(jìn)CTS的棋力指明了前進(jìn)的新方向砖第。

Deepmind團(tuán)隊(duì)通過“強(qiáng)化學(xué)習(xí)”方法訓(xùn)練的程序在類似紅白機(jī)的游戲機(jī)上打通了200多個(gè)游戲撤卢，大多數(shù)得分超過人類玩家。

“強(qiáng)化學(xué)習(xí)”是一類機(jī)器學(xué)習(xí)方法梧兼，Agent通過和環(huán)境s的交互放吩，選擇下一步的動(dòng)作a，這個(gè)動(dòng)作會(huì)影響環(huán)境s袱院，給Agent一個(gè)reward屎慢，Agent然后繼續(xù)和環(huán)境交互。游戲結(jié)束的時(shí)候忽洛，Agent得到一個(gè)最后總分r腻惠。將環(huán)境狀態(tài)s、動(dòng)作a匹配起來得到一系列欲虚，設(shè)定目標(biāo)為最后的總得分r集灌，可以訓(xùn)練一個(gè)神經(jīng)網(wǎng)絡(luò)擬合在狀態(tài)s下，做動(dòng)作a的總得分。下一次進(jìn)行游戲時(shí)欣喧，就可以根據(jù)當(dāng)前狀態(tài)s腌零，去選擇最后總得分最大的動(dòng)作a。通過不斷進(jìn)行游戲唆阿，對(duì)下總得分的估計(jì)會(huì)越來越準(zhǔn)確益涧，游戲得分會(huì)越來越好。

以打磚塊游戲?yàn)槔北睿瑥?qiáng)化學(xué)習(xí)的程序在600盤以后闲询，學(xué)到球在快要把墻打穿的時(shí)候評(píng)價(jià)函數(shù)v的分值會(huì)急劇上升，既球打到墻的后面去浅辙，球會(huì)自動(dòng)反彈得分扭弧。

在圍棋中引入一個(gè)評(píng)價(jià)函數(shù)v(s)，在P_human()模擬開局20步后记舆，不需要搜索到底鸽捻，通過v(s)就可以直接判斷是否能贏，得到最后的結(jié)果r泽腮，進(jìn)而提高M(jìn)CTS的學(xué)習(xí)速度御蒲。

首先利用P_human和P_human對(duì)弈獲取大量棋譜（如進(jìn)行一萬(wàn)局，就得到了一萬(wàn)個(gè)新棋譜诊赊。）删咱。將棋譜加入到訓(xùn)練集中，訓(xùn)練出P_human_1（此時(shí)訓(xùn)練方法較之前稍有不同豪筝，P_human盡可能的模仿人類棋手下棋痰滋，而不區(qū)分每一步棋的好壞。P_human和P_human對(duì)弈之后续崖，記錄下狀態(tài)s啊研、下一步落子位置a慎冤、以及最終勝負(fù)情況z蚕钦，得到一個(gè)訓(xùn)練數(shù)據(jù)(s,a,z)温艇。如果z=1, 表示我方贏棋，則盡可能模仿此時(shí)自我對(duì)弈中的下棋位置像吻；反之則盡可能避免選擇自我對(duì)弈中的下棋位置峻黍。）。然后再使P_human_1和P_human_1對(duì)局拨匆，得到大量的新棋譜姆涩，以訓(xùn)練出P_human_2。如此往復(fù)惭每，可以得到P_human_n骨饿。P_human_n得到了最多的訓(xùn)練，棋力理應(yīng)比原來更強(qiáng)，將該策略記作P_human_plus宏赘。這時(shí)绒北，P_human_plus和P_human對(duì)局，在不用任何搜索的情況下勝率可達(dá)80%察署，不加任何搜索策略的P_human_plus和開源的MCTS相比也有85%的勝率闷游。

將P_human_plus代入MCTS中，用P_human_plus開局贴汪，然后用P_human_fast繼續(xù)接下來的操作储藐。因P_human_plus走棋的路數(shù)太集中，而MCTS需要發(fā)散出更多的選擇嘶是，導(dǎo)致結(jié)果棋力反而不如用P_human。

進(jìn)一步改進(jìn)蛛碌，開局仍先用P_human走L步聂喇，以有利于生成更多局面。為了進(jìn)一步擴(kuò)大搜索空間蔚携，在L+1步的時(shí)候希太，隨機(jī)落子，記下當(dāng)前狀態(tài)SL+1酝蜒，然后用P_human_plus對(duì)弈誊辉，直到結(jié)束獲得結(jié)果r。經(jīng)不斷訓(xùn)練亡脑，由于L也是隨機(jī)數(shù)堕澄，可得開局、中盤霉咨、官子不同階段的局面s及其對(duì)應(yīng)的結(jié)果r蛙紫。利用這些訓(xùn)練樣本，使用神經(jīng)網(wǎng)絡(luò)將最后一層的目標(biāo)改成回歸而非分類途戒，得到v( )函數(shù)坑傅。v()可給出下一步落子在棋盤上任意位置后，如雙方均用P_human_plus來落子喷斋，我方贏棋的概率唁毒。

五、AlphaGO

在MCTS框架之上融合局面評(píng)估函數(shù)v()星爪。用P_human作為初始分開局浆西，每局選擇分?jǐn)?shù)最高的方案落子，下到第L步之后顽腾，改用P_human_fast將剩余棋局走完室谚，同時(shí)調(diào)用v(SL)，評(píng)估局面的獲勝概率。按照如下規(guī)則更新樹的分?jǐn)?shù)：

新分?jǐn)?shù)=調(diào)整后的初始分+ 0.5 * 通過模擬得到的贏棋概率 + 0.5 * 局面評(píng)估分

前兩項(xiàng)與原來相同秒赤，如待更新的節(jié)點(diǎn)即為葉子節(jié)點(diǎn)猪瞬，則局面評(píng)估分即是v(SL)。如為待更新的節(jié)點(diǎn)是上級(jí)節(jié)點(diǎn)入篮，局面評(píng)估分是該節(jié)點(diǎn)所有葉子節(jié)點(diǎn)v()的平均值陈瘦。

假設(shè)v()表示大局觀，“P_human_fast模擬對(duì)局”表示快速驗(yàn)算潮售，則方法為大局觀和快速模擬驗(yàn)算并重痊项。至此，AlphaGO初步實(shí)現(xiàn)酥诽。