什么是启发式搜索

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

2

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

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

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

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

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

board.js

  1. gen (role, onlyThrees, starSpread) {
  2.     if (this.count <= 0) return [7, 7]
  3.     var fives = []
  4.     var comfours=[]
  5.     var humfours=[]
  6.     var comblockedfours = []
  7.     var humblockedfours = []
  8.     var comtwothrees=[]
  9.     var humtwothrees=[]
  10.     var comthrees = []
  11.     var humthrees = []
  12.     var comtwos = []
  13.     var humtwos = []
  14.     var neighbors = []
  16.     var board = this.board
  17.     var reverseRole = R.reverse(role)
  19.     for(var i=0;i<board.length;i++) {
  20.       for(var j=0;j<board.length;j++) {
  21.         var p = [i, j]
  22.         if(board[i][j] == R.empty) {
  23.           var neighbor = [2,2]
  24.           if(this.allSteps.length < 6) neighbor = [1, 1]
  25.           if(this.hasNeighbor([i, j], neighbor[0], neighbor[1])) { //必须是有邻居的才行
  27.             var scoreHum = p.scoreHum = this.humScore[i][j]
  28.             var scoreCom = p.scoreCom = this.comScore[i][j]
  29.             var maxScore = Math.max(scoreCom, scoreHum)
  30.             p.score = maxScore
  31.             p.role = role
  33.             if(scoreCom >= S.FIVE) {//先看电脑能不能连成5
  34.               fives.push(p)
  35.             } else if(scoreHum >= S.FIVE) {//再看玩家能不能连成5
  36.               //别急着返回，因为遍历还没完成，说不定电脑自己能成五。
  37.               fives.push(p)
  38.             } else if(scoreCom >= S.FOUR) {
  39.               comfours.push(p)
  40.             } else if(scoreHum >= S.FOUR) {
  41.               humfours.push(p)
  42.             } else if(scoreCom >= S.BLOCKED_FOUR) {
  43.               comblockedfours.push(p)
  44.             } else if(scoreHum >= S.BLOCKED_FOUR) {
  45.               humblockedfours.push(p)
  46.             } else if(scoreCom >= 2*S.THREE) {
  47.               //能成双三也行
  48.               comtwothrees.push(p)
  49.             } else if(scoreHum >= 2*S.THREE) {
  50.               humtwothrees.push(p)
  51.             } else if(scoreCom >= S.THREE) {
  52.               comthrees.push(p)
  53.             } else if(scoreHum >= S.THREE) {
  54.               humthrees.push(p)
  55.             } else if(scoreCom >= S.TWO) {
  56.               comtwos.unshift(p)
  57.             } else if(scoreHum >= S.TWO) {
  58.               humtwos.unshift(p)
  59.             } else {
  60.               neighbors.push(p)
  61.             }
  62.           }
  63.         }
  64.       }
  65.     }
  67.     //如果成五，是必杀棋，直接返回
  68.     if(fives.length) return fives
  70.     // 自己能活四，则直接活四，不考虑冲四
  71.     if (role === R.com && comfours.length) return comfours
  72.     if (role === R.hum && humfours.length) return humfours
  74.     // 对面有活四冲四，自己冲四都没，则只考虑对面活四 （此时对面冲四就不用考虑了)
  76.     if (role === R.com && humfours.length && !comblockedfours.length) return humfours
  77.     if (role === R.hum && comfours.length && !humblockedfours.length) return comfours
  79.     // 对面有活四自己有冲四，则都考虑下
  80.     var fours = role === R.com ? comfours.concat(humfours) : humfours.concat(comfours)
  81.     var blockedfours = role === R.com ? comblockedfours.concat(humblockedfours) : humblockedfours.concat(comblockedfours)
  82.     if (fours.length) return fours.concat(blockedfours)
  84.     var result = []
  85.     if (role === R.com) {
  86.       result = 
  87.         comtwothrees
  88.         .concat(humtwothrees)
  89.         .concat(comblockedfours)
  90.         .concat(humblockedfours)
  91.         .concat(comthrees)
  92.         .concat(humthrees)
  93.     }
  94.     if (role === R.hum) {
  95.       result = 
  96.         humtwothrees
  97.         .concat(comtwothrees)
  98.         .concat(humblockedfours)
  99.         .concat(comblockedfours)
  100.         .concat(humthrees)
  101.         .concat(comthrees)
  102.     }
  104.     // result.sort(function(a, b) { return b.score - a.score })
  106.     //双三很特殊，因为能形成双三的不一定比一个活三强
  107.     if(comtwothrees.length || humtwothrees.length) {
  108.       return result
  109.     }
  112.     // 只返回大于等于活三的棋
  113.     if (onlyThrees) {
  114.       return result
  115.     }
  118.     var twos
  119.     if (role === R.com) twos = comtwos.concat(humtwos)
  120.     else twos = humtwos.concat(comtwos)
  122.     twos.sort(function(a, b) { return b.score - a.score })
  123.     result = result.concat(twos.length ? twos : neighbors)
  125.     //这种分数低的，就不用全部计算了
  126.     if(result.length>config.countLimit) {
  127.       return result.slice(0, config.countLimit)
  128.     }
  130.     return result
  131.   }

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