五子棋AI算法六 迭代加深

前面讲到了算杀,其实在算杀之前应该讲一下迭代加深。因为这些文章是我边做边写的一些笔记,所以顺序上可能不是那么严谨。

AI没有找到最优解

按照前面的所有算法实现之后(当然不包括算杀),会发现一个比较严重的问题,就是电脑在自己已经胜券在握的情况下(有双三之类的棋可以走),竟然会走一些冲四之类的棋来调戏玩家。这种走法出现的本质就是因为现在的AI只比较最终结果,并没有考虑到路径长短。所以很容易出现在6层搜索到一个双三,其实在4层的时候也有一个双三,因为分数一样,AI会随机选择一个走法。就导致了明明可以两步赢的棋,AI非要走3步,对玩家来说,感觉就是在调戏人。

所以这里我们定义一个最优解的概念:分数最高的走法中路径最短的那一个走法。那么现在问题就是我们如何找到最优解。

迭代加深

我们通过AB搜索能够找到所有的最高分走法,一个直观的想法就是我们把所有走法都找到,然后比较他们的长度,选择长度最短的走法。

这确实是一个方法,但是我们可以有效率更高的做法,就是通过迭代加深 来优先找到最短路径。

所谓迭代加深,就是从2层开始,逐步增加搜索深度,直到找到胜利走法或者达到深度限制为止。比如我们搜索6层深度,那么我们先尝试2层,如果没有找到能赢的走法,再尝试4层,最后尝试6层。我们只尝试偶数层。因为奇数层其实是电脑比玩家多走了一步,忽视了玩家的防守,并不会额外找到更好的解法。

所以实现这个算法是非常简单的:

1
2
3
4
5
6
7
8
9
10
11
var deeping = function(board, deep) {
deep = deep === undefined ? config.searchDeep : deep;
//迭代加深
//注意这里不要比较分数的大小,因为深度越低算出来的分数越不靠谱,所以不能比较大小,而是是最高层的搜索分数为准
var result;
for(var i=2;i<=deep; i+=2) {
result = maxmin(board, i);
if(math.greatOrEqualThan(result.score, SCORE.FOUR)) return result;
}
return result;
}

这里为了减少一层搜索,我们只搜索到活四就认为是达到最高分了。

迭代加深的优势

迭代加深可以在找到最优解的同时,只增加非常小的额外时间开销,很多时候甚至可以减少开销。假设我们平均一步 50种选择,那么可以证明,4层搜索只需要6层搜索 1/2500 分之一的时间,所以我们额外进行的浅层搜索即使全部没有找到结果,也额外增加了可以忽略不计的时间。另外很可能浅层搜索就能找到最优解,此时可以极大提升效率。

相比之下,如果是搜索到全部最高分解再比较路径长短,时间复杂度会成倍增加。

集成算杀

有了迭代加深之后,我们就可以集成算杀了,很明显第一步应该现将算杀算法也改造成迭代加深,以保证每次算杀找到的都是最优解:

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
67
var c = function(board, role, deep) {
deep = deep || config.checkmateDeep;
if(deep <= 0) return false;
var start = new Date();
debugNodeCount = 0;
//迭代加深
for(var i=1;i<=deep;i++) {
var result = max(board, role, i);
if(result) break; //找到一个就行
}
var time = Math.round(new Date() - start);
if(result) console.log("算杀成功("+time+"毫秒, "+ debugNodeCount + "个节点):" + JSON.stringify(result));
else {
//console.log("算杀失败("+time+"毫秒)");
}
return result;
}

然后,我们就可以在搜索的叶节点进行算杀。因为叶节点有很多,所以叶节点加入算杀之后会导致搜索时间变长:


var negamax = function(board, deep, alpha, beta, role) {
var v = evaluate(board);
count ++;
if(deep <= 0 || win(board)) {
return v;
}

var best = MIN;
var points = gen(board, deep);

for(var i=0;i<points.length;i++) {
var p = points[i];
board[p[0]][p[1]] = role;

//pvs

/*var pv = - negamax(board, deep-1, -alpha-1, -alpha, R.reverse(role));
if(math.littleThan(pv, alpha) {
PVcut ++;
board[p[0]][p[1]] = R.empty;
//console.log(pv, alpha);
return pv;
}*/

alpha = Math.max(best, alpha);
var v = - negamax(board, deep-1, -beta, -alpha, R.reverse(role));
board[p[0]][p[1]] = R.empty;
if(math.greatThan(v, best)) {
best = v;
}
if(math.greatOrEqualThan(v, beta)) { //AB 剪枝
ABcut ++;
return v;
}

//算杀
if( (deep <= 2 ) && role == R.com && math.littleThan(best, SCORE.FOUR) && math.greatThan(best, SCORE.FOUR * -1)) {
var mate = checkmate(board, R.com);
if(mate) {
return SCORE.FIVE * Math.pow(.8, mate.length);
}
}
}

return best;
}

上述代码中我们只对AI自己进行了算杀,没有对玩家进行算杀,主要是因为现在的算杀效率比较低,如果对玩家也进行算杀会导致时间增加一倍。

另外上述的极大极小值搜索被改成了负极大值搜索,不过原理上并没有区别,只是代码变得更加简洁统一了。

以现在的算杀和搜索效率,可以做到 4+7,即4层负极大值搜索加上7层算杀,棋力会比之前有明显的提升。

内部迭代加深

上面讲的迭代加深只对负极大值搜索进行了一层封装,其实可以更深入一点,对每一次 negamax 搜索都进行迭代加深,具体效果还没有验证,有兴趣可以尝试下,后续我应该也会尝试这个方法。