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

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

國際象棋：10123

中國象棋：10150不可能的準(zhǔn)確靜態(tài)盤面評(píng)估圍棋從本質(zhì)上無法做準(zhǔn)確的靜態(tài)盤面評(píng)估分析圍棋棋子位置，數(shù)目的多少，以及棋子之間的靜態(tài)關(guān)系（例如影響函數(shù)）無法完整地和準(zhǔn)確地評(píng)判圍棋棋子的作用與最終死活圍棋棋子的作用與最終死活必須由博弈的具體進(jìn)程所決定完整和準(zhǔn)確的圍棋盤面評(píng)估也無法靜態(tài)地完成過早的終結(jié)圍棋搜索無法得到有效的盤面評(píng)估結(jié)果（例如，α-β搜索）無法驗(yàn)證專家系統(tǒng)的落子選點(diǎn)通過知識(shí)、規(guī)則和推理不可能構(gòu)建高水平的計(jì)算機(jī)圍棋博弈專家系統(tǒng)知識(shí)和規(guī)則通常局限在局部和低層次上圍棋的知識(shí)和規(guī)則過于復(fù)雜，例外極多通過專家系統(tǒng)所產(chǎn)生的局部落子選點(diǎn)無法經(jīng)過嚴(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)開局定式，手筋，等等。表示人類所使用的圍棋抽象串，群，眼，眼位，等等。局部搜索吃和逃（征子），連結(jié)和切斷，死活，等等。全局搜索（使用得非常有限）現(xiàn)代計(jì)算機(jī)圍棋博弈技術(shù)現(xiàn)代計(jì)算機(jī)圍棋博弈主要使用的關(guān)鍵技術(shù)：蒙特卡羅模擬（MonteCarloSimulation）信心上限算法（UCB，UpperConfidenceBounds）信心上限應(yīng)用樹算法（UCT，UCBappliedtoTrees）蒙特卡羅樹搜索（MCTS，MonteCarloTreeSearch）高性能計(jì)算（HighPerformanceComputing）蒙特卡羅模擬用于圍棋形式評(píng)估從所需評(píng)估盤面開始進(jìn)行隨機(jī)對(duì)弈至終局把終局結(jié)果返回給所需評(píng)估盤面以大量模擬的期望值來評(píng)估該盤面參考文獻(xiàn)Abramson,B.(1990).Expected-outcome:ageneralmodelofstaticevaluation.IEEEtransactionsonPAMI,Vol.12,pp.182–193.Bruegmann,B.(1993).MonteCarloGo.蒙特卡羅模擬的特點(diǎn)蒙特卡羅模擬可以看作是博弈樹上單個(gè)路徑上的搜索，并有以下二個(gè)特點(diǎn)：搜索可快速終結(jié)2GHzPentium，10000盤/秒九路圍棋蒙特卡羅模擬十九路圍棋的蒙特卡羅模擬速度大約是九路圍棋的1/4選點(diǎn)可快速驗(yàn)證選點(diǎn)的優(yōu)劣可根據(jù)終局結(jié)果在一定程度上得以驗(yàn)證終局結(jié)果通過中國圍棋規(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問題Multi-armedBandit問題K個(gè)獨(dú)立賭博角子機(jī)（匪徒的臂）每個(gè)賭博角子機(jī)的回報(bào)滿足一個(gè)未知的、靜態(tài)的隨機(jī)分布觀測(cè)到的玩賭博角子機(jī)i的回報(bào)為：Xi,1,Xi,2,...策略P會(huì)根據(jù)以往的玩的賭博角子機(jī)及其回報(bào)選擇下一次玩的賭博角子機(jī)Multi-armedBandit和計(jì)算機(jī)圍棋博弈在計(jì)算機(jī)圍棋博弈中，一個(gè)棋盤狀態(tài)下的選點(diǎn)問題就是一個(gè)Multi-armedBandit問題一個(gè)棋盤狀態(tài)就是一個(gè)多臂匪徒該棋盤狀態(tài)下的每個(gè)可下選點(diǎn)就是該多臂匪徒的一只手臂能選擇最優(yōu)選點(diǎn)的計(jì)算機(jī)圍棋對(duì)應(yīng)于解決Multi-armedBandit問題的最優(yōu)策略解決Multi-armedBandit問題的算法可用于指導(dǎo)蒙特卡羅模擬在圍棋選點(diǎn)搜索上的應(yīng)用Multi-armedBandit的UCB算法平衡了探索與利用與最優(yōu)算法的差距不超過對(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è)棋盤狀態(tài)下的選點(diǎn)是搜索樹上的極大極小搜索過程，在樹的每個(gè)節(jié)點(diǎn)上都面臨Multi-armedBandit問題UCT算法是UCB算法在樹搜索上的應(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算法的局限性作為在線機(jī)器學(xué)習(xí)的算法，UCT有其局限性圍棋知識(shí)沒有得到應(yīng)用解決方法把在線學(xué)習(xí)UCT算法與傳統(tǒng)圍棋知識(shí)結(jié)合起來蒙特卡羅樹搜索（MCTS）蒙特卡羅樹搜索是把離線學(xué)習(xí)的知識(shí)與在線搜索的過程相結(jié)合的一種最優(yōu)優(yōu)先的搜索方法使用UCT算法進(jìn)行在線搜索使用離線知識(shí)提高UCT搜索的效率蒙特卡羅樹搜索的四個(gè)主要組成部分搜索–通過UCT算法，遞歸地從博弈樹的根節(jié)點(diǎn)向下搜索直至當(dāng)前的葉子節(jié)點(diǎn)擴(kuò)展–對(duì)當(dāng)前的博弈樹葉子節(jié)點(diǎn)進(jìn)行擴(kuò)展模擬–從當(dāng)前的博弈樹葉子節(jié)點(diǎn)開始進(jìn)行蒙特卡羅模擬更新–把蒙特卡羅模擬的結(jié)果更新到搜索過程中博弈樹的每個(gè)節(jié)點(diǎn)上離線知識(shí)在蒙特卡羅樹搜索中的使用離線知識(shí)在蒙特卡羅樹搜索的四個(gè)組成部分中的使用搜索–使用知識(shí)進(jìn)行UCT算法的初始化擴(kuò)展–使用知識(shí)控制博弈樹擴(kuò)展可選落子點(diǎn)的排序策略可選落子點(diǎn)的擴(kuò)展策略可選落子點(diǎn)的剪枝策略模擬–使用知識(shí)指導(dǎo)蒙特卡羅模擬更新–按照UCT算法進(jìn)行更新基于知識(shí)的博弈樹擴(kuò)展可選落子點(diǎn)的排序策略蒙特卡羅樹搜索結(jié)束時(shí)，葉子節(jié)點(diǎn)的訪問次數(shù)很少；好的排序策略可以保證在有限時(shí)間內(nèi)雙方最強(qiáng)的應(yīng)手可以被搜索到EloRating–根據(jù)離線知識(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不在無效點(diǎn)上落子（例如，自殺）-Mogo參考文獻(xiàn)Gelly,S.,Wang,Y.,Munos,R.,andTeytaud,O.ModificationofUCTwithpatternsinMonte-CarloGo.TechnicalReport6062,INRIA,France,2006.高性能計(jì)算在蒙特卡羅樹搜索算法實(shí)現(xiàn)相同的條件下，計(jì)算機(jī)圍棋的博弈水平取決于單位時(shí)間的計(jì)算量計(jì)算量大→模擬次數(shù)多→評(píng)估更準(zhǔn)確計(jì)算量大→搜索的博弈樹更完整→評(píng)估更準(zhǔn)確共享內(nèi)存并行計(jì)算MoGo使