五子棋AI教程第二版六：迭代加深

[lihongxun945]

AI没有找到最优解

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

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

迭代加深

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

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

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

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

negamax.js

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

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

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

var deeping = function(candidates, role, deep) {
  start = (+ new Date())
  Cache = {} // 每次开始迭代的时候清空缓存。这里缓存的主要目的是在每一次的时候加快搜索，而不是长期存储。事实证明这样的清空方式对搜索速度的影响非常小（小于10%)

  var bestScore
  for(var i=2; i<=deep; i+=2) {
    bestScore = negamax(candidates, role, i, MIN, MAX)
  //// 每次迭代剔除必败点，直到没有必败点或者只剩最后一个点
  //// 实际上，由于必败点几乎都会被AB剪枝剪掉，因此这段代码几乎不会生效
  //var newCandidates = candidates.filter(function (d) {
  //  return !d.abcut
  //})
  //candidates = newCandidates.length ? newCandidates : [candidates[0]] // 必败了，随便走走

    if (math.greatOrEqualThan(bestScore, SCORE.FIVE)) break // 能赢了
    // 下面这样做，会导致上一层的分数，在这一层导致自己被剪枝的bug，因为我们的判断条件是 >=， 上次层搜到的分数，在更深一层搜索的时候，会因为满足 >= 的条件而把自己剪枝掉
    // if (math.littleThan(bestScore, T.THREE * 2)) bestScore = MIN // 如果能找到双三以上的棋，则保留bestScore做剪枝，否则直接设置为最小值
  }

  // 美化一下
  candidates = candidates.map(function (d) {
    var r = [d[0], d[1]]
    r.score = d.v.score
    r.step = d.v.step
    r.steps = d.v.steps
    if (d.v.vct) r.vct = d.v.vct
    if (d.v.vcf) r.vcf = d.v.vcf
    return r
  })

  // 排序
  // 经过测试，这个如果放在上面的for循环中（就是每次迭代都排序），反而由于迭代深度太浅，排序不好反而会降低搜索速度。
  candidates.sort(function (a,b) {
    if (math.equal(a.score,b.score)) {
      // 大于零是优势，尽快获胜，因此取步数短的
      // 小于0是劣势，尽量拖延，因此取步数长的
      if (a.score >= 0) {
        if (a.step !== b.step) return a.step - b.step
        else return b.score - a.score // 否则 选取当前分最高的（直接评分)
      }
      else {
        if (a.step !== b.step) return b.step - a.step
        else return b.score - a.score // 否则 选取当前分最高的（直接评分)
      }
    }
    else return (b.score - a.score)
  })

  var result = candidates[0]

  return result
}

迭代加深的优势

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

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

内部迭代加深

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

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

[ChangleSong]

需要修復一些bug，有時開局就會死棋，把棋盤下滿了也不會和棋。當然，最重要的是感謝經驗分享。：）

[luyuner]

请问math.js 中的threshold是什么作用？

[PYUDNG]

请问math.js 中的threshold是什么作用？

以math.equal为例来解释：
math.equal函数的作用是判断传入的两个值是否大致相等。根据代码

var threshold = 1.15

var equal = function(a, b) {
  b = b || 0.01
  return b >= 0 ? ((a >= b / threshold) && (a <= b * threshold))
          : ((a >= b * threshold) && (a <= b / threshold))
}

可以知道，对于两个数 (a, b) ，当a的值处于b * threshold 和b / threshold之间时，math.equal函数就判断两个数大致相等，threshold在这里起到划定“大致相等”中“大致”的范围的作用。

Math中其他涉及threshold的函数也都是如此。

[luyuner]

您好，请您检查一下是否输入了正确的抄送邮箱。本人不记得有从事五子棋AI相关的项目。

…

---原始邮件--- 发件人: ***@***.***&gt; 发送时间: 2022年2月1日(周二) 晚上9:53 收件人: ***@***.***&gt;; 抄送: ***@***.******@***.***&gt;; 主题: Re: [lihongxun945/myblog] 五子棋AI教程第二版六：迭代加深 (#16) 请问math.js 中的threshold是什么作用？ 以math.equal为例来解释： math.equal函数的作用是判断传入的两个值是否大致相等。根据代码 var threshold = 1.15 var equal = function(a, b) { b = b || 0.01 return b &gt;= 0 ? ((a &gt;= b / threshold) &amp;&amp; (a <= b * threshold)) : ((a &gt;= b * threshold) &amp;&amp; (a <= b / threshold)) } 可以知道，对于两个数 (a, b) ，当a的值处于b * threshold 和b / threshold之间时，math.equal函数就判断两个数大致相等，threshold在这里起到划定“大致相等”中“大致”的范围的作用。 Math中其他涉及threshold的函数也都是如此。 — Reply to this email directly, view it on GitHub, or unsubscribe. Triage notifications on the go with GitHub Mobile for iOS or Android. You are receiving this because you commented.Message ID: ***@***.***&gt;

[PYUDNG]

您好，请您检查一下是否输入了正确的抄送邮箱。本人不记得有从事五子棋AI相关的项目。
…
---原始邮件--- 发件人: @.> 发送时间: 2022年2月1日(周二) 晚上9:53 收件人: @.>; 抄送: @.@.>; 主题: Re: [lihongxun945/myblog] 五子棋AI教程第二版六：迭代加深 (#16) 请问math.js 中的threshold是什么作用？ 以math.equal为例来解释： math.equal函数的作用是判断传入的两个值是否大致相等。根据代码 var threshold = 1.15 var equal = function(a, b) { b = b || 0.01 return b >= 0 ? ((a >= b / threshold) && (a <= b * threshold)) : ((a >= b * threshold) && (a <= b / threshold)) } 可以知道，对于两个数 (a, b) ，当a的值处于b * threshold 和b / threshold之间时，math.equal函数就判断两个数大致相等，threshold在这里起到划定“大致相等”中“大致”的范围的作用。 Math中其他涉及threshold的函数也都是如此。 — Reply to this email directly, view it on GitHub, or unsubscribe. Triage notifications on the go with GitHub Mobile for iOS or Android. You are receiving this because you commented.Message ID: @.***>

抱歉，如果打扰到您了的话。
我是直接在github上回复的，回复的内容时间已经太过久远，写出来也是为了让后来者能够看到，如果打扰，真心抱歉。