1、計算機圍棋的最新發(fā)展,北京郵電大學北郵?九鼎計算機圍棋研究所劉知青,提綱,計算機圍棋博弈研究的意義及其主要困難計算機圍棋博弈的發(fā)展歷史傳統(tǒng)的計算機圍棋博弈技術現(xiàn)代的計算機圍棋博弈技術蒙特卡羅模擬信心上限算法與信心上限應用樹算法蒙特卡羅樹搜索并行與分布式計算總結與展望,計算機圍棋博弈研究的意義,科學技術意義機器學習模式識別自然語言理解分布式高性能計算社會意義國防建設教育娛樂,圍棋是最具挑戰(zhàn)性的計算機博弈

2、,1997年，許峰雄博士領導的IBM Deeper Blue團隊在國際象棋上戰(zhàn)勝了世界冠軍。2006年，徐心和教授領導的東北大學棋天大圣團隊在中國象棋上戰(zhàn)平了全國冠軍。圍棋是唯一一個計算機博弈水平仍遠低于人類博弈水平的傳統(tǒng)博弈現(xiàn)在，最強的19路計算機圍棋能達到被職業(yè)棋手讓大約7-9個子的水平。,計算機圍棋博弈的基本方法,博弈樹搜索通過搜索博弈樹進行落子選點當博弈樹搜索過程可以終結的時候，該搜索過程會找到最優(yōu)落子點，并同時證明該

3、落子選點是最優(yōu)的專家系統(tǒng)通過使用具有知識、規(guī)則、推理的專家系統(tǒng)進行落子選點。,計算機圍棋博弈的二大核心困難,搜索無法終結 – 無法有效地終結在圍棋博弈樹上的傳統(tǒng)搜索過程圍棋具有巨大的狀態(tài)空間復雜度和博弈樹復雜度提前終結搜索依賴于準確的靜態(tài)盤面評估，而圍棋從本質上無法做準確的靜態(tài)盤面評估落子選點無法驗證 – 圍棋專家系統(tǒng)的構建非常復雜，其落子選點無法經(jīng)過嚴格的驗證（例如，數(shù)學證明，或搜索驗證）,巨大的狀態(tài)空間和博弈樹復雜度,圍棋

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

5、必須由博弈的具體進程所決定完整和準確的圍棋盤面評估也無法靜態(tài)地完成過早的終結圍棋搜索無法得到有效的盤面評估結果（例如，α-β搜索）,無法驗證專家系統(tǒng)的落子選點,通過知識、規(guī)則和推理不可能構建高水平的計算機圍棋博弈專家系統(tǒng)知識和規(guī)則通常局限在局部和低層次上圍棋的知識和規(guī)則過于復雜，例外極多通過專家系統(tǒng)所產(chǎn)生的局部落子選點無法經(jīng)過嚴格的全局驗證,計算機圍棋博弈的發(fā)展歷史,傳統(tǒng)計算機圍棋博弈技術（1968至2005）現(xiàn)代計算機圍棋

6、博弈技術（2006至今）分水嶺（2006) -- UCT算法的出現(xiàn)及其在計算機圍棋博弈上的應用,傳統(tǒng)的計算機圍棋博弈技術,基于影響函數(shù)的形勢判斷使用模式生成落子候選點開局定式，手筋，等等。表示人類所使用的圍棋抽象串，群，眼，眼位，等等。局部搜索吃和逃（征子），連結和切斷，死活，等等。全局搜索（使用得非常有限）,現(xiàn)代計算機圍棋博弈技術,現(xiàn)代計算機圍棋博弈主要使用的關鍵技術：蒙特卡羅模擬（Monte Carlo Simul

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

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

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

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

12、it問題的算法可用于指導蒙特卡羅模擬在圍棋選點搜索上的應用,Multi-armed Bandit的UCB算法,UCB1算法：1.每個賭博角子機先玩一次2.以后每次選擇使右面公式最大化的賭博角子機平衡了探索與利用與最優(yōu)算法的差距不超過對數(shù)范圍,Xi是賭博角子機i的平均回報n是玩賭博角子機的總次數(shù)ni是玩賭博角子機i的次數(shù),參考文獻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算法和計算機圍棋博弈,計算機圍棋博弈中一個棋盤狀態(tài)下的選點是搜索樹上的極大極小搜索過程，在樹的每個節(jié)點上都面臨Multi-armed Bandit問題UCT算法是UCB算法在樹搜索上的應用參考文獻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計算機圍棋程序使用的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算法的局限性,作為在線機器學習的算法，UCT有其局限性圍棋知識沒有得到應用解決方法把在線學習UCT算法與傳統(tǒng)圍棋知識結合起來,蒙特卡羅樹搜索（MCTS）,蒙特卡羅樹搜索是把離線學習的知識與在線搜索的過程相結合的一種最優(yōu)優(yōu)先的搜索方法使用UCT算法進行在線搜索使用離線知識提高UCT搜索的效率,蒙特卡羅樹搜索的四個主要組成部分,搜索 – 通過UCT算法，遞歸地

17、從博弈樹的根節(jié)點向下搜索直至當前的葉子節(jié)點擴展 – 對當前的博弈樹葉子節(jié)點進行擴展模擬 – 從當前的博弈樹葉子節(jié)點開始進行蒙特卡羅模擬更新 – 把蒙特卡羅模擬的結果更新到搜索過程中博弈樹的每個節(jié)點上,離線知識在蒙特卡羅樹搜索中的使用,離線知識在蒙特卡羅樹搜索的四個組成部分中的使用搜索 – 使用知識進行UCT算法的初始化擴展 – 使用知識控制博弈樹擴展可選落子點的排序策略可選落子點的擴展策略可選落子點的剪枝策略模擬 –

18、使用知識指導蒙特卡羅模擬更新 – 按照UCT算法進行更新,基于知識的博弈樹擴展,可選落子點的排序策略蒙特卡羅樹搜索結束時，葉子節(jié)點的訪問次數(shù)很少；好的排序策略可以保證在有限時間內雙方最強的應手可以被搜索到Elo Rating – 根據(jù)離線知識靜態(tài)對可選落子點排序可選落子點的擴展策略Progressive Widening – 先擴展最強的落子選點可選落子點的剪枝策略適當?shù)募糁蓽p少搜索范圍，提高搜索效率參考文獻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.,基于知識的蒙特卡羅模擬,完全隨機的蒙特卡羅模擬效率不高蒙特卡羅模擬中加入圍棋知識以提高效率不填入自己的眼 - GobbleAMAF（所有落子如同第一手）- Gobble

20、模擬退火（逐漸減弱模擬中隨機性）- Gobble使用3x3模式 – Mogo優(yōu)先在關鍵點上落子（例如，點眼）- Mogo不在無效點上落子（例如，自殺） - Mogo參考文獻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.,高性能計算,在蒙特卡羅樹搜索算法實現(xiàn)相同的條件下，計算機圍棋的博弈水平取決于單位時間的計算量計算量大→模擬次數(shù)多→評估更準確計算量大→搜索的博弈樹更完整→評估更準確共享內存并行計算MoGo使用640核的Huygens超級計算機戰(zhàn)勝了韓國職業(yè)八段（十九路圍棋，讓九子） 分布式計算ManyFaces使用8臺4核工作站分布式計算戰(zhàn)勝了職業(yè)圍棋選手（十九路圍棋，讓七子）,總結與展望,九路圍棋計算機圍