首页 > 代码库 > 五子棋AI算法-迭代加深
五子棋AI算法-迭代加深
前面讲到了算杀，其实在算杀之前应该讲一下迭代加深。因为这些文章是我边做边写的一些笔记，所以顺序上可能不是那么严谨。
按照前面的所有算法实现之后（当然不包括算杀），会发现一个比较严重的问题，就是电脑在自己已经胜券在握的情况下（有双三之类的棋可以走），竟然会走一些冲四之类的棋来调戏玩家。这种走法出现的本质就是因为现在的AI只比较最终结果，并没有考虑到路径长短。所以很容易出现在6层搜索到一个双三，其实在4层的时候也有一个双三，因为分数一样，AI会随机选择一个走法。就导致了明明可以两步赢的棋，AI非要走3步，对玩家来说，感觉就是在调戏人。
所以这里我们定义一个最优解的概念：分数最高的走法中路径最短的那一个走法。那么现在问题就是我们如何找到最优解。
迭代加深
我们通过AB搜索能够找到所有的最高分走法，一个直观的想法就是我们把所有走法都找到，然后比较他们的长度，选择长度最短的走法。
这确实是一个方法，但是我们可以有效率更高的做法，就是通过迭代加深 来优先找到最短路径。
所谓迭代加深，就是从2层开始，逐步增加搜索深度，直到找到胜利走法或者达到深度限制为止。比如我们搜索6层深度，那么我们先尝试2层，如果没有找到能赢的走法，再尝试4层，最后尝试6层。我们只尝试偶数层。因为奇数层其实是电脑比玩家多走了一步，忽视了玩家的防守，并不会额外找到更好的解法。
所以实现这个算法是非常简单的：
1 var deeping = function(board, deep) { 2 deep = deep === undefined ? config.searchDeep : deep; 3 //迭代加深 4 //注意这里不要比较分数的大小，因为深度越低算出来的分数越不靠谱，所以不能比较大小，而是是最高层的搜索分数为准 5 var result; 6 for(var i=2;i<=deep; i+=2) { 7 result = maxmin(board, i); 8 if(math.greatOrEqualThan(result.score, SCORE.FOUR)) return result; 9 }10 return result;11 }
这里为了减少一层搜索，我们只搜索到活四就认为是达到最高分了。
迭代加深的优势
迭代加深可以在找到最优解的同时，只增加非常小的额外时间开销，很多时候甚至可以减少开销。假设我们平均一步 50种选择，那么可以证明，4层搜索只需要6层搜索 1/2500 分之一的时间，所以我们额外进行的浅层搜索即使全部没有找到结果，也额外增加了可以忽略不计的时间。另外很可能浅层搜索就能找到最优解，此时可以极大提升效率。
相比之下，如果是搜索到全部最高分解再比较路径长短，时间复杂度会成倍增加。
集成算杀
有了迭代加深之后，我们就可以集成算杀了，很明显第一步应该现将算杀算法也改造成迭代加深，以保证每次算杀找到的都是最优解:
1 var c = function(board, role, deep) { 2 deep = deep || config.checkmateDeep; 3 if(deep <= 0) return false; 4 var start = new Date(); 5 debugNodeCount = 0; 6 //迭代加深 7 for(var i=1;i<=deep;i++) { 8 var result = max(board, role, i); 9 if(result) break; //找到一个就行10 }11 var time = Math.round(new Date() - start);12 if(result) console.log("算杀成功("+time+"毫秒, "+ debugNodeCount + "个节点):" + JSON.stringify(result));13 else {14 //console.log("算杀失败("+time+"毫秒)");15 }16 return result;17 }18 然后，我们就可以在搜索的叶节点进行算杀。因为叶节点有很多，所以叶节点加入算杀之后会导致搜索时间变长:19 20 var negamax = function(board, deep, alpha, beta, role) {21 var v = evaluate(board);22 count ++;23 if(deep <= 0 || win(board)) {24 return v;25 }26 27 var best = MIN;28 var points = gen(board, deep);29 30 for(var i=0;i<points.length;i++) {31 var p = points[i];32 board[p[0]][p[1]] = role;33 34 //pvs35 36 /*var pv = - negamax(board, deep-1, -alpha-1, -alpha, R.reverse(role));37 if(math.littleThan(pv, alpha) {38 PVcut ++;39 board[p[0]][p[1]] = R.empty;40 //console.log(pv, alpha);41 return pv;42 }*/43 44 alpha = Math.max(best, alpha);45 var v = - negamax(board, deep-1, -beta, -alpha, R.reverse(role));46 board[p[0]][p[1]] = R.empty;47 if(math.greatThan(v, best)) {48 best = v;49 }50 if(math.greatOrEqualThan(v, beta)) { //AB 剪枝51 ABcut ++;52 return v;53 }54 55 //算杀56 if( (deep <= 2 ) && role == R.com && math.littleThan(best, SCORE.FOUR) && math.greatThan(best, SCORE.FOUR * -1)) {57 var mate = checkmate(board, R.com);58 if(mate) {59 return SCORE.FIVE * Math.pow(.8, mate.length);60 }61 }62 }63 64 return best;65 }
上述代码中我们只对AI自己进行了算杀，没有对玩家进行算杀，主要是因为现在的算杀效率比较低，如果对玩家也进行算杀会导致时间增加一倍。
另外上述的极大极小值搜索被改成了负极大值搜索，不过原理上并没有区别，只是代码变得更加简洁统一了。
以现在的算杀和搜索效率，可以做到 4+7，即4层负极大值搜索加上7层算杀，棋力会比之前有明显的提升。
内部迭代加深
上面讲的迭代加深只对负极大值搜索进行了一层封装，其实可以更深入一点，对每一次 negamax 搜索都进行迭代加深，具体效果还没有验证，有兴趣可以尝试下，后续我应该也会尝试这个方法。
五子棋AI算法-迭代加深