六子棋机器博弈关键技术分析ppt课件

1、六子棋计算机博弈的关键技术分析,徐长明、徐心和、王翠荣 2011. 06. 13,五子棋,入手,起源于中国 发展在日本（棋型棋） Renju / Go-Moku 棋盘 1515,五子棋机器博弈研究现状,入手,两种常见的五子棋均已经被成功破解 Go-moku(无禁手):于1994年解决 Renju(禁手):于2001年解决,花费了9000小时=375天。 破解五子棋的重要因素 借助了机器博弈 当时恰好发现新算法TSS（Threat Space Search）+PNS(Proof Number Search) 新的五子棋其规则变得复杂，致使趣味性大减,六子棋简介,入手,棋盘 1919 6子棋型为胜

2、 复杂度显著提高,吴毅成教授,六子棋简介,入手,令connect(m, n, k, p, q) 代表一族k子棋，博弈的双方分别执黑和执白，黑先。赋予connect(m, n, k, p, q)下述涵义： 棋盘包含mn个交叉点。 黑第一次下q枚棋子，此后，双方轮流下p枚棋子。 在(水平的、垂直的、对角线方向的)任何一条线上，能率先形成本方连续不间断的k子序列者取胜；若双方均无法取胜，判和。 标准的六子棋是connect(19, 19, 6, 2, 1)，标准的五子棋是connect(15, 15, 5, 1, 1) 。,复杂度,入手,二人博弈问题一般至少属于NP-hard类，而且，多属于PSPA

3、CE-complete(如奥赛罗) 或EXPTIME-complete(如中国象棋、西洋跳棋、国际象棋和围棋等)类问题。 在机器博弈问题中，如此分类稍显粗糙。到底哪些棋类相对更难，以及难多少？,复杂度,入手,状态空间复杂度 （从初始局面可达的）所有合法状态的数目。 博弈树空间复杂度 初始局面开始的解树（Solution Tree）中所有结点的数目。 影响棋类复杂程度的因素 平均分枝因子 一盘游戏的平均步数 棋盘大小 ,复杂度,入手,复杂度： 计算复杂度为PSPACE-complete； 平均分枝因子约为300； 每盘棋平均30步。 研究现状：涉及到k子棋（如五子棋和六子棋）复杂度的文献均高估了

4、它的复杂度。,零,万事开头难，从哪里入手？,六子棋 发明人吴毅成教授网站：/web/index.php?option=com_content 其中， 优点： 第一，兼顾了引入先验知识和自动调整权值的需求； 第二，通过先验知识粗略勾勒出估值函数，通过神经元网络精调估值函数的权值，先验知识有助于加速训练的收敛； 第三，通过参数来表达对先验知识的信心。,43,自学习训练样本的选择,图5.4 可应用TD学习的状态序列,状态转换,四,TSS,TSS是二值搜索，若求解成功，搜索算法会返回true或false。 二值搜索需要预设一个二元问题，搜索的目标就是肯定该问

5、题为真，或否定该问题： 例如：“黑方能赢么？” 对于TSS搜索，就是“MAX方（进攻方）能通过连续的威胁着法获胜么？”,45,TSS原理,黑DTSS胜的一个变化（轮黑走）,46,STSS举例,由左图可知： 在上图中黑可STSS胜,黑可TSS胜的一个局面 （轮黑走）,47,TSS的形式化描述,表2 TSS搜索的相关记号、函数及其涵义,48,TSS的形式化描述,表3 TSS搜索的结果及其涵义,49,TSS的形式化描述,图1 描述DTSS策略递归规则的伪代码,50,TSS的扩展Anti-TSS,表2 Anti-TSS搜索的相关记号、函数及其涵义,51,TSS的扩展Anti-TSS,描述Anti-TSS策略规则的伪码,52,TSS搜索,一般采用深度优先搜索方式； 难点： 搜索的最大深度的设置； 时间的控制；,53,深度优先的迭代加深搜索,DFID的执行过程如图所示：,DFID执行过程的示意图,54,55,DFID的特点,DFID的特点： 以深度优先的方式模拟深度优先，因而可找到路径最短的解； 浅层迭代对深层迭代有重要的启发作用； 迭代加深的额外代价并不高； 迭代加深为优化时间控制提供支持。,56,DFID-TSS搜索,DFID-TSS: 将DFID与TSS搜索结合起来,实验: