計(jì)算機(jī)圍棋博弈的最新發(fā)展全國(guó)計(jì)算機(jī)博弈大賽

計(jì)算機(jī)圍棋博弈的最新發(fā)展全國(guó)計(jì)算機(jī)博弈大賽提綱計(jì)算機(jī)圍棋博弈研究的意義及其主要困難計(jì)算機(jī)圍棋博弈的發(fā)展歷史傳統(tǒng)的計(jì)算機(jī)圍棋博弈技術(shù)現(xiàn)代的計(jì)算機(jī)圍棋博弈技術(shù)蒙特卡羅模擬信心上限算法與信心上限應(yīng)用樹(shù)算法蒙特卡羅樹(shù)搜索并行與分布式計(jì)算總結(jié)與展望計(jì)算機(jī)圍棋博弈研究的意義科學(xué)技術(shù)意義機(jī)器學(xué)習(xí)模式識(shí)別自然語(yǔ)言理解分布式高性能計(jì)算社會(huì)意義國(guó)防建設(shè)教育娛樂(lè)圍棋是最具挑戰(zhàn)性的計(jì)算機(jī)博弈1997年，許峰雄博士領(lǐng)導(dǎo)的IBMDeeperBlue團(tuán)隊(duì)在國(guó)際象棋上戰(zhàn)勝了世界冠軍。2006年，徐心和教授領(lǐng)導(dǎo)的東北大學(xué)棋天大圣團(tuán)隊(duì)在中國(guó)象棋上戰(zhàn)平了全國(guó)冠軍。圍棋是唯一一個(gè)計(jì)算機(jī)博弈水平仍遠(yuǎn)低于人類(lèi)博弈水平的傳統(tǒng)博弈現(xiàn)在，最強(qiáng)的19路計(jì)算機(jī)圍棋能達(dá)到被職業(yè)棋手讓大約7-9個(gè)子的水平。計(jì)算機(jī)圍棋博弈的基本方法博弈樹(shù)搜索通過(guò)搜索博弈樹(shù)進(jìn)行落子選點(diǎn)當(dāng)博弈樹(shù)搜索過(guò)程可以終結(jié)的時(shí)候，該搜索過(guò)程會(huì)找到最優(yōu)落子點(diǎn)，并同時(shí)證明該落子選點(diǎn)是最優(yōu)的專(zhuān)家系統(tǒng)通過(guò)使用具有知識(shí)、規(guī)則、推理的專(zhuān)家系統(tǒng)進(jìn)行落子選點(diǎn)。計(jì)算機(jī)圍棋博弈的二大核心困難搜索無(wú)法終結(jié)–無(wú)法有效地終結(jié)在圍棋博弈樹(shù)上的傳統(tǒng)搜索過(guò)程圍棋具有巨大的狀態(tài)空間復(fù)雜度和博弈樹(shù)復(fù)雜度提前終結(jié)搜索依賴(lài)于準(zhǔn)確的靜態(tài)盤(pán)面評(píng)估，而圍棋從本質(zhì)上無(wú)法做準(zhǔn)確的靜態(tài)盤(pán)面評(píng)估落子選點(diǎn)無(wú)法驗(yàn)證–圍棋專(zhuān)家系統(tǒng)的構(gòu)建非常復(fù)雜，其落子選點(diǎn)無(wú)法經(jīng)過(guò)嚴(yán)格的驗(yàn)證（例如，數(shù)學(xué)證明，或搜索驗(yàn)證）巨大的狀態(tài)空間和博弈樹(shù)復(fù)雜度圍棋具有巨大的狀態(tài)空間復(fù)雜度和博弈樹(shù)復(fù)雜度狀態(tài)空間復(fù)雜度（用于搜索）十九路圍棋：10172國(guó)際象棋：1046中國(guó)象棋：1048博弈樹(shù)復(fù)雜度（用于決策）十九路圍棋：10300

國(guó)際象棋：10123

中國(guó)象棋：10150不可能的準(zhǔn)確靜態(tài)盤(pán)面評(píng)估圍棋從本質(zhì)上無(wú)法做準(zhǔn)確的靜態(tài)盤(pán)面評(píng)估分析圍棋棋子位置，數(shù)目的多少，以及棋子之間的靜態(tài)關(guān)系（例如影響函數(shù)）無(wú)法完整地和準(zhǔn)確地評(píng)判圍棋棋子的作用與最終死活圍棋棋子的作用與最終死活必須由博弈的具體進(jìn)程所決定完整和準(zhǔn)確的圍棋盤(pán)面評(píng)估也無(wú)法靜態(tài)地完成過(guò)早的終結(jié)圍棋搜索無(wú)法得到有效的盤(pán)面評(píng)估結(jié)果（例如，α-β搜索）無(wú)法驗(yàn)證專(zhuān)家系統(tǒng)的落子選點(diǎn)通過(guò)知識(shí)、規(guī)則和推理不可能構(gòu)建高水平的計(jì)算機(jī)圍棋博弈專(zhuān)家系統(tǒng)知識(shí)和規(guī)則通常局限在局部和低層次上圍棋的知識(shí)和規(guī)則過(guò)于復(fù)雜，例外極多通過(guò)專(zhuān)家系統(tǒng)所產(chǎn)生的局部落子選點(diǎn)無(wú)法經(jīng)過(guò)嚴(yán)格的全局驗(yàn)證計(jì)算機(jī)圍棋博弈的發(fā)展歷史傳統(tǒng)計(jì)算機(jī)圍棋博弈技術(shù)（1968至2005）現(xiàn)代計(jì)算機(jī)圍棋博弈技術(shù)（2006至今）分水嶺（2006)--UCT算法的出現(xiàn)及其在計(jì)算機(jī)圍棋博弈上的應(yīng)用傳統(tǒng)的計(jì)算機(jī)圍棋博弈技術(shù)基于影響函數(shù)的形勢(shì)判斷使用模式生成落子候選點(diǎn)開(kāi)局定式，手筋，等等。表示人類(lèi)所使用的圍棋抽象串，群，眼，眼位，等等。局部搜索吃和逃（征子），連結(jié)和切斷，死活，等等。全局搜索（使用得非常有限）現(xiàn)代計(jì)算機(jī)圍棋博弈技術(shù)現(xiàn)代計(jì)算機(jī)圍棋博弈主要使用的關(guān)鍵技術(shù)：蒙特卡羅模擬（MonteCarloSimulation）信心上限算法（UCB，UpperConfidenceBounds）信心上限應(yīng)用樹(shù)算法（UCT，UCBappliedtoTrees）蒙特卡羅樹(shù)搜索（MCTS，MonteCarloTreeSearch）高性能計(jì)算（HighPerformanceComputing）蒙特卡羅模擬用于圍棋形式評(píng)估從所需評(píng)估盤(pán)面開(kāi)始進(jìn)行隨機(jī)對(duì)弈至終局把終局結(jié)果返回給所需評(píng)估盤(pán)面以大量模擬的期望值來(lái)評(píng)估該盤(pán)面參考文獻(xiàn)Abramson,B.(1990).Expected-outcome:ageneralmodelofstaticevaluation.IEEEtransactionsonPAMI,Vol.12,pp.182–193.Bruegmann,B.(1993).MonteCarloGo.蒙特卡羅模擬的特點(diǎn)蒙特卡羅模擬可以看作是博弈樹(shù)上單個(gè)路徑上的搜索，并有以下二個(gè)特點(diǎn)：搜索可快速終結(jié)2GHzPentium，10000盤(pán)/秒九路圍棋蒙特卡羅模擬十九路圍棋的蒙特卡羅模擬速度大約是九路圍棋的1/4選點(diǎn)可快速驗(yàn)證選點(diǎn)的優(yōu)劣可根據(jù)終局結(jié)果在一定程度上得以驗(yàn)證終局結(jié)果通過(guò)中國(guó)圍棋規(guī)則進(jìn)行簡(jiǎn)單評(píng)判緩解了計(jì)算機(jī)圍棋博弈的二大主要困難增加模擬時(shí)間可以方便地提高總體的評(píng)估效果蒙特卡羅模擬的效果與局限性蒙特卡羅模擬的效果是明顯的：1993年，Gobble在286PC上達(dá)到九路圍棋25級(jí)的水平在UCT算法出現(xiàn)之前，蒙特卡羅模擬的效果已接近傳統(tǒng)計(jì)算機(jī)圍棋博弈技術(shù)的水平蒙特卡羅模擬有局限性：簡(jiǎn)單的、按正態(tài)分布選點(diǎn)進(jìn)行蒙特卡羅模擬的效率很低Multi-armedBandit問(wèn)題Multi-armedBandit問(wèn)題K個(gè)獨(dú)立賭博角子機(jī)（匪徒的臂）每個(gè)賭博角子機(jī)的回報(bào)滿(mǎn)足一個(gè)未知的、靜態(tài)的隨機(jī)分布觀(guān)測(cè)到的玩賭博角子機(jī)i的回報(bào)為：Xi,1,Xi,2,...策略P會(huì)根據(jù)以往的玩的賭博角子機(jī)及其回報(bào)選擇下一次玩的賭博角子機(jī)Multi-armedBandit和計(jì)算機(jī)圍棋博弈在計(jì)算機(jī)圍棋博弈中，一個(gè)棋盤(pán)狀態(tài)下的選點(diǎn)問(wèn)題就是一個(gè)Multi-armedBandit問(wèn)題一個(gè)棋盤(pán)狀態(tài)就是一個(gè)多臂匪徒該棋盤(pán)狀態(tài)下的每個(gè)可下選點(diǎn)就是該多臂匪徒的一只手臂能選擇最優(yōu)選點(diǎn)的計(jì)算機(jī)圍棋對(duì)應(yīng)于解決Multi-armedBandit問(wèn)題的最優(yōu)策略解決Multi-armedBandit問(wèn)題的算法可用于指導(dǎo)蒙特卡羅模擬在圍棋選點(diǎn)搜索上的應(yīng)用Multi-armedBandit的UCB算法平衡了探索與利用與最優(yōu)算法的差距不超過(guò)對(duì)數(shù)范圍Xi是賭博角子機(jī)i的平均回報(bào)n是玩賭博角子機(jī)的總次數(shù)ni是玩賭博角子機(jī)i的次數(shù)參考文獻(xiàn)Auer,P.,Cesa-Bianchi,N.,&Fischer,P.(2002a).Finite-timeanalysisofthemultiarmedbanditproblem.Ma-chineLearning,47,235-256.UCT算法和計(jì)算機(jī)圍棋博弈計(jì)算機(jī)圍棋博弈中一個(gè)棋盤(pán)狀態(tài)下的選點(diǎn)是搜索樹(shù)上的極大極小搜索過(guò)程，在樹(shù)的每個(gè)節(jié)點(diǎn)上都面臨Multi-armedBandit問(wèn)題UCT算法是UCB算法在樹(shù)搜索上的應(yīng)用參考文獻(xiàn)LKocsisandCsSzepesvari.BanditBasedMonte-CarloPlanning.In15thEuropeanConferenceonMachineLearning(ECML),pages282–293,2006.UCT算法的偽代碼MoGo計(jì)算機(jī)圍棋程序使用的UCT算法的偽代碼

functionplayOneSequence(rootNode)node[0]:=rootNode;i:=0;

donode[i+1]:=descendByUCB1(node[i]);i:=i+1;

whilenode[i]isnotfirstvisited;createNode(node[i]);node[i].value:=getValueByMC(node[i]);updateValue(node,-node[i].value);

endfunction;UCT算法的局限性作為在線(xiàn)機(jī)器學(xué)習(xí)的算法，UCT有其局限性圍棋知識(shí)沒(méi)有得到應(yīng)用解決方法把在線(xiàn)學(xué)習(xí)UCT算法與傳統(tǒng)圍棋知識(shí)結(jié)合起來(lái)蒙特卡羅樹(shù)搜索（MCTS）蒙特卡羅樹(shù)搜索是把離線(xiàn)學(xué)習(xí)的知識(shí)與在線(xiàn)搜索的過(guò)程相結(jié)合的一種最優(yōu)優(yōu)先的搜索方法使用UCT算法進(jìn)行在線(xiàn)搜索使用離線(xiàn)知識(shí)提高UCT搜索的效率蒙特卡羅樹(shù)搜索的四個(gè)主要組成部分搜索–通過(guò)UCT算法，遞歸地從博弈樹(shù)的根節(jié)點(diǎn)向下搜索直至當(dāng)前的葉子節(jié)點(diǎn)擴(kuò)展–對(duì)當(dāng)前的博弈樹(shù)葉子節(jié)點(diǎn)進(jìn)行擴(kuò)展模擬–從當(dāng)前的博弈樹(shù)葉子節(jié)點(diǎn)開(kāi)始進(jìn)行蒙特卡羅模擬更新–把蒙特卡羅模擬的結(jié)果更新到搜索過(guò)程中博弈樹(shù)的每個(gè)節(jié)點(diǎn)上離線(xiàn)知識(shí)在蒙特卡羅樹(shù)搜索中的使用離線(xiàn)知識(shí)在蒙特卡羅樹(shù)搜索的四個(gè)組成部分中的使用搜索–使用知識(shí)進(jìn)行UCT算法的初始化擴(kuò)展–使用知識(shí)控制博弈樹(shù)擴(kuò)展可選落子點(diǎn)的排序策略可選落子點(diǎn)的擴(kuò)展策略可選落子點(diǎn)的剪枝策略模擬–使用知識(shí)指導(dǎo)蒙特卡羅模擬更新–按照UCT算法進(jìn)行更新基于知識(shí)的博弈樹(shù)擴(kuò)展可選落子點(diǎn)的排序策略蒙特卡羅樹(shù)搜索結(jié)束時(shí)，葉子節(jié)點(diǎn)的訪(fǎng)問(wèn)次數(shù)很少；好的排序策略可以保證在有限時(shí)間內(nèi)雙方最強(qiáng)的應(yīng)手可以被搜索到EloRating–根據(jù)離線(xiàn)知識(shí)靜態(tài)對(duì)可選落子點(diǎn)排序可選落子點(diǎn)的擴(kuò)展策略ProgressiveWidening–先擴(kuò)展最強(qiáng)的落子選點(diǎn)可選落子點(diǎn)的剪枝策略適當(dāng)?shù)募糁蓽p少搜索范圍，提高搜索效率參考文獻(xiàn)Coulom,R.(2007)ComputingEloRatingsofMovePatternsintheGameofGo,ICGAJournal,Vol.30,No.4.(December2007),pp.198-208.基于知識(shí)的蒙特卡羅模擬完全隨機(jī)的蒙特卡羅模擬效率不高蒙特卡羅模擬中加入圍棋知識(shí)以提高效率不填入自己的眼-GobbleAMAF（所有落子如同第一手）-Gobble模擬退火（逐漸減弱模擬中隨機(jī)性）-Gobble使用3x3模式–Mogo優(yōu)先在關(guān)鍵點(diǎn)上落子（例如，點(diǎn)眼）-Mogo不在無(wú)效點(diǎn)上落子（例如，自殺）-Mogo參考文獻(xiàn)Gelly,S.,Wang,Y.,Munos,R.,andTeytaud,O.ModificationofUCTwithpatternsinMonte-CarloGo.TechnicalReport6062,INRIA,France,2006.高性能計(jì)算在蒙特卡羅樹(shù)搜索算法實(shí)現(xiàn)相同的條件下，計(jì)算機(jī)圍棋的博弈水平取決于單位時(shí)間的計(jì)算量計(jì)算量大→模擬次數(shù)多→評(píng)估更準(zhǔn)確計(jì)算量大→搜索的博弈樹(shù)更完整→評(píng)估更準(zhǔn)確共享內(nèi)存并行計(jì)算MoGo使