五子棋AI算法第四篇-啟發式搜尋函數

什麼是啟發式搜尋

之前我們講到需要優化一個重要的函數，就是

gen

函數 顧名思義就是生成待搜尋的位置的函數。這個函數目前做了一個很簡單的處理，就是隻要一個空位的周圍有鄰居即可。而其實這麼做是非常不合理的，它的不合理性展現在兩友善：

1. 沒有對結果進行排序，完全是按照數組的周遊順序的。而Alpha Beta 剪枝的效率是非常依賴節點順序的，這個我們馬上就會講一下。
2. 沒有排除不需要節點。如果能減少一些不必要的節點，那麼其實就是優化了 M^N 中的M，優化效果是非常明顯的。

我們接下來分别針對上面兩點講一下如何優化啟發式搜尋函數

對待搜尋節點進行排序

還是前一章的那張圖，上面可以看到在第二層中，第一個節點的值是3，因為他其實是本層中的極小值，導緻後面的兩個節點都可以進行剪枝（這裡第二個節點的第二個孩子也可以剪掉的）。這是最好的一種情況，即在MIN層中極小值是第一個節點，那麼後序的所有節點都可以根據這個極小值進行剪枝，即使極小值不在第一個節點，隻要大緻能按照從小到大的順序排列，也會剪掉很多節點。如果很不幸，這一層的節點是從大到小排列的，那麼剪枝就完全沒有用。

對于Beta 剪枝也是同樣的道理。是以說Alpha Beta剪枝的效率是取決于每一層節點的順序的。 我們肯定是無法精确排序的，因為每一個節點的值并不能直接計算出來，需要遞歸計算子節點。 但是我們依然能對節點進行大緻的一個排序。前面說過了，隻要有一個大緻的排序 其實就能很好的提升剪枝效率。

那麼如何排序呢？就是給所有待搜尋的位置進行打分，按照分數的高低來排序。注意這個打分算法是對某一個空位進行打分，和對整個棋盤進行打分的

evaluate

函數是不一樣的。不過打分的基本原理是相同的。具體就是根據這個位置是否能成五，活四，活三等來進行打分。具體的代碼有些長就不貼出來了，請參見

evaluate-point.js

。

有了打分之後，我們就可以按照分數高低進行排序了。具體實作的時候，是根據按照 成五，活四，雙三，活三，其他 的順序來排序的。

删除不必須要的節點

這個難度也比較高，目前能做的就是，還是按照 成五，活四，雙三的順序，因為這三種是必殺棋，隻要出現了，就不用再考慮其他節點了，如果都沒有，才需要考慮其他節點。

代碼實作

綜合上面兩種情況，啟發式搜尋函數的代碼如下：

var R = require("./role.js");
var scorePoint = require("./evaluate-point.js");
var S = require("./score.js");

var gen = function(board, deep) {

  var fives = [];
  var fours=[];
  var twothrees=[];
  var threes = [];
  var twos = [];
  var neighbors = [];
  var nextNeighbors = [];

  for(var i=0;i<board.length;i++) {
    for(var j=0;j<board[i].length;j++) {
      if(board[i][j] == R.empty) {
        if(hasNeighbor(board, [i, j], 1, 1)) { //必須是有鄰居的才行
          var scoreHum = scorePoint(board, [i,j], R.hum);
          var scoreCom= scorePoint(board, [i,j], R.com);

          if(scoreCom >= S.FIVE) {//先看電腦能不能連成5
            return [[i, j]];
          } else if(scoreHum >= S.FIVE) {//再看玩家能不能連成5
            //别急着傳回，因為周遊還沒完成，說不定電腦自己能成五。
            fives.push([i, j]);
          } else if(scoreCom >= S.FOUR) {
            fours.unshift([i,j]);
          } else if(scoreHum >= S.FOUR) {
            fours.push([i,j]);
          } else if(scoreCom >= 2*S.THREE) {
            //能成雙三也行
            twothrees.unshift([i,j]);
          } else if(scoreHum >= 2*S.THREE) {
            twothrees.push([i,j]);
          } else if(scoreCom >= S.THREE) {
            threes.unshift([i, j]);
          } else if(scoreHum >= S.THREE) {
            threes.push([i, j]);
          } else if(scoreCom >= S.TWO) {
            twos.unshift([i, j]);
          } else if(scoreHum >= S.TWO) {
            twos.push([i, j]);
          } else {
            neighbors.push([i, j]);
          }
        } else if(deep >= 2 && hasNeighbor(board, [i, j], 2, 2)) {
          nextNeighbors.push([i, j]);
        }
      }
    }
  }

  //如果成五，是必殺棋，直接傳回
  if(fives.length) return [fives[0]];

  if(fours.length) return fours;

  if(twothrees.length) return twothrees;

  return threes.concat(
      twos.concat(
        neighbors.concat(nextNeighbors)
      )
    );
}
           

優化效果

前一章講過 Alpha Beta 剪枝之後每一步平均大約計算 50W 個節點，需要10秒鐘。經過啟發式函數的優化之後，每一步平均1W節點左右， 不到一秒鐘的時間， 可以看到啟發式搜尋函數的優化效果是非常巨大的，效率提升了 50 倍。

進一步優化

目前master上的代碼就包括了我前面講到的全部優化方法。進一步的優化會包括置換表，以及更進一步的優化剪枝算法和啟發式搜尋函數。具體的做法還在考慮中。