六子棋培训讲义

六子棋培训讲义1.规则简介规则与五子棋非常相似，除了第一次黑方下一颗子外，之后黑白双方轮流每次各下两子，先连成六子者获胜。2.程序架构六子棋博弈程序和一般的博弈程序一样，一般包括一下几部分：2.1.棋盘表示棋盘表示主要探讨的是使用什么数据结构来表示棋盘上的信息。一般说来，这与具体的棋类知识密切相关。通常，用来描述棋盘及其上棋子信息的是一个二维数组。例如，对于六子棋，我们可以用一个二维数组ChessBoard[19][19]来表示棋盘，定义黑棋为0；白棋为1，空为0xFF。constintBlack=0,White=1,Empty=255;intChessBoard[19][19];2.2.棋型识别以19*19的二位整型数组作为输入，通过对棋盘4个维度（水平，竖直，左倾45°，右倾45°）的扫描，统计处各种棋形的数量。棋型一般包括:六连（Continuoussix）：+OOOOOO+，在棋盘的纵向、横向或斜向的任意一条线上，形成的6颗同色棋子相连。长连（Continuouslong）：+OOOOOOO+，在棋盘的纵向、横向或斜向的任意一条线上，形成的7颗或7颗以上同色棋子相连。六连或长连是六字获胜的必要条件。活五（Activefive）：+OOOOO+，在同一直线上的5颗同色棋子，符合“对方必须用两手棋才能挡住”的条件。挡住是指不让另一方形成六连或长连。眠五（Sleepfive）：XOOOOO+，在同一直线上的5颗同色棋子，符合“对方用一手棋就能挡住”的条件。活四（Activefour）：++OOOO++，在同一直线上的4颗同色棋子，符合“对方必须用两手棋才能挡住”的条件。眠四（Sleepfour）：XOOOO++，在同一直线上的4颗同色棋子，符合“对方用一手棋就能挡住”的条件。活三（Activethree）：+++OOO+++，在同一直线上的3颗同色棋子，符合“再下一手棋就能活四”的条件。朦胧三（Indistinctthree）：X++O+OO+X，在同一直线上的3颗同色棋子，符合“再下一手棋只能形成眠四，但如果再下两手棋的话就能形成活五”的条件。眠三（Sleepthree）：XOOO+++，在同一直线上的3颗同色棋子，符合“再下两手棋也只能形成眠五”的条件。活二（Activetwo）：++++OO++++，在同一直线上的2颗同色棋子，符合“再下两手棋就能形成活四”的条件。眠二（Sleeptwo）：XOO++++，在同一直线上的2颗同色棋子，符合“再下两手棋只能形成眠四”的条件。2.2.1.简单棋型识别算法简述1.从左到右从上到下扫描找出第一个非空点。2.以此点为中心分别在水平、垂直、左斜、右斜四个方向扫描棋型。3.将以参与扫描的点标记为“已分析”。4.读取下一个非空点，如果该点未被分析，则转1，否则转4，直至所有的点都已被分析。2.2.2.横向扫描1.从左到右从上到下扫描找出第一个点。2.以此点为中心分别向左右两个方向扩展，得到棋型的“相连边界”和“落子范围”，如图所示。3.计算中心相连部分的长度。4.根据中心相连的长度判断棋型，并将以参与扫描的点标记为“已分析”。2.2.3.其他方向扫描我们可以将垂直、左斜、右斜方向的棋型扫描转换为水平方向的棋型扫描。以从左上到右下方向扫描为例1.新建一个一维数组inttempLine[19]。2.找出待扫描点所在左45度斜线的起始位置//(y,x)为一行的起点if(ij){y=0;x=j-i;}else{x=0;y=i-j;}3.将该条斜线上的点复制到临时数组tempLine中for(k=0;kGRID_NUM;k++){//防止越界if(x+k=GRID_NUM||y+k=GRID_NUM)break;tempLine[k]=chessBoard[y+k][x+k];}4.按照水平扫描棋型的方法分析该临时数组5.标记扫描过的点2.3.评估系统根据棋型识别所得的结果对当前棋局进行评估，得到当前棋型的估值。一般来讲估值越大，局势对己方越有利。2.3.1.静态原始棋子位置得分也就是位置得固有得分。其分值分布为：天元点分值最大，沿其四周分数依次递减，棋盘四周分值最低。以19*19棋盘为例，我们可以建立静态棋子价值表。intPosValue[19][19]={{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},{0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0},{0,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,1,0},{0,1,2,3,3,3,3,3,3,3,3,3,3,3,3,3,2,1,0},{0,1,2,3,4,4,4,4,4,4,4,4,4,4,4,3,2,1,0},{0,1,2,3,4,5,5,5,5,5,5,5,5,5,4,3,2,1,0},{0,1,2,3,4,5,6,6,6,6,6,6,6,5,4,3,2,1,0},{0,1,2,3,4,5,6,7,7,7,7,7,6,5,4,3,2,1,0},{0,1,2,3,4,5,6,7,8,8,8,7,6,5,4,3,2,1,0},{0,1,2,3,4,5,6,7,8,9,8,7,6,5,4,3,2,1,0},{0,1,2,3,4,5,6,7,8,8,8,7,6,5,4,3,2,1,0},{0,1,2,3,4,5,6,7,7,7,7,7,6,5,4,3,2,1,0},{0,1,2,3,4,5,6,6,6,6,6,6,6,5,4,3,2,1,0},{0,1,2,3,4,5,5,5,5,5,5,5,5,5,4,3,2,1,0},{0,1,2,3,4,4,4,4,4,4,4,4,4,4,4,3,2,1,0},{0,1,2,3,3,3,3,3,3,3,3,3,3,3,3,3,2,1,0},{0,1,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,1,0},{0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0},{0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0},};2.3.2.对局势进行评估在对棋局进行分析时，可以分为两种，第一种：棋盘得整体扫描。以19路棋盘为例，需要计算19+19=38行阳线，（37-10）+（37-10）=54行阴线，共92路棋型得分。这里92路实际上可以划分为4个维度。即水平，竖直，左倾45°，右倾45°。第二种：以落子点（或记录的HP-3棋型）为中心，向外延展3格检查（若研究对象是棋型，那么只需由向量方向延展3格检查）。2.3.3.潜力值的影响有关潜力值得影响。活二，眠三，如上面定义的，看起来并不是很起眼。他虽然不像“四”、“五”，那样具有非常直观的杀伤力，但是他往往是决定成败的关键因素。这里在一次提到这个和Connect（6，2，1）的特性是密不可分的。如果在活二的基础上沿其方向再连续增添两子，而其中一子又能与其它己方棋型形成一个威胁度的话，那么就会马上获得胜利。据此我们可以设想构造一个形势评估函数（仅评估当前攻防趋势），如果一方没有活二，和一些分布分散（可以用向量分析方法）的眠三，那么我们可以判断，此方目前进攻形式不佳，只能加强防守，如果此时贸然冲四，可能导致顷刻告负。相反，如果另一方，分布相对集中的眠三，以及活二，那么我们可以考虑使用VCF战术。2.3.4.权值与参数值的优化评估函数的准确度直接影响着博弈程序的好坏，一个准确度差的博弈程序，即使搜索深度再深，也很难提高棋力，甚至还会离精确值越来越远。一般我们会对参数值进行人工调整。从经验上我们就可以得知，活四的价值要大于活三的价值，多个眠三的价值可能都小于一个活四的价值等等。将自己的这些猜测放入其中与机器反复对弈，然后改变参数，试验程序的能力是增强还是削弱了。在经过多次实验后，找出一组性能较高的参数。手工调整的方法很费时间。并且由于人同机器博弈时由于偏好、风格、疲劳程度以及博弈技术的限制，准确的分辨两组参数孰优孰劣并不容易。这时候，采用程序来辅助确定参数就有一定的必要了。下面介绍几种通过程序优化参数的方法：a.爬山法(Hill-Climbing).类似于交手法，每次对权重作很小的改变，测试改变后的表现，仅当成绩提高时才采纳这个改变，需要重复很多次.这个方法看上去很慢，并且只能找到“局部最优”的组合(即评价可能很差，但是任何很小的改变都会使评价更差)。b.模拟退火法(SimulatedAnnealing)。类似于爬山法，也是对权重做出改变来提高成绩的。但是如果改变没有提高成绩，有时候(随机地，给定一个几率)也采纳改变，试图跳出全局最优。这个方法需要给定一些几率，从几率高、梯度大的条件开始，然后逐渐减小。模拟退火法比爬山法更慢，但是最终可能得到比较好的值。c．遗传算法（Geneticalgorithms）。爬山法和模拟退火通过逐渐的改变参数来逼近一组较好的参数。而遗传算法则同时维护着几组较好的参数。通过向其中添加一组新参数，通常是将几组老参数中选出的值组合在一起作一点变化。然后同几组老的参数比较孰优孰劣。将最差的一组从中去除。这里面较重要的操作是交叉和变异操作。交叉通过随机交换父代个体的信息来继承已有参数中的优良内容。变异则通过随机改变个体中的基因而增加种群的多样性，避免优化的因局部震荡而失败。这一寻优算法由J.Holland于1975年提出。因其模仿生物的遗传机制（包括染色体的复制，交叉，变异等操作）而得名。详细内容请参考“计算机博弈培训班教材”。2.3.5.简单评估函数实例简单估值参考：棋型己方棋型分值六连10000朦胧三180活五1000眠三150眠五500活二150活四900朦胧二100眠四460眠二10活三350///summary///简单估值函数///获取nType方的评估值///summary/intGetEvaluatedValue(intchessBoard[][GRID_NUM],intnType){intwValue=0,bValue=0;scan(chessBoard);//计算估值bValue+=10000*TypeCount[Black][SIX];bValue+=1000*TypeCount[Black][FIVE];bValue+=900*TypeCount[Black][FOUR];bValue+=500*TypeCount[Black][SFIVE];bValue+=460*TypeCount[Black][SFOUR];bValue+=350*TypeCount[Black][THREE];bValue+=180*TypeCount[Black][MTHREE];bValue+=150*TypeCount[Black][STHREE];bValue+=150*TypeCount[Black][TWO];bValue+=100*TypeCount[Black][MTWO];bValue+=10*TypeCount[Black][STWO];wValue+=10000*TypeCount[White][SIX];wValue+=1000*TypeCount[White][FIVE];wValue+=900*TypeCount[White][FOUR];wValue+=500*TypeCount[White][SFIVE];wValue+=460*TypeCount[White][SFOUR];wValue+=350*TypeCount[White][THREE];wValue+=180*TypeCount[White][MTHREE];wValue+=150*TypeCount[White][STHREE];wValue+=150*TypeCount[White][TWO];wValue+=100*TypeCount[White][MTWO];wValue+=10*TypeCount[White][STWO];if(nType==White