什么是启发式搜索

前面讲到了，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
  }