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

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）,蒙特卡罗模拟,用于围棋形式评估 从所需评估盘面开始 进行随机对弈至终局 把终

6、局结果返回给所需评估盘面 以大量模拟的期望值来评估该盘面 参考文献 Abramson, B. (1990). Expected-outcome : a general model of static evaluation. IEEE transactions on PAMI, Vol. 12, pp. 182193. Bruegmann, B. (1993). Monte Carlo Go. ,蒙特卡罗模拟的特点,蒙特卡罗模拟可以看作是博弈树上单个路径上的搜索，并有以下二个特点： 搜索可快速终结 2GHz Pentium，10000盘/秒九路围棋蒙特卡罗模拟 十九路围棋的蒙特卡罗模拟速度大约是

7、九路围棋的1/4 选点可快速验证 选点的优劣可根据终局结果在一定程度上得以验证 终局结果通过中国围棋规则进行简单评判 缓解了计算机围棋博弈的二大主要困难 增加模拟时间可以方便地提高总体的评估效果,蒙特卡罗模拟的效果与局限性,蒙特卡罗模拟的效果是明显的： 1993年，Gobble在286PC上达到九路围棋25级的水平 在UCT算法出现之前，蒙特卡罗模拟的效果已接近传统计算机围棋博弈技术的水平 蒙特卡罗模拟有局限性： 简单的、按正态分布选点进行蒙特卡罗模拟的效率很低,Multi-armed Bandit问题,Multi-armed Bandit问题 K个独立赌博角子机（匪徒的臂） 每个赌博角子机的

8、回报满足一个未知的、静态的随机分布 观测到的玩赌博角子机i的回报为：Xi,1, Xi ,2, . . . 策略P会根据以往的玩的赌博角子机及其回报选择下一次玩的赌博角子机,Multi-armed Bandit和计算机围棋博弈,在计算机围棋博弈中，一个棋盘状态下的选点问题就是一个Multi-armed Bandit问题 一个棋盘状态就是一个多臂匪徒 该棋盘状态下的每个可下选点就是该多臂匪徒的一只手臂 能选择最优选点的计算机围棋对应于解决Multi-armed Bandit问题的最优策略 解决Multi-armed Bandit问题的算法可用于指导蒙特卡罗模拟在围棋选点搜索上的应用,Multi-a

9、rmed Bandit的UCB算法,UCB1算法：1.每个赌博角子机先玩一次2.以后每次选择使右面公式最大化的赌博角子机 平衡了探索与利用 与最优算法的差距不超过对数范围,Xi是赌博角子机i的平均回报 n是玩赌博角子机的总次数 ni是玩赌博角子机i的次数,参考文献 Auer, P., Cesa-Bianchi, N., i := 0; do nodei+1 := descendByUCB1(nodei); i := i+1; while nodei is not first visited; createNode(nodei); nodei.value := getValueByMC(node

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

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

12、ning 先扩展最强的落子选点 可选落子点的剪枝策略 适当的剪枝可减少搜索范围，提高搜索效率 参考文献 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.,基于知识的蒙特卡罗模拟,完全随机的蒙特卡罗模拟效率不高 蒙特卡罗模拟中加入围棋知识以提高效率 不填入自己的眼 - Gobble AMAF（所有落子如同第一手）- Gobble 模拟退火（逐渐减弱模拟中随机性）- Gobble

13、 使用3x3模式 Mogo 优先在关键点上落子（例如，点眼）- 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超级计