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

國際象棋：10123

中國象棋：10150不可能的準確靜態盤面評估圍棋從本質上無法做準確的靜態盤面評估分析圍棋棋子位置，數目的多少，以及棋子之間的靜態關系（例如影響函數）無法完整地和準確地評判圍棋棋子的作用與最終死活圍棋棋子的作用與最終死活必須由博弈的具體進程所決定完整和準確的圍棋盤面評估也無法靜態地完成過早的終結圍棋搜索無法得到有效的盤面評估結果（例如，α-β搜索）無法驗證專家系統的落子選點通過知識、規則和推理不可能構建高水平的計算機圍棋博弈專家系統知識和規則通常局限在局部和低層次上圍棋的知識和規則過于復雜，例外極多通過專家系統所產生的局部落子選點無法經過嚴格的全局驗證計算機圍棋博弈的發展歷史傳統計算機圍棋博弈技術（1968至2005）現代計算機圍棋博弈技術（2006至今）分水嶺（2006)--UCT算法的出現及其在計算機圍棋博弈上的應用傳統的計算機圍棋博弈技術基于影響函數的形勢判斷使用模式生成落子候選點開局定式，手筋，等等。表示人類所使用的圍棋抽象串，群，眼，眼位，等等。局部搜索吃和逃（征子），連結和切斷，死活，等等。全局搜索（使用得非常有限）現代計算機圍棋博弈技術現代計算機圍棋博弈主要使用的關鍵技術：蒙特卡羅模擬（MonteCarloSimulation）信心上限算法（UCB，UpperConfidenceBounds）信心上限應用樹算法（UCT，UCBappliedtoTrees）蒙特卡羅樹搜索（MCTS，MonteCarloTreeSearch）高性能計算（HighPerformanceComputing）蒙特卡羅模擬用于圍棋形式評估從所需評估盤面開始進行隨機對弈至終局把終局結果返回給所需評估盤面以大量模擬的期望值來評估該盤面參考文獻Abramson,B.(1990).Expected-outcome:ageneralmodelofstaticevaluation.IEEEtransactionsonPAMI,Vol.12,pp.182–193.Bruegmann,B.(1993).MonteCarloGo.蒙特卡羅模擬的特點蒙特卡羅模擬可以看作是博弈樹上單個路徑上的搜索，并有以下二個特點：搜索可快速終結2GHzPentium，10000盤/秒九路圍棋蒙特卡羅模擬十九路圍棋的蒙特卡羅模擬速度大約是九路圍棋的1/4選點可快速驗證選點的優劣可根據終局結果在一定程度上得以驗證終局結果通過中國圍棋規則進行簡單評判緩解了計算機圍棋博弈的二大主要困難增加模擬時間可以方便地提高總體的評估效果蒙特卡羅模擬的效果與局限性蒙特卡羅模擬的效果是明顯的：1993年，Gobble在286PC上達到九路圍棋25級的水平在UCT算法出現之前，蒙特卡羅模擬的效果已接近傳統計算機圍棋博弈技術的水平蒙特卡羅模擬有局限性：簡單的、按正態分布選點進行蒙特卡羅模擬的效率很低Multi-armedBandit問題Multi-armedBandit問題K個獨立賭博角子機（匪徒的臂）每個賭博角子機的回報滿足一個未知的、靜態的隨機分布觀測到的玩賭博角子機i的回報為：Xi,1,Xi,2,...策略P會根據以往的玩的賭博角子機及其回報選擇下一次玩的賭博角子機Multi-armedBandit和計算機圍棋博弈在計算機圍棋博弈中，一個棋盤狀態下的選點問題就是一個Multi-armedBandit問題一個棋盤狀態就是一個多臂匪徒該棋盤狀態下的每個可下選點就是該多臂匪徒的一只手臂能選擇最優選點的計算機圍棋對應于解決Multi-armedBandit問題的最優策略解決Multi-armedBandit問題的算法可用于指導蒙特卡羅模擬在圍棋選點搜索上的應用Multi-armedBandit的UCB算法平衡了探索與利用與最優算法的差距不超過對數范圍Xi是賭博角子機i的平均回報n是玩賭博角子機的總次數ni是玩賭博角子機i的次數參考文獻Auer,P.,Cesa-Bianchi,N.,&Fischer,P.(2002a).Finite-timeanalysisofthemultiarmedbanditproblem.Ma-chineLearning,47,235-256.UCT算法和計算機圍棋博弈計算機圍棋博弈中一個棋盤狀態下的選點是搜索樹上的極大極小搜索過程，在樹的每個節點上都面臨Multi-armedBandit問題UCT算法是UCB算法在樹搜索上的應用參考文獻LKocsisandCsSzepesvari.BanditBasedMonte-CarloPlanning.In15thEuropeanConferenceonMachineLearning(ECML),pages282–293,2006.UCT算法的偽代碼MoGo計算機圍棋程序使用的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算法的局限性作為在線機器學習的算法，UCT有其局限性圍棋知識沒有得到應用解決方法把在線學習UCT算法與傳統圍棋知識結合起來蒙特卡羅樹搜索（MCTS）蒙特卡羅樹搜索是把離線學習的知識與在線搜索的過程相結合的一種最優優先的搜索方法使用UCT算法進行在線搜索使用離線知識提高UCT搜索的效率蒙特卡羅樹搜索的四個主要組成部分搜索–通過UCT算法，遞歸地從博弈樹的根節點向下搜索直至當前的葉子節點擴展–對當前的博弈樹葉子節點進行擴展模擬–從當前的博弈樹葉子節點開始進行蒙特卡羅模擬更新–把蒙特卡羅模擬的結果更新到搜索過程中博弈樹的每個節點上離線知識在蒙特卡羅樹搜索中的使用離線知識在蒙特卡羅樹搜索的四個組成部分中的使用搜索–使用知識進行UCT算法的初始化擴展–使用知識控制博弈樹擴展可選落子點的排序策略可選落子點的擴展策略可選落子點的剪枝策略模擬–使用知識指導蒙特卡羅模擬更新–按照UCT算法進行更新基于知識的博弈樹擴展可選落子點的排序策略蒙特卡羅樹搜索結束時，葉子節點的訪問次數很少；好的排序策略可以保證在有限時間內雙方最強的應手可以被搜索到EloRating–根據離線知識靜態對可選落子點排序可選落子點的擴展策略ProgressiveWidening–先擴展最強的落子選點可選落子點的剪枝策略適當的剪枝可減少搜索范圍，提高搜索效率參考文獻Coulom,R.(2007)ComputingEloRatingsofMovePatternsintheGameofGo,ICGAJournal,Vol.30,No.4.(December2007),pp.198-208.基于知識的蒙特卡羅模擬完全隨機的蒙特卡羅模擬效率不高蒙特卡羅模擬中加入圍棋知識以提高效率不填入自己的眼-GobbleAMAF（所有落子如同第一手）-Gobble模擬退火（逐漸減弱模擬中隨機性）-Gobble使用3x3模式–Mogo優先在關鍵點上落子（例如，點眼）-Mogo不在無效點上落子（例如，自殺）-Mogo參考文獻Gelly,S.,Wang,Y.,Munos,R.,andTeytaud,O.ModificationofUCTwithpatternsinMonte-CarloGo.TechnicalReport6062,INRIA,France,2006.高性能計算在蒙特卡羅樹搜索算法實現相同的條件下，計算機圍棋的博弈水平取決于單位時間的計算量計算量大→模擬次數多→評估更準確計算量大→搜索的博弈樹更完整→評估更準確共享內存并行計算MoGo使