Jinlong's Blog

如何设计一个还可以的五子棋AI

发表于

2018/5/20更新：已把源代码分享到Github，并推出了1.0版本（当然只是改进了一下界面）。推出了第一版对外接口，大家可以很容易地将此五子棋AI整合到自己的项目中，点击此处转到项目链接。如果大家觉得项目不错，可进行star，多谢支持！

图形界面

由于图形界面不是本次讨论的重点，所以只用python实现了一个简单的图形界面，然后用C++来实现算法部分的内容，编译成动态链接库，在python界面程序中调用动态链接库中的相关函数就可以了。选择python是因为考虑到它的夸平台性，在各大操作系统都可以直接解释执行。对于动态链接库，Linux是so，而Windows是dll，代码写法略有不同，但也差别不大。
比如说在*nix系统中直接编译我们写好的代码成so库就好了，而在Windows中函数则要额外加上declspec(dllexport)或declspec(dllimport)声明，例如：

1
2
3
4
5
6
7
8
9
10
11
#ifdef BUILD_DLL
	#define DLL_EXPORT __declspec(dllexport)
#else
	#define DLL_EXPORT __declspec(dllimport)
#endif
extern "C" {
	DLL_EXPORT int add(int a, int b) {
		return a + b;
	}
}

注意，如果是用C++，需要用extern “C” {}把导出函数括起来，否则C++中的函数名字修饰（Decorated Name）会导致在加载动态链接库中相应函数的时候找不到函数名

另外附上*uix平台和Windows平台编译生成动态链接库的命令：
Linux

1
g++ -shared -fPIC -o libfivechess.so fivechess.cpp

Windows

1
2
g++ -c -DBUILD fivechess.cpp
g++ -shared -o fivechess.dll fivechess.o -Wl,--out-implib,libfivechess.a

当应用需要发布的时候可以用pyinstaller等工具来把python脚本打包成exe等可执行文件。
wuziqi3.jpg
wuziqi4.jpg

最初的思路

下面进入本次讨论的重点，算法部分。
最初的思路是根据人的经验制定一个评分表，根据评分表对棋盘中每一个位置进行评分，选取评分最高的位置作为下一步走的棋。什么是评分表呢？看下图：
score.jpg
这是摘自董红安2005年论文“计算机五子棋博弈系统的研究与实现”中的评分表，图中共有16中不同的特征，在每一种特征中，O代表棋子，+代表空位，每一种特征的右侧有其对应的评分。在一个好的评分表中，威胁大的特征具有绝对优势的评分，再多威胁小的评分加起来也不可能超过威胁大的评分表。
有了评分表，那怎么利用评分表对相应位置进行评分呢？评分规则如下：
对该位置所在的行和列和正斜列以及反斜列上相关范围进行扫描，如图
score1.jpg
可以看出，图中四个矩形的模式分别是(假如要在粉色多边形的位置上放置绿方棋子）：

  • 横：+++OO++++
  • 竖：+++OOO+++
  • \：++++O++++
  • /：++AOO++++
    其中的A表示该位置有敌方棋子，我们对这四组数据进行模式匹配，得出该位置的分数为：
    120 + 720 + 20 + 0 = 860
    应用此算法对棋盘中的所有位置进行评分，然后选取分数最高的位置进行下棋

加入博弈树-利用极大极小搜索提升棋力

上诉的方法虽然简单容易实现，却可以取得不错的效果，有时候一不小还真的被他打输了。但是，上诉方法的确有非常大的缺陷，电脑只能预测一步，相当于一个仅仅拘束于眼前利益的傻子，稍微熟悉五子棋的人套路一下电脑，就可以轻易打赢电脑了。
解决方法是我们可以设计程序让电脑可以思考几步，极大极小搜索树可以帮忙我们实现这种功能。在此我们需要修改一下评分函数，这次不是对每一个位置进行评分，而是对整个棋局来进行评分（评分的时候对整个棋盘的每一行每一列每一斜列进行模式匹配，然后把所有的分数加起来即可），整个棋局作为一个独立单位。
score2.jpg
如图，我们先计算叶子节点的分数（注：这里指的分数是对于己方来说的，分数越高，对己方越有利）。接着，如果子节点是己（敌）方下的棋，则子节点的父节点的值被赋值为子节点中的最大（小）值。最后，在第一层中，找出得分最高的节点，作为下一步下棋的位置。（注：生成下一步可能下棋的点的时候只需要考虑现有棋子旁边的点，也就是与现有棋子相差一格且没有棋子的点即可）

在使用了极大极小搜索之后，棋力得到了一定的提升。但是因为极大极小搜索需要巨大的运算量（时间复杂度为指数级别），所以只能做很少几层的搜索（3层），这对于计算机来说是患了很深的近视眼（观察距离只能是3层），下面我们通过AlphaBeta优化来优化极大极小搜索。

质的提升-AlphaBeta剪枝

AlphaBeta剪枝是对极大极小搜索的优化，描述算法需要大量的篇幅，这里就不讨论了，直接给出一篇写的还不错的文章http://www.xqbase.com/computer/search_alphabeta.htm，另外附上伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int AlphaBeta(int depth, int alpha, int beta) {
　if(depth == 0) {
　　return Evaluate();
　}
　GenerateLegalMoves();
　while(MovesLeft()) {
　　MakeNextMove();
　　val = -AlphaBeta(depth - 1, -beta, -alpha);
　　UnmakeMove();
　　if(val >= beta) {
　　　return beta;
　　}
　　if(val > alpha) {
　　　alpha = val;
　　}
　}
　return alpha;
}

再一次质的提升-启发式搜索

AlphaBeta剪枝有严重依赖于每一层节点扫描的顺序，因为前面节点生成的alpha直接决定了后面节点剪枝的多少。如果我们针对每一层生成的节点事先排好序，那么程序的速度将极大地提升。然而，对生成的节点进行绝对准确地排序是不可能的，因为需要巨大的运算量（等同于再进行一次alphabeta剪枝的搜索），所以我们只能对节点进行粗略地排好序。
在”最初的思想”中，我们已经讨论了如何对棋盘上的位置进行评分，我们可以利用这个评分，对生成的可能的点进行排序。排序开销小，然而对整体的搜索速度带来巨大的提升。加入此优化之后，五子棋可以轻松做到5层搜索。

看起来不起眼的一个小优化

在进行了AlphaBeta剪枝和启发式搜索之后，搜索依然只能进行到5层左右。6层还非常慢。
在启发式式搜索的优化中，已经对下一步可能出现的位置粗略地排好了序，极大地提高了AlphaBeta剪枝的效率。但是由于每层产生的点太多，导致计算机仍然需要搜索数量巨大的节点。
事实上，只要对位置进行评分的函数足够好，我们就可以保证最优解基本出现在排好序的节点的前十之中。所以我们只需要扫描产生的排好序的点的前十个点就ok了。这个不起眼的优化提升非常巨大，有了这个小优化之后，在一台好一点的电脑五子棋的搜索层数可以达到7层。棋力迅猛提升，在电脑先走的情况下基本打不赢电脑。
附上伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int AlphaBeta(int depth, int alpha, int beta) {
　if(depth == 0) {
　　return Evaluate();
　}
　GenerateLegalMoves();
  int count = 0;
　while(MovesLeft()) {
　　MakeNextMove();
　　val = -AlphaBeta(depth - 1, -beta, -alpha);
　　UnmakeMove();
　　if(val >= beta) {
　　　return beta;
　　}
　　if(val > alpha) {
　　　alpha = val;
　　}
	if(count++ >= 10)
		break;
　}
　return alpha;
}

增加置换表以及悔棋功能

到此，棋子力已经超过7层了。然而在搜索的过程中，还是会出现一些重复搜索的情况，例如：
score3.jpg
这时候，就要用到zobrist和置换表了，相关链接如下：
http://www.xqbase.com/computer/struct_zobrist.htm
http://www.xqbase.com/computer/search_hashing.htm
对于置换表，保存搜索过的棋局的哈希数组越大，速度就越快。但是这次的提升并没有前几次优化的提升那么明显，以为索引的计算以及记录也需要时间，况且总结点还那么大，加入了置换表之后搜索还是只能停留在7层。不过，总体来看，使用置换表对程序的性能来说还是有一定的提升的。使用置换表还有一个很有用的功能，那就是如果用户悔棋，然后再下的话，运算速度可以快不少，因为有的节点已经搜索过计算好保存在置换表中啦。

总结

好了，到此我们就完成了一个简易版但棋力还可以的五子棋AI。
下面是其对弈github中小有名气的五子棋项目gobang的对弈结果，本讨论做的具有7层搜索能力的五子棋AI可以轻松打赢gobang（其实也可以打赢网上大部分的五子棋软件）。
wuziqi1.jpg
wuziqi2.jpg
在人机对弈上，此五子棋已经达到了普通人偏上的棋力水平，发给很多朋友测试后称很难打赢，在“电脑先走”的这种情况下更是几乎没有赢过。但是，由于这只是一个简易版的五子棋AI，不懂得如何算杀，更不懂得如何把控局面进行优势的积累，与弈心、黑石等著名五子棋引擎还是有一定的差距的。源代码经调整后随后呈上。
最后附上下载链接（Windows EXE可执行文件）：
https://kimlongli.github.io/files/fivechess.zip
（注: 在一些老式电脑上可能运行比较慢）

一些优化（2017/1/20更新）

  • 前面提到的对整个局面进行评分。一种解决方案是在alpha-beta的每一次迭代中，都对整个棋盘进行一次扫描，来得出一个局面的评分。这样虽然可行，但是效率低下。因为在alpha-beta剪枝函数的每一次迭代当中，棋盘中的棋子只会增加（减少）一个，棋盘中的大部分区域的评分是不变的，所以不用每次迭代都对整个棋盘来进行一次完整的扫描。可以保存好前一次迭代里棋盘的评分（可以把每一行，每一列每一斜列的评分都保存起来），然后在当前迭代中扫描当前下的棋子所在的行、列、斜列，结合前一次迭代的棋盘评分，得出新的评分。这样就免去了每次都要重新扫描整个棋盘。效率可以有不小的提升。
  • 计算下一步所有可能的点的时候，也可以采用同样的思想。
    下一步可能出现的点（新） = 下一步可能出现的点（旧） - 当前下棋的点 + 当前下棋的点旁边的位置

加入ac算法（2018/5/29更新）

ac算法是一种可以在一个字符串中高效搜索多种模式的字符串匹配算法，可以用来优化我们五子棋程序模式匹配的速度。