六子棋机器博弈关键技术分析.pptxVIP

六子棋机器博弈关键技术分析第1页/共62页第2页/共62页五子棋入手起源于中国发展在日本（棋型棋）Renju / Go-Moku棋盘 15×15第3页/共62页五子棋机器博弈研究现状入手两种常见的五子棋均已经被成功破解Go-moku(无禁手):于1994年解决Renju(禁手):于2001年解决,花费了9000小时=375天。破解五子棋的重要因素借助了机器博弈当时恰好发现新算法——TSS（Threat Space Search）+PNS(Proof Number Search)新的五子棋其规则变得复杂，致使趣味性大减第4页/共62页六子棋简介入手棋盘 19×196子棋型为胜复杂度显著提高吴毅成教授第5页/共62页六子棋简介入手令connect(m, n, k, p, q) 代表一族k子棋，博弈的双方分别执黑和执白，黑先。赋予connect(m, n, k, p, q)下述涵义：棋盘包含m×n个交叉点。黑第一次下q枚棋子，此后，双方轮流下p枚棋子。在(水平的、垂直的、对角线方向的)任何一条线上，能率先形成本方连续不间断的k子序列者取胜；若双方均无法取胜，判和。 标准的六子棋是connect(19, 19, 6, 2, 1)，标准的五子棋是connect(15, 15, 5, 1, 1) 。第6页/共62页复杂度入手二人博弈问题一般至少属于NP-hard类，而且，多属于PSPACE-complete(如奥赛罗) 或EXPTIME-complete(如中国象棋、西洋跳棋、国际象棋和围棋等)类问题。在机器博弈问题中，如此分类稍显粗糙。到底哪些棋类相对更难，以及难多少？第7页/共62页复杂度入手状态空间复杂度（从初始局面可达的）所有合法状态的数目。博弈树空间复杂度初始局面开始的解树（Solution Tree）中所有结点的数目。影响棋类复杂程度的因素平均分枝因子一盘游戏的平均步数棋盘大小……第8页/共62页复杂度入手复杂度：计算复杂度为PSPACE-complete；平均分枝因子约为300；每盘棋平均30步。研究现状：涉及到k子棋（如五子棋和六子棋）复杂度的文献均高估了它的复杂度。第9页/共62页零万事开头难，从哪里入手？第10页/共62页参考文献入手六子棋 发明人吴毅成教授网站：/web/index.php?option=com_contenttask=viewid=15Itemid=26.简评：介绍六子棋规则、历史、理论、台湾地区的六子棋活动等。其中，“六子棋教室”等栏目很有价值。六子棋 的对弈网站：/Connect6.aspx简评：大陆和台湾的六子棋高手聚集地。黄晨的象棋百科全书网站： /computer.htm简评：很有价值的计算机博弈网站，里面有系统的入门资料。第11页/共62页参考文献入手Van den Herik, H.J. Uiterwijk, J.W.H.M. Van Rijswijck. Games solved: Now and in the future. Artificial Intelligence. 2002.简评： 作者对计算机博弈有着深刻的认识，该文预测了的几种棋类的解决程度和大致时间，几乎逐一应验。 Wu, I.C. Huang, D.Y. A New Family of k-in-a-row Games. Advances in Computer Games. 2006.简评：介绍了六子棋的规则，给出了六子棋程序中应该采用的方法。黄晨的象棋百科全书： /computer.htm简评：很有价值的计算机博弈网站，里面有系统的入门资料。第12页/共62页第13页/共62页六子棋计算机博弈！状态转换第14页/共62页一状态转换第15页/共62页第16页/共62页局面的表示知识表示 完整的局面信息应包含： 盘面上的棋子布局 走棋方是哪方第17页/共62页棋盘的编码知识表示 棋盘的表示方法 数组表示 bit棋盘 bit向量(18, 18)(18, 0) （举例）二维数组表示法：建立平面坐标系，如左图 自底向上 自左向右(1, 18)(1, 0) (0, 0) (0, 1) (0, 2) … …(0,18) 第18页/共62页棋盘的编码知识表示360342 （举例）一维数组表示法：建立平面坐标系，如左图 行优先 自左向右3719 0 1 2 … …17 18 第19页/共62页棋盘的编码（13*13棋盘为例）知识表示第20页/共62页其它的高级知识知识表示程序的知识源于何处？ 专家（人类大师或专业棋手） 程序的自动推理第21页/共62页其它的高级知识知识表示K子棋数据表示存在的问题： 基于交叉点的数据表示； 缺乏从较高层级描述各个交叉点之间的紧密联系的方法和手段； 虽然可能引入了模式，但这样的模式往往无法构成