计算机围棋博弈的最新发展

计算机围棋的最新发展北京邮电大学北邮九鼎计算机围棋研究所刘知青提纲计算机围棋博弈研究的意义及其主要困难计算机围棋博弈的发展历史传统的计算机围棋博弈技术现代的计算机围棋博弈技术蒙特卡罗模拟信心上限算法与信心上限应用树算法蒙特卡罗树搜索并行与分布式计算总结与展望计算机围棋博弈研究的意义科学技术意义机器学习模式识别自然语言理解分布式高性能计算社会意义国防建设教育娱乐围棋是最具挑战性的计算机博弈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算法UCB1算法：1.每个赌博角子机先玩一次2.以后每次选择使右面公式最大化的赌博角子机平衡了探索与利用与最优算法的差距不超过对数范围iinnxlog2•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.基于知识的蒙特卡罗模拟完全随机的蒙特卡罗模拟效率不高蒙特卡罗模拟中加入围棋知识以提高效率不填入自己的眼-GobbleAMAF（所有落子如同第一手）-Gobble模拟退火（逐渐减弱模拟中随机性）-Gobble使用3x3模式–Mogo优先在关键点上落子（例如，点眼）-Mogo不在无效点上落子（例如，自杀）-Mogo参考文献Gelly,S.,Wang,Y.,Munos,R.,andTeytaud,O.ModificationofUCTwithpatternsinMonte-CarloGo.TechnicalReport6062,INRIA,France,2006.高性能计算在蒙特卡罗树搜索算法实现相同的条件下，计算机围棋的博弈水平取决于单位时间的计算量计算量大→模拟次数多→评估更准确计算量大→搜索的博弈树更完整→评估更准确共享内存并行计算MoGo使用640核的Huygens超级计算机战胜了韩国职业八段（十九路围棋，让九子）分布式计算ManyFaces使用8台4核工作站分布式计算战胜了职业围棋选手（十九路围棋，让七子）总结与展望九路围棋计算机围棋博弈水平在当前软件和硬件技术上已接近人类最高水平未来几年可以看到计算机围棋博弈水平达到或超过人类最高水平十九路围棋计算机围棋博弈水平达到业余2段左右的水平（被让7-9个子）现有的计算机围棋博弈技术仍不足以挑战人类谢谢大家!