AI没有找到最优解

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

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

迭代加深

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

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

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

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

negamax.js

  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 = negamax(board, i);
  8.     if(math.greatOrEqualThan(result.score, SCORE.FOUR)) return result;
  9.   }
  10.   return result;
  11. }

这其实是我最早期的代码，其中有一个致命Bug：如果电脑发现自己局势不好，会自杀。什么意思呢，就是电脑发现无论怎么走都是很大的一个负分，那么他会选取最短的一个路径走，也就是尽快达到这个负分，直观的感觉就是，电脑发现自己要输了，就不防守了。

为什么会这样呢？因为我们能赢的时候要选最短的，但是要输的时候，一定要选最长的而不是最短的走法，因为我们要尽量“挣扎”一下。所以完整的实现是这样的：

  1. var deeping = function(candidates, role, deep) {
  2.   start = (+ new Date())
  3.   Cache = {} // 每次开始迭代的时候清空缓存。这里缓存的主要目的是在每一次的时候加快搜索，而不是长期存储。事实证明这样的清空方式对搜索速度的影响非常小（小于10%)
  5.   var bestScore
  6.   for(var i=2; i<=deep; i+=2) {
  7.     bestScore = negamax(candidates, role, i, MIN, MAX)
  8.   //// 每次迭代剔除必败点，直到没有必败点或者只剩最后一个点
  9.   //// 实际上，由于必败点几乎都会被AB剪枝剪掉，因此这段代码几乎不会生效
  10.   //var newCandidates = candidates.filter(function (d) {
  11.   //  return !d.abcut
  12.   //})
  13.   //candidates = newCandidates.length ? newCandidates : [candidates[0]] // 必败了，随便走走
  15.     if (math.greatOrEqualThan(bestScore, SCORE.FIVE)) break // 能赢了
  16.     // 下面这样做，会导致上一层的分数，在这一层导致自己被剪枝的bug，因为我们的判断条件是 >=， 上次层搜到的分数，在更深一层搜索的时候，会因为满足 >= 的条件而把自己剪枝掉
  17.     // if (math.littleThan(bestScore, T.THREE * 2)) bestScore = MIN // 如果能找到双三以上的棋，则保留bestScore做剪枝，否则直接设置为最小值
  18.   }
  20.   // 美化一下
  21.   candidates = candidates.map(function (d) {
  22.     var r = [d[0], d[1]]
  23.     r.score = d.v.score
  24.     r.step = d.v.step
  25.     r.steps = d.v.steps
  26.     if (d.v.vct) r.vct = d.v.vct
  27.     if (d.v.vcf) r.vcf = d.v.vcf
  28.     return r
  29.   })
  31.   // 排序
  32.   // 经过测试，这个如果放在上面的for循环中（就是每次迭代都排序），反而由于迭代深度太浅，排序不好反而会降低搜索速度。
  33.   candidates.sort(function (a,b) {
  34.     if (math.equal(a.score,b.score)) {
  35.       // 大于零是优势，尽快获胜，因此取步数短的
  36.       // 小于0是劣势，尽量拖延，因此取步数长的
  37.       if (a.score >= 0) {
  38.         if (a.step !== b.step) return a.step - b.step
  39.         else return b.score - a.score // 否则 选取当前分最高的（直接评分)
  40.       }
  41.       else {
  42.         if (a.step !== b.step) return b.step - a.step
  43.         else return b.score - a.score // 否则 选取当前分最高的（直接评分)
  44.       }
  45.     }
  46.     else return (b.score - a.score)
  47.   })
  49.   var result = candidates[0]
  51.   return result
  52. }

迭代加深的优势

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

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

内部迭代加深

上面讲的迭代加深只对负极大值搜索进行了一层封装，其实可以更深入一点，对每一次 negamax 搜索都进行迭代加深，我们一般把这种实现叫 “内部迭代加深”，我并没有实现，有兴趣可以自行实现并测试下效果。

下一篇：五子棋AI设计教程第二版七：Zobrist缓存