跳至主要內容

五子棋AI算法（3）

奇葩的灵梦2020/5/6大约 8 分钟五子棋算法Java
最近更新：

注意

此AI并非“人工智能”，而是我们早期意义上的传统AI，并无学习能力，纯粹用算法实现五子棋每一步棋的应对策略。

上一章成功的实现了一个五子棋AI，尽管它的性能非常不佳。接下来，我们打算在此基础上进行一系列优化，大幅度提高运算性能。

α-β剪枝

回顾一下我们上一章说的“极大值极小值搜索”：

按照上一章的方法，首先我们从第一个分支6和5中找到最小值5。接下来，我们找第二个分支，结果我们一上来就看到了2。这个时候我们思考一下，如果后面的数比2大，那么2是最小值；如果后面的数比2小，那么说明最小值比2小。这样一来，我在第二个分支中得到的最小值肯定不会超过2。在第一个分支我们已经得到最小值5了，由于MAX层要找最大值，第二个分支是不会超过2的，所以整个第二个分支下面的所有分支我们都可以放弃了。这就是所谓的“剪枝”。同理，第三个分支找到了0，第四个分支找到了3，都比5小，这两个分支也都不用看了。

这样一来，如果在“运气好”的情况下，每一排只需要看第一个分支即可，后面的分支都可以忽略。这个忽略后面的分支的方法就叫做“剪枝”。

那么代码是怎么写的呢？首先我们拿到上一章的代码过来看一下：

RobotPlayer.java

观察一下，for循环就相当于博弈树的一个节点下的不同分支，而中间的递归调用相当于进入下一个子节点。我们需要修改的是，在递归调用的时候，将已经遍历过的子节点中得到过的极大值（或极小值）传给未遍历过的节点，若未遍历过的节点中已经发现满足剪枝的条件时进行剪枝即可。

我们把上面的代码稍加修改

RobotPlayer.java

好了，经历了α-β剪枝之后，在“运气好”的情况下，可以省去很多的进一步遍历。

启发式搜索

上面多次着重强调了“运气好”这三个字，那么也就是说，我们的运气并不是一直都这么好。如果算法仅仅适用于运气好，那么就不通用了。

首先，我们想一下。什么样的点，容易出现上述的“极大值”（或者“极小值”）？显然，那些对胜负至关重要的点，相比那些不重要的点，更容易出现极值。那么，我们在遍历下一层之前，先交换一下遍历的顺序，让重要的点先进行遍历，就更加容易出现之前所说的“运气好”的情况——更容易很快出现极值。那么我们首先需要一个函数，来给每个点一个评估，它到底对胜负是否非常重要，这个函数就被称为“启发式搜索”函数。（这段代码看似很长，其实并无含金量，原本打算不贴出来的，但想了想还是补上了，方便读者节约时间，不在这个问题上浪费太多时间）

RobotPlayer.java

参数p表示接下来要计算的点，me表示调用这个函数的那一方自己的颜色，plyer代表接下来要计算的人的编号。一个点对两方的重要性之和，就是我们需要的结果。这样我们就可以大致得到了一个对单个点的价值评估函数，也就是“启发式搜索”函数。

值得一提的是，这里的这些数字，其实都是凭个人感觉写的（例如四肯定比三重要，例如活四就直接赢了那我肯定优先走活四），并且多次测试后慢慢调整的，所以不精确。将来如果有机会，我打算用其他的方法来给这些数字一些更加科学的值。

然后我们在遍历之前，排个序即可。这里偷点懒，直接用了优先队列PriorityQueue。

RobotPlayer.java
private PointAndValue max(int leftStep, int color, int passValue) {
	PriorityQueue<PointAndValue> queue = new PriorityQueue<>((obj1, obj2)->Integer.compare(obj2.value, obj1.value));
	for (int i = 0; i < Constant.MAX_LEN; i++) {
		for (int j = 0; j < Constant.MAX_LEN; j++) {
			Point p = new Point(j, i);
			if (board.get(p) == 0 && board.isNeighbor(p)) {
				int evathis = evaluatePoint(p, colorNext);
				queue.add(new PointAndValue(p, evathis));
			}
		}
	}
	//下面的代码循环就从优先队列的头开始循环，而不再需要从左上角到右下角一一遍历了
	//循环代码和上文基本一样，就不再赘述了
}

从减少遍历次数的方法对博弈树的极大极小值搜索进行优化，就基本到这里为止了。后续还会介绍一些其他的方法进行优化的技巧。