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

1、計(jì)算機(jī)圍棋的最新發(fā)展,北京郵電大學(xué)北郵?九鼎計(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í)別自然語(yǔ)言理解分布式高性能計(jì)算社會(huì)意義國(guó)防建設(shè)教育娛樂,圍棋是最具挑戰(zhàn)性的計(jì)算機(jī)博弈

2、,1997年，許峰雄博士領(lǐng)導(dǎo)的IBM Deeper Blue團(tuán)隊(duì)在國(guó)際象棋上戰(zhàn)勝了世界冠軍。2006年，徐心和教授領(lǐng)導(dǎo)的東北大學(xué)棋天大圣團(tuán)隊(duì)在中國(guó)象棋上戰(zhàn)平了全國(guó)冠軍。圍棋是唯一一個(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í)證明該

3、落子選點(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ù)雜度,圍棋

4、具有巨大的狀態(tài)空間復(fù)雜度和博弈樹復(fù)雜度狀態(tài)空間復(fù)雜度（用于搜索）十九路圍棋：10172國(guó)際象棋：1046中國(guó)象棋：1048博弈樹復(fù)雜度（用于決策）十九路圍棋： 10300 國(guó)際象棋： 10123 中國(guó)象棋： 10150,不可能的準(zhǔn)確靜態(tài)盤面評(píng)估,圍棋從本質(zhì)上無法做準(zhǔn)確的靜態(tài)盤面評(píng)估分析圍棋棋子位置，數(shù)目的多少，以及棋子之間的靜態(tài)關(guān)系（例如影響函數(shù)）無法完整地和準(zhǔn)確地評(píng)判圍棋棋子的作用與最終死活圍棋棋子的作用與最終死活

5、必須由博弈的具體進(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ī)圍棋

6、博弈技術(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ù)：蒙特卡羅模擬（Monte Carlo Simul

7、ation）信心上限算法（UCB，Upper Confidence Bounds）信心上限應(yīng)用樹算法（UCT，UCB applied to Trees）蒙特卡羅樹搜索（MCTS ，Monte Carlo Tree Search）高性能計(jì)算（High Performance Computing）,蒙特卡羅模擬,用于圍棋形式評(píng)估從所需評(píng)估盤面開始進(jìn)行隨機(jī)對(duì)弈至終局把終局結(jié)果返回給所需評(píng)估盤面以大量模擬的期望值來評(píng)估該盤面參

8、考文獻(xiàn)Abramson, B. (1990). Expected-outcome : a general model of static evaluation. IEEE transactions on PAMI, Vol. 12, pp. 182–193.Bruegmann, B. (1993). Monte Carlo Go. http://www.ideanest.com/vegos/MonteCarloGo.pdf,蒙特卡羅

9、模擬的特點(diǎn),蒙特卡羅模擬可以看作是博弈樹上單個(gè)路徑上的搜索，并有以下二個(gè)特點(diǎn)：搜索可快速終結(jié)2GHz Pentium，10000盤/秒九路圍棋蒙特卡羅模擬十九路圍棋的蒙特卡羅模擬速度大約是九路圍棋的1/4選點(diǎn)可快速驗(yàn)證選點(diǎn)的優(yōu)劣可根據(jù)終局結(jié)果在一定程度上得以驗(yàn)證終局結(jié)果通過中國(guó)圍棋規(guī)則進(jìn)行簡(jiǎn)單評(píng)判緩解了計(jì)算機(jī)圍棋博弈的二大主要困難增加模擬時(shí)間可以方便地提高總體的評(píng)估效果,蒙特卡羅模擬的效果與局限性,蒙特卡羅模擬的效果是明

10、顯的：1993年，Gobble在286PC上達(dá)到九路圍棋25級(jí)的水平在UCT算法出現(xiàn)之前，蒙特卡羅模擬的效果已接近傳統(tǒng)計(jì)算機(jī)圍棋博弈技術(shù)的水平蒙特卡羅模擬有局限性：簡(jiǎn)單的、按正態(tài)分布選點(diǎn)進(jìn)行蒙特卡羅模擬的效率很低,Multi-armed Bandit問題,Multi-armed Bandit問題K個(gè)獨(dú)立賭博角子機(jī)（匪徒的臂）每個(gè)賭博角子機(jī)的回報(bào)滿足一個(gè)未知的、靜態(tài)的隨機(jī)分布觀測(cè)到的玩賭博角子機(jī)i的回報(bào)為：Xi,1, Xi

11、,2, . . .策略P會(huì)根據(jù)以往的玩的賭博角子機(jī)及其回報(bào)選擇下一次玩的賭博角子機(jī),Multi-armed Bandit和計(jì)算機(jī)圍棋博弈,在計(jì)算機(jī)圍棋博弈中，一個(gè)棋盤狀態(tài)下的選點(diǎn)問題就是一個(gè)Multi-armed Bandit問題一個(gè)棋盤狀態(tài)就是一個(gè)多臂匪徒該棋盤狀態(tài)下的每個(gè)可下選點(diǎn)就是該多臂匪徒的一只手臂能選擇最優(yōu)選點(diǎn)的計(jì)算機(jī)圍棋對(duì)應(yīng)于解決Multi-armed Bandit問題的最優(yōu)策略解決Multi-armed Band

12、it問題的算法可用于指導(dǎo)蒙特卡羅模擬在圍棋選點(diǎn)搜索上的應(yīng)用,Multi-armed Bandit的UCB算法,UCB1算法：1.每個(gè)賭博角子機(jī)先玩一次2.以后每次選擇使右面公式最大化的賭博角子機(jī)平衡了探索與利用與最優(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. (2

13、002a). Finite-time analysis of the multiarmed bandit problem. Ma-chine Learning, 47, 235-256.,UCT算法和計(jì)算機(jī)圍棋博弈,計(jì)算機(jī)圍棋博弈中一個(gè)棋盤狀態(tài)下的選點(diǎn)是搜索樹上的極大極小搜索過程，在樹的每個(gè)節(jié)點(diǎn)上都面臨Multi-armed Bandit問題UCT算法是UCB算法在樹搜索上的應(yīng)用參考文獻(xiàn)L Kocsis and Cs Szep

14、esvari. Bandit Based Monte-Carlo Planning. In 15th European Conference on Machine Learning (ECML), pages 282–293, 2006.,UCT算法的偽代碼,MoGo計(jì)算機(jī)圍棋程序使用的UCT算法的偽代碼 function playOneSequence(rootNode) node[0] := rootNode;

15、i := 0; do node[i+1] := descendByUCB1(node[i]); i := i+1; while node[i] is not first visited; createNode(node[i]); node[i].value := getValueByMC(node[i]); updateValue(node,

16、-node[i].value); end function;,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算法，遞歸地

17、從博弈樹的根節(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)的剪枝策略模擬 –

18、使用知識(shí)指導(dǎo)蒙特卡羅模擬更新 – 按照UCT算法進(jìn)行更新,基于知識(shí)的博弈樹擴(kuò)展,可選落子點(diǎn)的排序策略蒙特卡羅樹搜索結(jié)束時(shí)，葉子節(jié)點(diǎn)的訪問次數(shù)很少；好的排序策略可以保證在有限時(shí)間內(nèi)雙方最強(qiáng)的應(yīng)手可以被搜索到Elo Rating – 根據(jù)離線知識(shí)靜態(tài)對(duì)可選落子點(diǎn)排序可選落子點(diǎn)的擴(kuò)展策略Progressive Widening – 先擴(kuò)展最強(qiáng)的落子選點(diǎn)可選落子點(diǎn)的剪枝策略適當(dāng)?shù)募糁蓽p少搜索范圍，提高搜索效率參考文獻(xiàn)Coul

19、om, R. (2007) Computing Elo Ratings of Move Patterns in the Game of Go, ICGA Journal, Vol. 30, No. 4. (December 2007), pp. 198-208.,基于知識(shí)的蒙特卡羅模擬,完全隨機(jī)的蒙特卡羅模擬效率不高蒙特卡羅模擬中加入圍棋知識(shí)以提高效率不填入自己的眼 - GobbleAMAF（所有落子如同第一手）- Gobble

20、模擬退火（逐漸減弱模擬中隨機(jī)性）- Gobble使用3x3模式 – Mogo優(yōu)先在關(guān)鍵點(diǎn)上落子（例如，點(diǎn)眼）- Mogo不在無效點(diǎn)上落子（例如，自殺） - Mogo參考文獻(xiàn)Gelly, S., Wang, Y., Munos, R., and Teytaud, O. Modification of UCT with patterns in Monte-Carlo Go. Technical Report 6062, INRIA

21、, 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使用640核的Huygens超級(jí)計(jì)算機(jī)戰(zhàn)勝了韓國(guó)職業(yè)八段（十九路圍棋，讓九子） 分布式計(jì)算ManyFaces使用8臺(tái)4核工作站分布式計(jì)算戰(zhàn)勝了職業(yè)圍棋選手（十九路圍棋，讓七子）,總結(jié)與展望,九路圍棋計(jì)算機(jī)圍