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