计算机围棋博弈的最新发展-全国计算机博弈大赛.ppt

1、计算机围棋的最新发展,北京邮电大学北邮九鼎计算机围棋研究所刘知青,提纲,计算机围棋博弈研究的意义及其主要困难计算机围棋博弈的发展历史传统的计算机围棋博弈技术现代的计算机围棋博弈技术蒙特卡罗模拟信心上限算法与信心上限应用树算法蒙特卡罗树搜索并行与分布式计算总结与展望,计算机围棋博弈研究的意义,科学技术意义机器学习模式识别自然语言理解分布式高性能计算社会意义国防建设教育娱乐,围棋是最具挑战性的计算机博弈,1997年，许峰雄博士领导的IBM Deeper Blue团队在国际象棋上战胜了世界冠军。2006年，徐心和教授领导的东北大学棋天大圣团队在中国象棋上战平了全国冠军。围棋是唯一一个计算机博弈水平仍

2、远低于人类博弈水平的传统博弈现在，最强的19路计算机围棋能达到被职业棋手让大约7-9个子的水平。,计算机围棋博弈的基本方法,博弈树搜索通过搜索博弈树进行落子选点当博弈树搜索过程可以终结的时候，该搜索过程会找到最优落子点，并同时证明该落子选点是最优的专家系统通过使用具有知识、规则、推理的专家系统进行落子选点。,计算机围棋博弈的二大核心困难,搜索无法终结 无法有效地终结在围棋博弈树上的传统搜索过程围棋具有巨大的状态空间复杂度和博弈树复杂度提前终结搜索依赖于准确的静态盘面评估，而围棋从本质上无法做准确的静态盘面评估落子选点无法验证 围棋专家系统的构建非常复杂，其落子选点无法经过严格的验证（例如，数学

3、证明，或搜索验证）,巨大的状态空间和博弈树复杂度,围棋具有巨大的状态空间复杂度和博弈树复杂度状态空间复杂度（用于搜索）十九路围棋：10172国际象棋：1046中国象棋：1048博弈树复杂度（用于决策）十九路围棋： 10300 国际象棋： 10123 中国象棋： 10150,不可能的准确静态盘面评估,围棋从本质上无法做准确的静态盘面评估分析围棋棋子位置，数目的多少，以及棋子之间的静态关系（例如影响函数）无法完整地和准确地评判围棋棋子的作用与最终死活围棋棋子的作用与最终死活必须由博弈的具体进程所决定完整和准确的围棋盘面评估也无法静态地完成过早的终结围棋搜索无法得到有效的盘面评估结果（例如，-搜索）

4、,无法验证专家系统的落子选点,通过知识、规则和推理不可能构建高水平的计算机围棋博弈专家系统知识和规则通常局限在局部和低层次上围棋的知识和规则过于复杂，例外极多通过专家系统所产生的局部落子选点无法经过严格的全局验证,计算机围棋博弈的发展历史,传统计算机围棋博弈技术（1968至2005）现代计算机围棋博弈技术（2006至今）分水岭（2006) - UCT算法的出现及其在计算机围棋博弈上的应用,传统的计算机围棋博弈技术,基于影响函数的形势判断使用模式生成落子候选点开局定式，手筋，等等。表示人类所使用的围棋抽象串，群，眼，眼位，等等。局部搜索吃和逃（征子），连结和切断，死活，等等。全局搜索（使用得非常

5、有限）,现代计算机围棋博弈技术,现代计算机围棋博弈主要使用的关键技术：蒙特卡罗模拟（Monte Carlo Simulation）信心上限算法（UCB，Upper Confidence Bounds）信心上限应用树算法（UCT，UCB applied to Trees）蒙特卡罗树搜索（MCTS ，Monte Carlo Tree Search）高性能计算（High Performance Computing）,蒙特卡罗模拟,用于围棋形式评估从所需评估盘面开始进行随机对弈至终局把终局结果返回给所需评估盘面以大量模拟的期望值来评估该盘面参考文献Abramson, B. (1990). Expect

6、ed-outcome : a general model of static evaluation. IEEE transactions on PAMI, Vol. 12, pp. 182193.Bruegmann, B. (1993). Monte Carlo Go. http:/ Pentium，10000盘/秒九路围棋蒙特卡罗模拟十九路围棋的蒙特卡罗模拟速度大约是九路围棋的1/4选点可快速验证选点的优劣可根据终局结果在一定程度上得以验证终局结果通过中国围棋规则进行简单评判缓解了计算机围棋博弈的二大主要困难增加模拟时间可以方便地提高总体的评估效果,蒙特卡罗模拟的效果与局限性,蒙特卡罗模拟的

7、效果是明显的：1993年，Gobble在286PC上达到九路围棋25级的水平在UCT算法出现之前，蒙特卡罗模拟的效果已接近传统计算机围棋博弈技术的水平蒙特卡罗模拟有局限性：简单的、按正态分布选点进行蒙特卡罗模拟的效率很低,Multi-armed Bandit问题,Multi-armed Bandit问题K个独立赌博角子机（匪徒的臂）每个赌博角子机的回报满足一个未知的、静态的随机分布观测到的玩赌博角子机i的回报为：Xi,1, Xi ,2, . . .策略P会根据以往的玩的赌博角子机及其回报选择下一次玩的赌博角子机,Multi-armed Bandit和计算机围棋博弈,在计算机围棋博弈中，一个棋盘

8、状态下的选点问题就是一个Multi-armed Bandit问题一个棋盘状态就是一个多臂匪徒该棋盘状态下的每个可下选点就是该多臂匪徒的一只手臂能选择最优选点的计算机围棋对应于解决Multi-armed Bandit问题的最优策略解决Multi-armed Bandit问题的算法可用于指导蒙特卡罗模拟在围棋选点搜索上的应用,Multi-armed Bandit的UCB算法,UCB1算法：1.每个赌博角子机先玩一次2.以后每次选择使右面公式最大化的赌博角子机平衡了探索与利用与最优算法的差距不超过对数范围,Xi是赌博角子机i的平均回报n是玩赌博角子机的总次数ni是玩赌博角子机i的次数,参考文献Aue

9、r, P., Cesa-Bianchi, N., & Fischer, P. (2002a). Finite-time analysis of the multiarmed bandit problem. Ma-chine Learning, 47, 235-256.,UCT算法和计算机围棋博弈,计算机围棋博弈中一个棋盘状态下的选点是搜索树上的极大极小搜索过程，在树的每个节点上都面临Multi-armed Bandit问题UCT算法是UCB算法在树搜索上的应用参考文献L Kocsis and Cs Szepesvari. Bandit Based Monte-Carlo Planning. I

10、n 15th European Conference on Machine Learning (ECML), pages 282293, 2006.,UCT算法的伪代码,MoGo计算机围棋程序使用的UCT算法的伪代码 function playOneSequence(rootNode) node0 := rootNode; i := 0; do nodei+1 := descendByUCB1(nodei); i := i+1; while nodei is not first visited; createNode(nodei); nodei.value := getValueByMC(no

11、dei); updateValue(node,-nodei.value); end function;,UCT算法的局限性,作为在线机器学习的算法，UCT有其局限性围棋知识没有得到应用解决方法把在线学习UCT算法与传统围棋知识结合起来,蒙特卡罗树搜索（MCTS）,蒙特卡罗树搜索是把离线学习的知识与在线搜索的过程相结合的一种最优优先的搜索方法使用UCT算法进行在线搜索使用离线知识提高UCT搜索的效率,蒙特卡罗树搜索的四个主要组成部分,搜索 通过UCT算法，递归地从博弈树的根节点向下搜索直至当前的叶子节点扩展 对当前的博弈树叶子节点进行扩展模拟 从当前的博弈树叶子节点开始进行蒙特卡罗模拟更新 把蒙

12、特卡罗模拟的结果更新到搜索过程中博弈树的每个节点上,离线知识在蒙特卡罗树搜索中的使用,离线知识在蒙特卡罗树搜索的四个组成部分中的使用搜索 使用知识进行UCT算法的初始化扩展 使用知识控制博弈树扩展可选落子点的排序策略可选落子点的扩展策略可选落子点的剪枝策略模拟 使用知识指导蒙特卡罗模拟更新 按照UCT算法进行更新,基于知识的博弈树扩展,可选落子点的排序策略蒙特卡罗树搜索结束时，叶子节点的访问次数很少；好的排序策略可以保证在有限时间内双方最强的应手可以被搜索到Elo Rating 根据离线知识静态对可选落子点排序可选落子点的扩展策略Progressive Widening 先扩展最强的落子选点可

13、选落子点的剪枝策略适当的剪枝可减少搜索范围，提高搜索效率参考文献Coulom, 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模拟退火（逐渐减弱模拟中随机性）- Gobble使用3x3模式 Mogo优先在关键点上落子（例如

14、，点眼）- Mogo不在无效点上落子（例如，自杀） - Mogo参考文献Gelly, S., Wang, Y., Munos, R., and Teytaud, O. Modification of UCT with patterns in Monte-Carlo Go. Technical Report 6062, INRIA, France, 2006.,高性能计算,在蒙特卡罗树搜索算法实现相同的条件下，计算机围棋的博弈水平取决于单位时间的计算量计算量大模拟次数多评估更准确计算量大搜索的博弈树更完整评估更准确共享内存并行计算MoGo使用640核的Huygens超级计算机战胜了韩国职业八段（十九路围棋，让九子） 分布式计算ManyFaces使用8台4核工作站分布式计算战胜了职业围棋选手（十九路围棋，让七子）,总结与展望,九路围棋计算机围棋博弈水平在当前软件和硬件技术上已接近人类最高水平未来几年可以看到计算机围棋博弈水平达到或超过人类最高水平十九路围棋计算机围棋博弈水平达到业余2段左右的水平（被让7-9个子）现有的计算机围棋博弈技术仍不足以挑战人类,谢谢大家!,