五子棋AI算法四 启发式评估函数

什么是启发式搜索

之前我们讲到需要优化一个重要的函数,就是 gen 函数 顾名思义就是生成待搜索的位置的函数。这个函数目前做了一个很简单的处理,就是只要一个空位的周围有邻居即可。而其实这么做是非常不合理的,它的不合理性体现在两方便:

  1. 没有对结果进行排序,完全是按照数组的遍历顺序的。而Alpha Beta 剪枝的效率是非常依赖节点顺序的,这个我们马上就会讲一下。
    2.没有排除不需要节点。如果能减少一些不必要的节点,那么其实就是优化了 M^N 中的M,优化效果是非常明显的。

我们接下来分别针对上面两点讲一下如何优化启发式搜索函数

对待搜索节点进行排序

alpha-beta

还是前一章的那张图,上面可以看到在第二层中,第一个节点的值是3,因为他其实是本层中的极小值,导致后面的两个节点都可以进行剪枝(这里第二个节点的第二个孩子也可以剪掉的)。这是最好的一种情况,即在MIN层中极小值是第一个节点,那么后序的所有节点都可以根据这个极小值进行剪枝,即使极小值不在第一个节点,只要大致能按照从小到大的顺序排列,也会剪掉很多节点。如果很不幸,这一层的节点是从大到小排列的,那么剪枝就完全没有用。

对于Beta 剪枝也是同样的道理。所以说Alpha Beta剪枝的效率是取决于每一层节点的顺序的。 我们肯定是无法精确排序的,因为每一个节点的值并不能直接计算出来,需要递归计算子节点。 但是我们依然能对节点进行大致的一个排序。前面说过了,只要有一个大致的排序 其实就能很好的提升剪枝效率。

那么如何排序呢?就是给所有待搜索的位置进行打分,按照分数的高低来排序。注意这个打分算法是对某一个空位进行打分,和对整个棋盘进行打分的 evaluate 函数是不一样的。不过打分的基本原理是相同的。具体就是根据这个位置是否能成五,活四,活三等来进行打分。具体的代码有些长就不贴出来了,请参见 evaluate-point.js

有了打分之后,我们就可以按照分数高低进行排序了。具体实现的时候,是根据按照 成五,活四,双三,活三,其他 的顺序来排序的。

删除不必须要的节点

这个难度也比较高,目前能做的就是,还是按照 成五,活四,双三的顺序,因为这三种是必杀棋,只要出现了,就不用再考虑其他节点了,如果都没有,才需要考虑其他节点。

代码实现

综合上面两种情况,启发式搜索函数的代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
var R = require("./role.js");
var scorePoint = require("./evaluate-point.js");
var S = require("./score.js");

var gen = function(board, deep) {

var fives = [];
var fours=[];
var twothrees=[];
var threes = [];
var twos = [];
var neighbors = [];
var nextNeighbors = [];

for(var i=0;i<board.length;i++) {
for(var j=0;j<board[i].length;j++) {
if(board[i][j] == R.empty) {
if(hasNeighbor(board, [i, j], 1, 1)) { //必须是有邻居的才行
var scoreHum = scorePoint(board, [i,j], R.hum);
var scoreCom= scorePoint(board, [i,j], R.com);

if(scoreCom >= S.FIVE) {//先看电脑能不能连成5
return [[i, j]];
} else if(scoreHum >= S.FIVE) {//再看玩家能不能连成5
//别急着返回,因为遍历还没完成,说不定电脑自己能成五。
fives.push([i, j]);
} else if(scoreCom >= S.FOUR) {
fours.unshift([i,j]);
} else if(scoreHum >= S.FOUR) {
fours.push([i,j]);
} else if(scoreCom >= 2*S.THREE) {
//能成双三也行
twothrees.unshift([i,j]);
} else if(scoreHum >= 2*S.THREE) {
twothrees.push([i,j]);
} else if(scoreCom >= S.THREE) {
threes.unshift([i, j]);
} else if(scoreHum >= S.THREE) {
threes.push([i, j]);
} else if(scoreCom >= S.TWO) {
twos.unshift([i, j]);
} else if(scoreHum >= S.TWO) {
twos.push([i, j]);
} else {
neighbors.push([i, j]);
}
} else if(deep >= 2 && hasNeighbor(board, [i, j], 2, 2)) {
nextNeighbors.push([i, j]);
}
}
}
}

//如果成五,是必杀棋,直接返回
if(fives.length) return [fives[0]];

if(fours.length) return fours;

if(twothrees.length) return twothrees;

return threes.concat(
twos.concat(
neighbors.concat(nextNeighbors)
)
);
}

优化效果

前一章讲过 Alpha Beta 剪枝之后每一步平均大约计算 50W 个节点,需要10秒钟。经过启发式函数的优化之后,每一步平均1W节点左右, 不到一秒钟的时间, 可以看到启发式搜索函数的优化效果是非常巨大的,效率提升了 50 倍。

进一步优化

目前master上的代码就包括了我前面讲到的全部优化方法。进一步的优化会包括置换表,以及更进一步的优化剪枝算法和启发式搜索函数。具体的做法还在考虑中。