《棋机器博弈关键技术分析.ppt》由会员分享，可在线阅读，更多相关《棋机器博弈关键技术分析.ppt（61页珍藏版）》请在三一办公上搜索。
1、,六子棋计算机博弈的关键技术分析,徐长明、徐心和、王翠荣2011.06.13,五子棋,入手,起源于中国发展在日本（棋型棋）Renju/Go-Moku棋盘 1515,五子棋机器博弈研究现状,入手,两种常见的五子棋均已经被成功破解Go-moku(无禁手):于1994年解决Renju(禁手):于2001年解决,花费了9000小时=375天。破解五子棋的重要因素借助了机器博弈当时恰好发现新算法TSS（Threat Space Search）+PNS(Proof Number Search)新的五子棋其规则变得复杂，致使趣味性大减,六子棋简介,入手,棋盘 19196子棋型为胜复杂度显著提高,吴毅成教授,
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类，而且，多属于PSPACE-complete(如奥赛罗)或EXPTIME-complete(如中
3、国象棋、西洋跳棋、国际象棋和围棋等)类问题。在机器博弈问题中，如此分类稍显粗糙。到底哪些棋类相对更难，以及难多少？,复杂度,入手,状态空间复杂度（从初始局面可达的）所有合法状态的数目。博弈树空间复杂度初始局面开始的解树（Solution Tree）中所有结点的数目。影响棋类复杂程度的因素平均分枝因子一盘游戏的平均步数棋盘大小,复杂度,入手,复杂度：计算复杂度为PSPACE-complete；平均分枝因子约为300；每盘棋平均30步。研究现状：涉及到k子棋（如五子棋和六子棋）复杂度的文献均高估了它的复杂度。,零,万事开头难，从哪里入手？,六子棋 发明人吴毅成教授网站：,简评：介绍六子棋规则、历史
4、、理论、台湾地区的六子棋活动等。其中，“六子棋教室”等栏目很有价值。,参考文献,入手,简评：很有价值的计算机博弈网站，里面有系统的入门资料。,六子棋 的对弈网站：,黄晨的象棋百科全书网站：,简评：大陆和台湾的六子棋高手聚集地。,Van den Herik,H.J.Uiterwijk,J.W.H.M.Van Rijswijck.Games solved:Now and in the future.Artificial Intelligence.2002.,简评：作者对计算机博弈有着深刻的认识，该文预测了的几种棋类的解决程度和大致时间，几乎逐一应验。,参考文献,入手,简评：很有价值的计算机博弈网站
5、，里面有系统的入门资料。,Wu,I.C.Huang,D.Y.A New Family of k-in-a-row Games.Advances in Computer Games.2006.,黄晨的象棋百科全书：,简评：介绍了六子棋的规则，给出了六子棋程序中应该采用的方法。,状态转换,六子棋计算机博弈！,状态转换,一,完整的局面信息应包含：盘面上的棋子布局 走棋方是哪方,局面的表示,知识表示,棋盘的编码,（举例）二维数组表示法：建立平面坐标系，如左图 自底向上 自左向右,棋盘的表示方法 数组表示 bit棋盘 bit向量,知识表示,(0,0)(0,1)(0,2)(0,18),(1,0),(1,1
6、8),(18,18),(18,0),棋盘的编码,（举例）一维数组表示法：建立平面坐标系，如左图 行优先 自左向右,知识表示,0 1 2 17 18,19,37,360,342,棋盘的编码（13*13棋盘为例）,知识表示,程序的知识源于何处？专家（人类大师或专业棋手）程序的自动推理,其它的高级知识,知识表示,K子棋数据表示存在的问题：基于交叉点的数据表示；缺乏从较高层级描述各个交叉点之间的紧密联系的方法和手段；虽然可能引入了模式，但这样的模式往往无法构成局面描述的基本单位；模式知识一般是不完整的，甚至主要依赖于程序设计者的个人经验，具有随意性。,其它的高级知识,知识表示,棋型,知识表示,在围棋中
7、，知识的表示用“模式”、串、龙等描述。这些知识是棋手总结的一些经验，关注的是棋子之间的配合、联络、分割、围地等。,六子棋比围棋简单得多。实际上，它在“模式”描述上要比围棋容易得多；而且我们能找到办法把那些可复用的知识描述和刻画得更精确。问题解决的难度受其表示方法影响。,棋型的抽取,知识表示,棋型及其诸属性棋型 c棋型的颜色 color(c)棋型的长度|c|棋型的形状|c|,棋型的起点 from(c)棋型的方向 orit(c)棋型的威胁数 th(c)棋型的类型 ct(c),棋型的表示,知识表示,全部连珠共划分为12个不相交的子集，即12种类型：(a)WIN；(b)DW；(c)L5；(d)D5；(
8、e)L4；(f)S4；(g)D4；(h)L3；(i)S3；(j)D3；(k)L2；(l)O。,棋型的分类,知识表示,获取棋型分类的方法,知识表示,黑方怎样获胜？,升变描述了在一个棋型中添加一枚同色棋子，它会演化为何种棋型。,棋型间的演化,知识表示,去除冗余的演化,知识表示,某些威胁类型之间的升变是非理性的，因而是冗余的。,连通度的计算,知识表示,威胁数的计算,知识表示,空交叉点的分类知识,知识表示,判断上述棋型中各个交叉点的价值,下列4个棋型，用交叉点的状态序列描述，交叉点上有黑子用X表示，交叉点空白用-表示。请指出：下列棋型的类型；如果黑方足够理性，哪个棋型是不可能出现的，为什么？XX-XX
9、XX-XX-XXXX-XXX-XX-XXX-XXX-XX-,思考题,知识表示,简评：很有价值的计算机博弈网站，里面有系统的入门资料。,六子棋 的对弈网站：,黄晨的象棋百科全书网站：,简评：大陆和台湾的六子棋高手聚集地。,状态转换,二,着法生成的策略：逐步生成。基于预置表生成。着法排序的策略：先将着法分类。再根据各个子类进行排序。,状态转换,三,37,估值函数设计的传统方法,估值函数设计的一般方法参数调整需高水平棋手的参与，且耗时甚巨；容易出错且严重依赖设计者的棋类领域知识；一种棋类的经验难以推广到其它棋类。例：国际跳棋的世界冠军程序Chinook的参数调整历时5年。,38,TD学习,TD学习自
10、动调整参数，无需人工干预对领域知识要求甚少，可通过自学习提高水平 例：自学习训练150万盘的西洋双陆棋TD-Gammon其水平已经全面超越人类顶尖高手。,39,TDLConn6的体系结构图,图 TDLConn6的体系结构图,40,TD学习算法的执行过程,图5.2 TD学习算法的执行过程,41,权值调整自动化BP神经元网络,输入层设计隐藏层设计输出层设计Sigmoid函数的选择g(x)=1/(1+exp(-x)用1.0表示取胜，0.5表示和棋，0.0表示输棋,42,整合先验知识与神经元网络的估值函数,估值函数 V(p)=S(p)+NN(p)(SMax()SMin()/(NNMax()NNMin(
11、);其中，优点：第一，兼顾了引入先验知识和自动调整权值的需求；第二，通过先验知识粗略勾勒出估值函数，通过神经元网络精调估值函数的权值，先验知识有助于加速训练的收敛；第三，通过参数来表达对先验知识的信心。,43,自学习训练样本的选择,图5.4 可应用TD学习的状态序列,状态转换,四,TSS,TSS是二值搜索，若求解成功，搜索算法会返回true或false。二值搜索需要预设一个二元问题，搜索的目标就是肯定该问题为真，或否定该问题：例如：“黑方能赢么？”对于TSS搜索，就是“MAX方（进攻方）能通过连续的威胁着法获胜么？”,TSS原理,黑DTSS胜的一个变化（轮黑走）,STSS举例,由左图可知：在上
12、图中黑可STSS胜,黑可TSS胜的一个局面（轮黑走）,TSS的形式化描述,表2 TSS搜索的相关记号、函数及其涵义,TSS的形式化描述,表3 TSS搜索的结果及其涵义,TSS的形式化描述,图1 描述DTSS策略递归规则的伪代码,TSS的扩展Anti-TSS,表2 Anti-TSS搜索的相关记号、函数及其涵义,TSS的扩展Anti-TSS,描述Anti-TSS策略规则的伪码,TSS搜索,一般采用深度优先搜索方式；难点：搜索的最大深度的设置；时间的控制；,深度优先的迭代加深搜索,DFID的执行过程如图所示：,DFID执行过程的示意图,55,DFID的特点,DFID的特点：以深度优先的方式模拟深度优先，因而可找到路径最短的解；浅层迭代对深层迭代有重要的启发作用；迭代加深的额外代价并不高；迭代加深为优化时间控制提供支持。,56,DFID-TSS搜索,DFID-TSS:将DFID与TSS搜索结合起来,实验:DFID-TSS vs.DF-TSS,实验:DFID-TSS vs.DF-TSS,60,NEUConn6的设计与实现,图6.1 NEUConn6的框架结构,
