五子棋人机对战设计-蒲公英云

一、人机对战算法概述

人机对战属于一种弱人工智能算法，其核心是：当玩家落下一枚棋子后，计算出这枚棋子构成的所有棋型，找出威胁程度最大的棋型，并破解其产生的威胁。

五子棋中所能产生的棋型有很多，如果棋子至少有一边被封死，这种棋型被称为“死”棋型，反之被称为“活”棋型。根据棋子的数量，棋型又可以细化为“活三”、“死三”、“活四”等不同的棋型。棋型的不同，产生的威胁程度不同，破解的方式也不同。以四枚棋子为例，列出所有棋型及其威胁值和破解方法，如图4.16所示。

Center

图4.16 四个棋子所产生的棋型及其威胁值和破解方法

说明：棋型就是棋子在棋盘上组合成的形状。

二、电脑自动处理用户请求

玩家联机对战的时候，是在各自电脑中处理对方的指令。但是玩家与电脑对战，则是在一台电脑中同时处理玩家和电脑的指令，这种情况下就不能再使用联机对战的命令处理逻辑了。在AI（电脑智能对战算法）类中，编写oprationHandler()方法，来专门处理玩家向电脑发来的指令。由于本程序取消了人机对战中的“认输”、“和棋”、“悔棋”命令，所以只处理玩家的“开始”命令即可。具体代码如下。

01 publicvoid oprationHandler(Object messageObj) { 02 intcode = (Integer) messageObj; // 获取命令代码 03 switch (code) { // 判断命令 04 case ChessPanel.OPRATION_START_MACHINE: // 如果是玩家请求开始游戏 05 frame.getChessPanel1().setTowardsStart(true); // 设置AI的游戏开始状态为true 06 break; 07 }

三、电脑判断落棋点

电脑判断落棋点总共分四个步骤：第一步，遍历整个棋盘，获取每个棋子坐标；第二步，以一个棋子为中心，获取其四个直线方向排列的所有棋子；第三步，判断此直线排列的棋子中是否出现了有威胁的棋型；第四部，根据棋型库给出的棋型和破解方法，记录其威胁值和破解方案。下面将详细介绍这四个步骤是如何实现的。

遍历整个棋盘，寻找落棋点

执行AI类中forEach()方法，此方法可以获取电脑最终给定的下棋位置。遍历整个棋盘，查看每一个棋子所能形成的棋型，找出其中威胁最大的，根据棋型库给出的破解位置找出落棋点。具体代码如下：

01 privateint[] forEach() { 02 intx = -1, y = -1; // 将要下的棋子坐标 03 intthreat = 0; // 棋盘上出现的最大威胁值 04 byte[][] chessmanArray = gobangModel1.getChessmanArray(); // 获得棋盘 05 for (inti = 0; i< 15; i++) { // 遍历棋盘行 06 for (intj = 0; j< 15; j++) { // 遍历棋盘列 07 if (chessmanArray[i][j] > 0) { // 如果此处有白棋子 08 // 捕捉每个棋子形成的棋型 09 inttmp[] = catchChessModle(i, j, chessmanArray); 10 // 如果存在比当前最大威胁值还要大的威胁值，则记录此处落子坐标 11 if (tmp[0] >threat) { 12 threat = tmp[0]; // 更新最大威胁值 13 x = tmp[1]; // 更新落子横坐标 14 y = tmp[2]; // 更新落子纵坐标 15 } 16 } 17 } 18 } 19 returnnewint[] { x, y }; // 返回横纵坐标组成的一维数组 20 }

判断棋子构成的棋型

forEach()方法中调用了catchChessModle()方法，这个方法以一枚棋子为原点向四种方位延伸，分别判断这四条线上可能产生具有威胁的棋型，并根据棋型库给出的破解位置，换算成棋盘坐标，并返回成结果数组。具体代码如下：

01 privateint[] catchChessModle(intx, inty, byte[][] chessmanArray) { 02 // 索引0：记录此位置的棋子可产生的最大威胁值或优势值 03 // 索引1：对应下棋横坐标 04 // 索引2：对应下棋横坐标 05 intposition[] = newint[3]; 06 // 创建以被捕捉棋子为中心的四个方向形成的棋型 07 // 以参数点为中心点，保存四个方向的棋型，方向分别为 — | \ / 08 intmodel[][] = newint[4][11]; 09 for (inttmp[] : model) { // 遍历数组 10 Arrays.fill(tmp, boundary); // 将数组填充为边界常量 11 } 12 // 把参数点放入每行的中心部位 13 model[0][5] = model[1][5] = model[2][5] = model[3][5] = chessmanArray[x][y]; 14 // 以该棋子为中心，向两边走5步 15 for (inti = 1; i<= 5; i++) { 16 // 水平方向棋型 17 if (x - i>= 0) { // 如果没有走出边界 18 model[0][5 - i] = chessmanArray[x - i][y]; // 将左侧棋子记录到水平棋型当中 19 } 20 if (x + i<= 14) { // 如果没有走出边界 21 model[0][5 + i] = chessmanArray[x + i][y]; // 将右侧棋子记录到水平棋型当中 22 } 23 24 // 垂直方向棋型 25 if (y - i>= 0) { // 如果没有走出边界 26 model[1][5 - i] = chessmanArray[x][y - i]; // 将上方棋子记录到垂直棋型当中 27 } 28 if (y + i<= 14) { // 如果没有走出边界 29 model[1][5 + i] = chessmanArray[x][y + i]; // 将下方棋子记录到垂直棋型当中 30 } 31 32 // 反斜杠方向棋型 33 if (x - i>= 0 &&y + i<= 14) { // 如果没有走出边界 34 // 将左下方棋子记录到反斜棋型当中 35 model[2][5 - i] = chessmanArray[x - i][y + i]; 36 } 37 if (x + i<= 14 &&y - i>= 0) { // 如果没有走出边界 38 // 将右上方棋子记录到反斜棋型当中 39 model[2][5 + i] = chessmanArray[x + i][y - i]; 40 } 41 42 // 正斜杠方向棋型 43 if (x - i>= 0 &&y - i>= 0) { // 如果没有走出边界 44 // 将左上方棋子记录到正斜棋型当中 45 model[3][5 - i] = chessmanArray[x - i][y - i]; 46 } 47 if (x + i<= 14 &&y + i<= 14) { // 如果没有走出边界 48 // 将右下方棋子记录到正斜棋型当中 49 model[3][5 + i] = chessmanArray[x + i][y + i]; 50 } 51 } 52 intscore = 0; // 记录最大评分（威胁值） 53 intdirection = -1; // 记录最大评分的方向（model数组一维下标） 54 intindex = 0; // 记录坐标偏移量(judgeModle()方法给予的破解位置) 55 for (inti = 0; i<model.length; i++) { // 遍历棋型数组 56 intgetResult[] = judgeModle(model[i]); // 针对此方向棋型，给予破解方案 57 if (score<getResult[1]) { // 如果出现比当前最大威胁值还要大的威胁 58 score = getResult[1]; // 更新最大分（威胁值） 59 // 被捕捉的棋子在模型中的索引为5，getResult[0]为破解方案中的下棋索引位置 60 // getResult[0] - 5 = 破解位置距离被捕捉的棋子的索引位置 61 index = getResult[0] - 5; 62 direction = i; // 记录此棋型的方向 63 } 64 } 65 switch (direction) { // 判断最大威胁值所在的方向 66 case 0: // 如果是水平方向 67 x += index; // 下棋的位置是原位置向右（或向左）偏移index的值 68 break; 69 case 1: // 如果是垂直方向 70 y += index; // 下棋的位置是原位置向下（或向上）偏移index的值 71 break; 72 case 2: // 如果是反斜方向 73 x += index; // 下棋的位置是原位置向右（或向左）偏移index的值 74 y -= index; // 下棋的位置是原位置向上（或向下）偏移index的值 75 break; 76 case 3: // 如果是正斜方向 77 x += index; // 下棋的位置是原位置向右（或向左）偏移index的值 78 y += index; // 下棋的位置是原位置向下（或向上）偏移index的值 79 break; 80 } 81 position[0] = score; // 记录此棋子的最大评分（威胁值） 82 position[1] = x; // 记录对应下棋横坐标 83 position[2] = y; // 记录对应下棋纵坐标 84 85 returnposition; // 返回结果数组 86 }

获取棋型威胁值及其破解方法

catchChessModle()中调用了judgeModle()方法，这个方法可以给出具体棋型的威胁值和相应破解位置。首先将一行棋子转换为字符串，然后查找字符串中是否出现与棋型库中相匹配的棋型，找出其中威胁值最大棋型，记录其的威胁值和落棋点并返回成结果数组。具体代码如下：

01 publicint[] judgeModle(intmodel[]) { 02 intpiont[] = newint[2]; // 初始化返回结果数组 03 intscore = 0; // 记录最大评分 04 StringBuffer sb = new StringBuffer(); // 准备将棋型数组保存为字符串的StringBuffer 05 for (intnum : model) { // 遍历数组，将数组变成字符串 06 if (num == GobangModel.BLACK_CHESSMAN) { // 如果是黑子 07 num = 4; // 改为其他数字，以免负号会占字符 08 } 09 sb.append(num); // 字符串添加此数字 10 } 11 Object library[][] = getModelLibrary(); // 获取棋型库中所有棋型及其解决方案 12 for (inti = 0; i<library.length; i++) { // 遍历棋型库 13 String chessModel = (String) library[i][0];// 获取库中棋型 14 intmodelIndex = -1; // 临时变量，用于保存某棋型在字符串中出现的索引位置 15 // 如果存在此棋型，则将棋型出现的位置付给modelIndex 16 if ((modelIndex = sb.indexOf(chessModel)) != -1) { 17 intscoreInLib = (int) library[i][1]; // 获取棋型评分 18 intstepIndex = (int) library[i][2]; // 获取对应的下棋位置 19 if (score<scoreInLib) { // 如果出现更高的评分 20 score = scoreInLib; // 更新最大分 21 // 记录应该(在这一行中)下棋的实际索引位置。 22 // 棋型在字符串中的索引位置 + 棋型给出的解决位置 = 字符串中的解决位置 23 piont[0] = modelIndex + stepIndex; 24 piont[1] = score; // 记录最大分数 25 } 26 } 27 } 28 returnpiont; // 返回结果数组