五子棋AI教程第二版五：启发式评估函数

[lihongxun945]

什么是启发式搜索

前面讲到了，AB搜索的效果很大程度上取决于子节点的排序。

还是前一章的那张图，上面可以看到在第二层中，第一个节点的值是3，第二个是6。因为3比较小，而这一层的最大值会被选中，所以第二个节点也需要完整计算所有孩子。如果3和6调换一下顺序，6在前，3在后。那么当第二个节点计算出第一个孩子5的时候就没有必要计算之后的孩子了。也就是，Alpha-Beta 剪枝的效率和节点排序有很大关系，如果最优的节点能排在前面，则能大幅提升剪枝效率。

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

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

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

启发式搜索函数的代码如下：

board.js

gen (role, onlyThrees, starSpread) {
    if (this.count <= 0) return [7, 7]
    var fives = []
    var comfours=[]
    var humfours=[]
    var comblockedfours = []
    var humblockedfours = []
    var comtwothrees=[]
    var humtwothrees=[]
    var comthrees = []
    var humthrees = []
    var comtwos = []
    var humtwos = []
    var neighbors = []

    var board = this.board
    var reverseRole = R.reverse(role)

    for(var i=0;i<board.length;i++) {
      for(var j=0;j<board.length;j++) {
        var p = [i, j]
        if(board[i][j] == R.empty) {
          var neighbor = [2,2]
          if(this.allSteps.length < 6) neighbor = [1, 1]
          if(this.hasNeighbor([i, j], neighbor[0], neighbor[1])) { //必须是有邻居的才行

            var scoreHum = p.scoreHum = this.humScore[i][j]
            var scoreCom = p.scoreCom = this.comScore[i][j]
            var maxScore = Math.max(scoreCom, scoreHum)
            p.score = maxScore
            p.role = role

            if(scoreCom >= S.FIVE) {//先看电脑能不能连成5
              fives.push(p)
            } else if(scoreHum >= S.FIVE) {//再看玩家能不能连成5
              //别急着返回，因为遍历还没完成，说不定电脑自己能成五。
              fives.push(p)
            } else if(scoreCom >= S.FOUR) {
              comfours.push(p)
            } else if(scoreHum >= S.FOUR) {
              humfours.push(p)
            } else if(scoreCom >= S.BLOCKED_FOUR) {
              comblockedfours.push(p)
            } else if(scoreHum >= S.BLOCKED_FOUR) {
              humblockedfours.push(p)
            } else if(scoreCom >= 2*S.THREE) {
              //能成双三也行
              comtwothrees.push(p)
            } else if(scoreHum >= 2*S.THREE) {
              humtwothrees.push(p)
            } else if(scoreCom >= S.THREE) {
              comthrees.push(p)
            } else if(scoreHum >= S.THREE) {
              humthrees.push(p)
            } else if(scoreCom >= S.TWO) {
              comtwos.unshift(p)
            } else if(scoreHum >= S.TWO) {
              humtwos.unshift(p)
            } else {
              neighbors.push(p)
            }
          }
        }
      }
    }

    //如果成五，是必杀棋，直接返回
    if(fives.length) return fives
    
    // 自己能活四，则直接活四，不考虑冲四
    if (role === R.com && comfours.length) return comfours
    if (role === R.hum && humfours.length) return humfours

    // 对面有活四冲四，自己冲四都没，则只考虑对面活四 （此时对面冲四就不用考虑了)
    
    if (role === R.com && humfours.length && !comblockedfours.length) return humfours
    if (role === R.hum && comfours.length && !humblockedfours.length) return comfours

    // 对面有活四自己有冲四，则都考虑下
    var fours = role === R.com ? comfours.concat(humfours) : humfours.concat(comfours)
    var blockedfours = role === R.com ? comblockedfours.concat(humblockedfours) : humblockedfours.concat(comblockedfours)
    if (fours.length) return fours.concat(blockedfours)

    var result = []
    if (role === R.com) {
      result = 
        comtwothrees
        .concat(humtwothrees)
        .concat(comblockedfours)
        .concat(humblockedfours)
        .concat(comthrees)
        .concat(humthrees)
    }
    if (role === R.hum) {
      result = 
        humtwothrees
        .concat(comtwothrees)
        .concat(humblockedfours)
        .concat(comblockedfours)
        .concat(humthrees)
        .concat(comthrees)
    }

    // result.sort(function(a, b) { return b.score - a.score })

    //双三很特殊，因为能形成双三的不一定比一个活三强
    if(comtwothrees.length || humtwothrees.length) {
      return result
    }


    // 只返回大于等于活三的棋
    if (onlyThrees) {
      return result
    }


    var twos
    if (role === R.com) twos = comtwos.concat(humtwos)
    else twos = humtwos.concat(comtwos)

    twos.sort(function(a, b) { return b.score - a.score })
    result = result.concat(twos.length ? twos : neighbors)

    //这种分数低的，就不用全部计算了
    if(result.length>config.countLimit) {
      return result.slice(0, config.countLimit)
    }

    return result
  }

下一篇：五子棋AI设计教程第二版六：迭代加深

[RechardWong]

还是前一章的那张图，上面可以看到在第二层中，第一个节点的值是3，因为他其实是本层中的极小值，导致后面的两个节点都可以进行剪枝（这里第二个节点的第二个孩子也可以剪掉的）。
这里第二个节点的第二个孩子不可以减掉吧，如果它的值小于6的话那第二个节点选的就不是6了而是这个值了。

[weiziyoung]

第

还是前一章的那张图，上面可以看到在第二层中，第一个节点的值是3，因为他其实是本层中的极小值，导致后面的两个节点都可以进行剪枝（这里第二个节点的第二个孩子也可以剪掉的）。
这里第二个节点的第二个孩子不可以减掉吧，如果它的值小于6的话那第二个节点选的就不是6了而是这个值了。

我也觉得，这个博主的逻辑上有明显的问题，第三层剪”8“结点完全是因为，他搜索到了5，而5比6小才不选择其他的结点。

[lihongxun945]

@weiziyoung @RechardWong 感谢指正，已经修改。写完代码太久确实容易搞错。

[weiziyoung]

@weiziyoung @RechardWong 感谢指正，已经修改。写完代码太久确实容易搞错。

嗯，之前总感觉理解不了alpha beta剪枝，总感觉跟你想的不一样，后来想了一天以后，确定是你错了。

[kevinyyh]

请教一下，我用了alpha beta pruning后发现只有在搜索层数为4的时候下的速度比较正常，但是一旦增加两层速度就会非常慢，请问在排序上有什么技巧吗？

[mo3000]

黑棋不能下33，44，长连，剪枝逻辑要改下。

[lihongxun945]

@kevinyyh 加一层可能会导致10倍左右的时间消耗，你从4增加到6时间增长50~100倍都是很正常的。
不过如果搜索6层就很慢，应该是你的代码有问题。好像直接用AB剪枝之后就能到6层了

[barnett617]

黑棋不能下33，44，长连，剪枝逻辑要改下。

黑棋禁手规则

[Ericufo]

starSpread参数未被使用，是不是可以删除