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

六子棋计算机博弈的关键技术分析徐长明、徐心和、王翠荣2011.06.13五子棋入手•起源于中国•发展在日本（棋型棋）•Renju/Go-Moku•棋盘15×15五子棋机器博弈研究现状入手•两种常见的五子棋均已经被成功破解•Go-moku(无禁手):于1994年解决•Renju(禁手):于2001年解决,花费了9000小时=375天。•破解五子棋的重要因素•借助了机器博弈•当时恰好发现新算法——TSS（ThreatSpaceSearch）+PNS(ProofNumberSearch)•新的五子棋其规则变得复杂，致使趣味性大减六子棋简介入手•棋盘19×19•6子棋型为胜•复杂度显著提高吴毅成教授六子棋简介入手令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)。复杂度入手二人博弈问题一般至少属于NP-hard类，而且，多属于PSPACE-complete(如奥赛罗)或EXPTIME-complete(如中国象棋、西洋跳棋、国际象棋和围棋等)类问题。在机器博弈问题中，如此分类稍显粗糙。到底哪些棋类相对更难，以及难多少？复杂度入手状态空间复杂度（从初始局面可达的）所有合法状态的数目。博弈树空间复杂度初始局面开始的解树（SolutionTree）中所有结点的数目。影响棋类复杂程度的因素平均分枝因子一盘游戏的平均步数棋盘大小……复杂度入手复杂度：计算复杂度为PSPACE-complete；平均分枝因子约为300；每盘棋平均30步。研究现状：涉及到k子棋（如五子棋和六子棋）复杂度的文献均高估了它的复杂度。零万事开头难，从哪里入手？1.六子棋发明人吴毅成教授网站：=com_content&task=view&id=15&Itemid=26.简评：介绍六子棋规则、历史、理论、台湾地区的六子棋活动等。其中，“六子棋教室”等栏目很有价值。参考文献入手简评：很有价值的计算机博弈网站，里面有系统的入门资料。2.六子棋的对弈网站：黄晨的象棋百科全书网站：简评：大陆和台湾的六子棋高手聚集地。4.VandenHerik,H.J.Uiterwijk,J.W.H.M.VanRijswijck.Gamessolved:Nowandinthefuture.ArtificialIntelligence.2002.简评：作者对计算机博弈有着深刻的认识，该文预测了的几种棋类的解决程度和大致时间，几乎逐一应验。参考文献入手简评：很有价值的计算机博弈网站，里面有系统的入门资料。5.Wu,I.C.Huang,D.Y.ANewFamilyofk-in-a-rowGames.AdvancesinComputerGames.2006.6.黄晨的象棋百科全书：简评：介绍了六子棋的规则，给出了六子棋程序中应该采用的方法。一•棋盘•棋子•着法•规则•博弈树•其它因素：玩家、进攻、防守…基本知识表示•启发知识•杀手着法表•历史着法表•临时记忆的中间计算结果•置换表•拒绝表•长期记忆和维护的结论•开局库（多基于经验）•残局库（基于推理）•知识库（多基于归纳）基本知识表示完整的局面信息应包含：盘面上的棋子布局走棋方是哪方局面的表示知识表示棋盘的编码（举例）二维数组表示法：建立平面坐标系，如左图自底向上自左向右棋盘的表示方法数组表示bit棋盘bit向量知识表示(0,0)(0,1)(0,2)……(0,18)(1,0)(1,18)(18,18)(18,0)棋盘的编码（举例）一维数组表示法：建立平面坐标系，如左图行优先自左向右知识表示012……17181937360342000001002003004005006007008009010011012013014015016017018019020021022023024025026027028029030031032033034035036037038039040041042043044045046047048049050051052053054055056057058059060061062063064065066067068069070071072073074075076077078079080081082083084085086087088089090091092093094095096097098099100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168棋盘的编码（13*13棋盘为例）知识表示程序的知识源于何处？专家（人类大师或专业棋手）程序的自动推理其它的高级知识知识表示K子棋数据表示存在的问题：基于交叉点的数据表示；缺乏从较高层级描述各个交叉点之间的紧密联系的方法和手段；虽然可能引入了模式，但这样的模式往往无法构成局面描述的基本单位；模式知识一般是不完整的，甚至主要依赖于程序设计者的个人经验，具有随意性。其它的高级知识知识表示棋型知识表示在围棋中，知识的表示用“模式”、串、龙等描述。这些知识是棋手总结的一些经验，关注的是棋子之间的配合、联络、分割、围地等。六子棋比围棋简单得多。实际上，它在“模式”描述上要比围棋容易得多；而且我们能找到办法把那些可复用的知识描述和刻画得更精确。问题解决的难度受其表示方法影响。棋型的抽取知识表示•棋型及其诸属性棋型c棋型的颜色color(c)棋型的长度|c|棋型的形状||c||18171615141312111098765432101817161514131211109876543210ACBDE棋型的起点from(c)棋型的方向orit(c)棋型的威胁数th(c)棋型的类型ct(c)181716151413121110987654321021323000000000000001000000110100001低位高位棋型的表示知识表示(a)(b)(c)(d)(e)(f)(g)(h)(i)(j)(k)(l)全部连珠共划分为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。棋型的分类知识表示获取棋型分类的方法知识表示黑方怎样获胜？•升变描述了在一个棋型中添加一枚同色棋子，它会演化为何种棋型。L2S3L3D3OD4L4L5DWD5WINS4l£2l=2l=3l=4l=56£l棋型间的演化知识表示去除冗余的演化知识表示L2S3L3D3OD4L4L5DWD5WINS4•某些威胁类型之间的升变是非理性的，因而是冗余的。连通度的计算知识表示威胁数的计算知识表示空交叉点的分类知识知识表示判断上述棋型中各个交叉点的价值1.下列4个棋型，用交叉点的状态序列描述，交叉点上有黑子用‘X’表示，交叉点空白用‘-’表示。请指出：下列棋型的类型；如果黑方足够理性，哪个棋型是不可能出现的，为什么？(1)XX--XXXX-XX-XXXX-XX(2)X--XX-XXX--XXX--XX-思考题知识表示简评：很有价值的计算机博弈网站，里面有系统的入门资料。2.六子棋的对弈网站：黄晨的象棋百科全书网站：简评：大陆和台湾的六子棋高手聚集地。二着法生成的策略：•逐步生成。•基于预置表生成。着法排序的策略：•先将着法分类。•再根据各个子类进行排序。三37估值函数设计的传统方法•估值函数设计的一般方法–参数调整需高水平棋手的参与，且耗时甚巨；–容易出错且严重依赖设计者的棋类领域知识；–一种棋类的经验难以推广到其它棋类。例：国际跳棋的世界冠军程序Chinook的参数调整历时5年。38TD学习•TD学习–自动调整参数，无需人工干预–对领域知识要求甚少，可通过自学习提高水平例：自学习训练150万盘的西洋双陆棋TD-Gammon其水平已经全面超越人类顶尖高手。39TDLConn6的体系结构图TDLer.EXE(TDlearner)Conn6_B.EXE(gametreesearchengine)Conn6_W.EXE(gametreesearchengine)父进程子进程1训练（局面）集棋谱文件子进程2TDNetNeuralNetNeuralNet网络权值文件Record.txtGame1Game2Game3…TrainSet.txtPosition1Position2Position3...Weight.txtWeight1Weitht2Weight3…统计信息文件Statistic.txtSomeusefulinformation…E.g.Winrate,Drawrate,etc.着法写入创建或撤销写入写入创建或撤销着法读入读入读入图TDLConn6的体系结构图40TD学习算法的执行过程第二时间顺序x1x2xt+1Pmxmz......xt局面的状态序列将神经元网络用作黑盒应用反向传播算法P1P2Pt+1PtP2–P1Pt–Pt–1Pt+1–PtPm–Pm–1z–Pm估值序列(f1,1,…f1,n)(f2,1,…f2,n)(ft,1,…ft,n)(ft+1,1,…ft+1,n)(fm,1,…fm,n)特征向量z............权值的增量序列更新权值即时差分值序列DwmDw1Dw2Dwm–1Dwt............抽取局面特征第一时间顺序每个时刻t所面临的操作和状态¬w+åDwi用神经元网络估值TD学习过程时刻m12t+1tm+1......权值调整自动化——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());其中，•优点：–第一，兼顾了引入先验知识和自动调整权值的需求；–第二，通过先验知识粗略勾勒出估值函数，通过神经元网络精调估值函数的权值，先验知识有助于加速训练的收敛；–第三，通过参数来表达对先验知识的信心。43自学习训练样本的选择xcxc+1xm+1xnz=xn+1......z=xm...TSS(xm,A,A)=trueÚAnti-TSS(xm,A,A)=false原始序列：TD序列：x1x2...xmxc+1根据棋规对弈结束随机生成的着法TSS着法应用TD学习的状态序列图5.4可应用TD学习的状态序列四TSS•TSS是二值搜索，若求解成功，搜索算法会返回true或false。•二值搜索需要预设一个二元问题，搜索的目标就是肯定该问题为