五子棋AI（二）

1、实现AI走棋

1.1　设计AI的数据成员

---

• 添加棋盘数据成员，以表示对哪个棋盘下棋。
• 添加评分数组chess[MAX_BORDER][MAX_BORDER]， 用来存储AI对棋盘所有落点的价值评估。

---

AI.h

private:
	Chess* ch;

再添加评分数组,为防止二次定义，我们使用extern关键词进行规避该风险。

chess.h

extern int chess[MAX_BORDER][MAX_BORDER];

1.2　对AI进行初始化

//AI初始化
void AI::Init(Chess* chess)
{
	this->ch = chess;
}

2、评估函数

对于五子棋AI而言，最重要的就是它的评估函数。评估函数网上大概有两种，但是很多人会弄混淆。

• 第一种函数暂且命名为Current函数（只是一个代号，与第二种相区别），它是对一个可走的空位子进行打分，如果AI将棋子落在这个空位置的分数越高，说明这个位置就越好，每次AI走棋就找到一个最好的空位置就行了。

• 第二种函数称为Global函数，是对现在的棋盘局面进行打分。 AI棋子首先找所有可以走的空位置，模拟走了这个位置以后，用Global函数进行局面评分，如果走了这样的一个空位置的得分越高，说明这个位置就越好，每次AI走棋就找这样一个分数最高的位置。

这两个评估函数的区别非常大！如果你只是想实现一个只看一步的AI，那么你可以用Current函数也可以用Global函数。但是如果你想要实现基于博弈树的Min-Max算法和α-β剪枝算法的AI，就只能用Global函数，因为AI必须要对局面打分，而不是对位置打分。

对局势的判断要怎样做才会有个准确的估计呢？其实五子棋的局势无非就是对棋型个数和权重的统计。

2.1　五子棋基本棋型介绍

最常见的基本棋型有以下几种：连五，活四，冲四，活三，眠三，活二，眠二。
具体可参考：http://game.onegreen.net/wzq/HTML/142336.html

① 连五：顾名思义，五颗同色棋子连在一起，不需要多讲。
　　　　　　　
②活四：有两个连五点（即有两个点可以形成五），图中白点即为连五点。
稍微思考一下就能发现活四出现的时候，如果对方单纯过来防守的话，是已经无法阻止自己连五了

③冲四：有一个连五点，如下面三图，均为冲四棋型。图中白点为连五点。
相对比活四来说，冲四的威胁性就小了很多，因为这个时候，对方只要跟着防守在那个唯一的连五点上，冲四就没法形成连五。
　　　　　　　　　　　　
④活三：可以形成活四的三，如下图，代表两种最基本的活三棋型。图中白点为活四点。
活三棋型是我们进攻中最常见的一种，因为活三之后，如果对方不以理会，将可以下一手将活三变成活四，而我们知道活四是已经无法单纯防守住了。所以，当我们面对活三的时候，需要非常谨慎对待。在自己没有更好的进攻手段的情况下，需要对其进行防守，以防止其形成可怕的活四棋型。
　　
其中图7中间跳着一格的活三，也可以叫做跳活三。

⑤眠三：只能够形成冲四的三，如下各图，分别代表最基础的六种眠三形状。图中白点代表冲四点。眠三的棋型与活三的棋型相比，危险系数下降不少，因为眠三棋型即使不去防守，下一手它也只能形成冲四，而对于单纯的冲四棋型，我们知道，是可以防守住的。
　　　　

　　　　　　　　
如上所示，眠三的形状是很丰富的。对于初学者，在下棋过程中，很容易忽略不常见的眠三形状，例如图2-13所示的眠三。
有新手学了活三眠三后，会提出疑问，说活三也可以形成冲四啊，那岂不是也可以叫眠三？
会提出这个问题，说明对眠三定义看得不够仔细：眠三的的定义是，只能够形成冲四的三。而活三可以形成眠三，但也能够形成活四。
此外，在五子棋中，活四棋型比冲四棋型具有更大的优势，所以，我们在既能够形成活四又能够形成冲四时，会选择形成活四。

⑥活二：能够形成活三的二，如下图，是三种基本的活二棋型。图中白点为活三点。
活二棋型看起来似乎很无害，因为他下一手棋才能形成活三，等形成活三，我们再防守也不迟。但其实活二棋型是非常重要的，尤其是在开局阶段，我们形成较多的活二棋型的话，当我们将活二变成活三时，才能够令自己的活三绵绵不绝微风里，让对手防不胜防。
　　　　　　

⑦眠二：能够形成眠三的二。图中四个为最基本的眠二棋型，细心且喜欢思考的同学会根据眠三介绍中的图2-13找到与下列四个基本眠二棋型都不一样的眠二。图中白点为眠三点。
　　

　　

⑧活一：走一步可以形成活2。

2.2　评估方法

对整个棋盘进行遍历，对于每一个白棋或黑棋，以它为中心，记录符合的棋型个数。

具体实现方式如下：
1、遍历棋盘上的每个点，如果是黑棋或白旗，则对这个点所在四个方向形成的四条线分别进行评估。四个方向即水平，竖直，两个斜线( \ , / ），四个方向依次按照从左到右， 从上到下，从左上到右下，从左下到右上来检测。

2、对于具体的一条线，如下图，已选取点为中心，取该方向上前面两个点，后面两个点，组成一个长度为4的“数组”（实际上是转换成二进制）。

然后找出和中心点相连的同色棋子有几个，比如下图，相连的白色棋子有3个，根据相连棋子的个数再分别进行判断，最后得出这行属于上面说的哪一种棋型。

这里有个注意点，在评估白旗1的时候，白棋3和5已经被判断过，所以要标记下，下次遍历到这个方向的白棋3和5，需要跳过，避免重复统计棋型。

3、根据棋盘上黑棋和白棋的棋型统计信息，按照一定规则进行评分。
假设形成该棋局的最后一步是黑棋下的，则最后的评分是（黑棋得分 - 白棋得分），在相同棋型相同个数的情况下，白棋会占优，因为下一步是白棋下。比如黑棋有个冲四，白棋有个冲四，显然白棋占优，因为下一步白棋就能成连五。

这里的权重设计是有技巧的，因为很多大佬已经经过实验得出许多不同的权重参数，所以这里我就直接使用大佬们给出的数据了。（下标中的死棋其实有的可以看成是活棋或者冲棋，但是为了方便就直接看作死棋的一种）

棋型代号	棋型说明	权重
VALUE_WIN	长连	10000000
VALUE_Huo4	活四	150000
VALUE_Chong4	冲四	7500
VALUE_Si4	死四	20
VALUE_Huo3	活三	7500
VALUE_Chong3	冲三	2000
VALUE_Si3	死三	10
VALUE_Huo2	活二	1000
VALUE_Chong2	冲二	200
VALUE_Si2	死二	5
VALUE_Huo1	活一	100
VALUE_Chong1	冲一	50
VALUE_Si1	死一	0

另外这里我在下面给出一位大佬给出的权重设计规则（但跟我给出的权重设计不相同），有兴趣的可以自行了解。具体的可参考：(250条消息) 五子棋ai：极大极小搜索和α-β剪枝算法的思想和实现(qt和c++)（二）贪心算法和评估函数_livingsu的博客-CSDN博客

• 规则一：己方棋型权重为正，对方棋型权重为负，且相同棋型时，对方权重的绝对值要大于己方(可以设置为2倍或者3倍关系)。这是因为要考虑到进攻和防守，现在是己方(ai白子)下，例如：如果己方走了一步棋形成了活2，而对方已经有一个活2，那么显然是对方占优一些，因为下一步是对方走，对方是可以形成更高等级的活3的，所以己方活2就没有对方活2等级高。
• 规则2：等级：连5>活4>冲4=活3>眠3=活2>眠2=活1，相邻等级的权重设置为相差20倍（也可以30，40倍）。这是因为会重复计算等级比较低的棋型，为了不影响总体判断，比如一开始放一个子，活1的权重会计算16次，我设置为20倍，那么活2的权重刚好比16倍活1还要大一些。
• 规则3：对方连5、对方活4、对方冲4、对方活3的绝对值要设置大一点，这一点非常重要！！如果此时对方已经连五，说明己方已经输了。如果此时对方有活4和冲4，那么如果己方没有连5的话，己方必须要去阻止对方的活4和冲4。像这样可以分析出其他棋型权重。

根据上述的步骤就可以设计评估函数了。

2.2.1　对棋形分数进行记录

AI.h

//棋形分数
#define INF 0x3f3f3f3f    //定义无穷大

#define VALUE_WIN	10000000	//长连/成五 获胜

#define VALUE_Huo4	150000		//活四
#define VALUE_Chong4	7500	//冲四
#define VALUE_Si4    20			//死四

#define VALUE_Huo3  7500		//活三
#define VALUE_Chong3  2000		//冲三
#define VALUE_Si3  10			//死三

#define VALUE_Huo2  1000 		//活二
#define VALUE_Chong2  200 		//冲二
#define VALUE_Si2  5			//死二

#define VALUE_Huo1  100 		//活一
#define VALUE_Chong1  50 		//冲一
#define VALUE_Si1  0			//死一

2.2.2　对下棋的四个方向进行估分

现在有8种有效的棋型（连五，活四，冲四，活三，眠三，活二，眠二，活一），大部份资料都是黑棋白棋用两个五元数组或者六元数组来存储，因为我只用结构体来区分，将黑棋和白棋分开算（side就是区分黑棋和白棋的结构体），并且在对下棋位置的四个位置估分时只关注当前AI的棋色，而不关注棋手下的棋和无棋的位置，所以，操作起来更加方便。

相关变量命名如下：

AI.cpp

int score;
int cmid, cleft, cright, cnt, leftmid, midright;
int left1, left2, right1, right2;
int flag;

注意：上述变量是AI.cpp中的**全局变量**

主体函数：

AI.cpp

//对下棋位置的四个方向（|  -  \  /）估分（准确来说应该是一个棋子的八个方向）
int AI::Get_Four_Side_Score(const Chess_Position& position, Object side)//side指明当前位置是黑棋还是白棋
{
	score = 0;
	int row, col, i;
 
	for (i = 0; i < 4; ++i) 
	{
		cmid = cleft = cright = 0;
		left1 = left2 = right1 = right2 = 0;

		//四个方向	|  -  \  /
		for (row = position.row + dir[i][0], col = position.col + dir[i][1]; chess[row][col] == side; ++cmid) 
		{
			row += dir[i][0];
			col += dir[i][1];
		}
		left1 = chess[row][col] != EMPTY;  //找到与side相同的棋子，则赋值为1
		//若在该方向上有同side一样的棋色，则继续搜索
		if (left1) 
		{
			for (row += dir[i][0], col += dir[i][1]; chess[row][col] == side; ++cleft) 
			{
				row += dir[i][0];
				col += dir[i][1];
			}
			left2 = chess[row][col] != EMPTY; //不等于0证明有棋子，则赋值给left2=1记录该位置已有棋子
		}

		for (row = position.row - dir[i][0], col = position.col - dir[i][1]; chess[row][col] == side; ++cmid) 
		{
			row -= dir[i][0];
			col -= dir[i][1];
		}
		right1 = chess[row][col] != EMPTY;
		if (right1) 
		{
			for (row -= dir[i][0], col -= dir[i][1]; chess[row][col] == side; ++cright) 
			{
				row -= dir[i][0];
				col -= dir[i][1];
			}
			right2 = chess[row][col] != EMPTY;
		}
		score += Return_A_Side_Score();  //计算某个方向的分数分数
	}
	return score;
}

上面的代码块中有一个变成小技巧可以注意一下：

++i 和 i++的结果是一样的， 都要等代码块执行完毕才能执行语句3 ，但是性能是不同的。在大量数据的时候++i的性能要比i++的性能好原因：. i++由于是在使用当前值之后再+1，所以需要一个临时的变量来转存。而++i则是在直接+1，省去了对内存的操作的环节，相对而言能够提高性能.

2.2.3　计算返回某个方向的估分

我们将当前棋子的四个方向遍历以后就需要对某一个方向上的棋型进行统计分数了。

我们先用一个数组来存储四个方向：

AI.cpp

const int dir[4][2] = { {-1,0},{0,-1},{-1,-1},{-1,1} };		//四个方向	|  -  \  /

然后再用三个数组分别存储活棋、冲棋和死棋的分数：

AI.cpp

const int live[6] = { 0,VALUE_Huo1,VALUE_Huo2,VALUE_Huo3,VALUE_Huo4,VALUE_WIN };	//活棋分数
const int go[6] = { 0,VALUE_Chong1,VALUE_Chong2,VALUE_Chong3,VALUE_Chong4,VALUE_Chong4 };		//冲棋分数
const int death[6] = { 0, VALUE_Si1,VALUE_Si2,VALUE_Si3,VALUE_Si4,VALUE_Si4 };	//死棋分数

然后进行估分：

AI.cpp

//计算返回某个方向的估分
int AI::Return_A_Side_Score()
{
	cmid = min(cmid + 1, 5);
	if (cmid == 5)
		return VALUE_WIN;  //一个方向上已经有五个子则直接输出
	cnt = min(cmid + cleft + cright, 5);
	leftmid = min(cleft + cmid, 5);
	midright = min(cmid + cright, 5);
	//将四个位置的1分开，就类似将棋型数据储存进一个四元数组
	//所以将记录的值进行二进制转换并进行一定程度的位置偏移("<<"是左移运算符)
	flag = left2 << 3 | left1 << 2 | right1 << 1 | right2;  

	//用二进制的0和1来代表黑棋白棋
	switch (flag) {
	case 0b0000:
		return live[cnt];
	case 0b0001:
	case 0b1000:
		return max(live[leftmid], go[cnt]);
	case 0b0010:
	case 0b0011:
		return go[leftmid];
	case 0b0100:
	case 0b1100:
		return go[midright];
	case 0b0101:
	case 0b1101:
		return midright >= 4 ? go[midright] : death[midright];
	case 0b1010:
	case 0b1011:
		return leftmid >= 4 ? go[leftmid] : death[leftmid];
	case 0b0110:
	case 0b0111:
	case 0b1110:
	case 0b1111:
		return death[cmid];
	case 0b1001:
		return cnt >= 4 ? max(live[cmid], go[cnt]) : death[cnt];
	}
	return 0;
}

“<<”是左移运算符，“|”是二级制的异或运算符，具体可参考：C++ 运算符 | 菜鸟教程 (runoob.com)

2.2.4　对当前整个棋盘进行评估

//对当前状态整个棋盘估分
int AI::Evaluate_WholeChess(Object side)
{
	int returnValue = 0;
	int v1 = 0, v2 = 0;
	for (int i = TOP; i <= DOWN; ++i)
		for (int j = LEFT; j <= RIGHT; ++j)
			if (chess[i][j] == side)
				v1 += Get_Four_Side_Score(Chess_Position(i, j), side);
			else if (chess[i][j] != EMPTY) {
				v2 += Get_Four_Side_Score(Chess_Position(i, j), (Object)chess[i][j]);
			}
	return (int)(v1 - v2);
}

2.2.5　细节补充

在AI.h中补充函数定义

AI.h

#pragma once

#include<vector>
#include"Chess.h"

using namespace std;

class AI
{
public:
	//AI初始化
	void Init(Chess* chess);

	//AI下棋接口
	void AISearch(Object aiSide, Chess_Position& Position, Chess_Position& nextPosition);
    
    //对下棋位置的四个方向估分
	int Get_Four_Side_Score(const Chess_Position& Position, Object side);

	//计算返回某个方向的估分
	int Return_A_Side_Score();

	//对当前状态整个棋盘估分
	int Evaluate_WholeChess(Object side);
    
    //判断某一方是否取胜
	bool Is_Win(const Chess_Position Position, Object side);
};

至此，我们第二部分的评估函数已经实现完了，接下来才是真正涉及到了AI部分的算法。下一篇就是五子棋AI当中两个主要算法：Min-Max算法和αβ剪枝算法的实现。

下一篇：五子棋AI（三）