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

,六子棋计算机博弈的关键技术分析,徐长明、徐心和、王翠荣2011.06.13,五子棋,入手,起源于中国发展在日本（棋型棋）Renju/Go-Moku棋盘1515,五子棋机器博弈研究现状,入手,两种常见的五子棋均已经被成功破解Go-moku(无禁手):于1994年解决Renju(禁手):于2001年解决,花费了9000小时=375天。破解五子棋的重要因素借助了机器博弈当时恰好发现新算法TSS（ThreatSpaceSearch）+PNS(ProofNumberSearch)新的五子棋其规则变得复杂，致使趣味性大减,六子棋简介,入手,棋盘19196子棋型为胜复杂度显著提高,吴毅成教授,六子棋简介,入手,令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类，而且，多属于PSPACE-complete(如奥赛罗)或EXPTIME-complete(如中国象棋、西洋跳棋、国际象棋和围棋等)类问题。在机器博弈问题中，如此分类稍显粗糙。到底哪些棋类相对更难，以及难多少？,复杂度,入手,状态空间复杂度（从初始局面可达的）所有合法状态的数目。博弈树空间复杂度初始局面开始的解树（SolutionTree）中所有结点的数目。影响棋类复杂程度的因素平均分枝因子一盘游戏的平均步数棋盘大小,复杂度,入手,复杂度：计算复杂度为PSPACE-complete；平均分枝因子约为300；每盘棋平均30步。研究现状：涉及到k子棋（如五子棋和六子棋）复杂度的文献均高估了它的复杂度。,零,万事开头难，从哪里入手？,六子棋发明人吴毅成教授网站：/web/index.php?option=com_content其中，优点：第一，兼顾了引入先验知识和自动调整权值的需求；第二，通过先验知识粗略勾勒出估值函数，通过神经元网络精调估值函数的权值，先验知识有助于加速训练的收敛；第三，通过参数来表达对先验知识的信心。,.,43,自学习训练样本的选择,图5.4可应用TD学习的状态序列,状态转换,四,.,45,TSS,TSS是二值搜索，若求解成功，搜索算法会返回true或false。二值搜索需要预设一个二元问题，搜索的目标就是肯定该问题为真，或否定该问题：例如：“黑方能赢么？”对于TSS搜索，就是“MAX方（进攻方）能通过连续的威胁着法获胜么？”,.,46,TSS原理,黑DTSS胜的一个变化（轮黑走）,.,47,STSS举例,由左图可知：在上图中黑可STSS胜,黑可TSS胜的一个局面（轮黑走）,.,48,TSS的形式化描述,表2TSS搜索的相关记号、函数及其涵义,.,49,TSS的形式化描述,表3TSS搜索的结果及其涵义,.,50,TSS的形式化描述,图1描述DTSS策略递归规则的伪代码,.,51,TSS的扩展Anti-TSS,表2Anti-TSS搜索的相关记号、函数及其涵义,.,52,TSS的扩展Anti-TSS,描述Anti-TSS策略规则的伪码,.,53,TSS搜索,一般采用深度优先搜索方式；难点：搜索的最大深度的设置；时间的控制；,.,54,深度优先的迭代加深搜索,DFID的执行过程如图所示：,DFID执行过程的示意图,.,55,DFID的特点,DFID的特点：以深度优先的方式模拟深度优先，因而可找到路径最短的解；浅层迭代对深层迭代有重要的启发作用；迭代加深的额外代价并不高；迭代加深为优化时间控制提供支持。,.,56,DFID-TSS搜索,DFID-TSS:将DFID与TSS搜索结合起来,.,57,实验