AI实现的基本思路-极大极小值搜索算法

五子棋AI教程第二版发布啦，地址：https://github.com/lihongxun945/myblog/labels/%E4%BA%94%E5%AD%90%E6%A3%8BAI%E6%95%99%E7%A8%8B%E7%AC%AC%E4%BA%8C%E7%89%88git

当前这个是旧版教程，强烈建议阅读新版教程。github

五子棋看起来有各类各样的走法，而实际上把每一步的走法展开，就是一颗巨大的博弈树。在这个树中，从根节点为0开始，奇数层表示电脑可能的走法，偶数层表示玩家可能的走法。web

假设电脑先手，那么第一层就是电脑的全部可能的走法，第二层就是玩家的全部可能走法，以此类推。算法

咱们假设平均每一步有50种可能的走法，那么从根节点开始，往下面每一层的节点数量是上一层的 50被，假设咱们进行4层思考，也就是电脑和玩家各走两步，那么这颗博弈树的最后一层的节点数为 50^4 = 625W 个。数组

先不考虑这么多个节点须要多久能算出来。有了对博弈树的基本认识，咱们就能够用递归来遍历这一棵树。dom

那么咱们如何才能知道哪个分支的走法是最优的，咱们就须要一个评估函数能对当前整个局势做出评估，返回一个分数。咱们规定对电脑越有利，分数越大，对玩家越有利，分数越小，分数的起点是0。svg

咱们遍历这颗博弈树的时候就很明显知道该如何选择分支了：函数

• 电脑走棋的层咱们称为 MAX层，这一层电脑要保证本身利益最大化，那么就须要选分最高的节点。
• 玩家走棋的层咱们称为MIN层，这一层玩家要保证本身的利益最大化，那么就会选分最低的节点。

这也就是极大极小值搜索算法的名称由来。直接盗一个图说明这个问题：性能

此图中甲是电脑，乙是玩家，那么在甲层的时候，老是选其中值最大的节点，乙层的时候，老是选其中最小的节点。优化

而每个节点的分数，都是由子节点决定的，所以咱们对博弈树只能进行深度优先搜索而没法进行广度优先搜索。深度优先搜索用递归很是容易实现，而后主要工做实际上是完成一个评估函数，这个函数须要对当前局势给出一个比较准确的评分。

这篇博客讲的五子棋算法已经所有用JS实现而且是开源的，源码地址： https://github.com/lihongxun945/gobang ,预览地址： http://gobang.light7.cn/

能够clone这个仓库，参考其中js目录下的源码。由于代码量不小，后面要讲的只是关键部分的代码实现，不会贴完整的代码。并且关键代码可能会省略部分实现，UI由于跟AI算法无关，也不会讲，请自行参考源码。

咱们下面来分部实现其中几个关键的部分。

极大极小值搜索

五子棋是一个15*15的棋盘，由于棋盘大小不会变更，因此目前来看用 15*15 的二维数组来存储，效果是最好的。

极大极小值的搜索比较简单，就是一个DFS，直接上代码，看不懂的能够

var maxmin = function(board, deep) {
  var best = MIN;
  var points = gen(board, deep);     //这个函数的做用是生成待选的列表，就是能够下子的空位。后面会讲这个方法。

  for(var i=0;i<points.length;i++) {
    var p = points[i];
    board[p[0]][p[1]] = R.com;     //尝试下一个子
    var v = min(board, deep-1);     //找最大值
    //若是跟以前的一个好，则把当前位子加入待选位子
    if(v == best) {
      bestPoints.push(p);
    }
    //找到一个更好的分，就把之前存的位子所有清除
    if(v > best) {
      best = v;
      bestPoints = [];
      bestPoints.push(p);
    }
    board[p[0]][p[1]] = R.empty;     //记得把尝试下的子移除
  }
  var result = bestPoints[Math.floor(bestPoints.length * Math.random())]; //在分数最高的几个位置中随机选择一个
  return result;
}

var min = function(board, deep) {
  var v = evaluate(board);     //重点来了，评价函数，这个函数返回的是对当前局势的估分。
  if(deep <= 0 || win(board)) {
    return v;
  }

  var best = MAX;
  var points = gen(board, deep);

  for(var i=0;i<points.length;i++) {
    var p = points[i];
    board[p[0]][p[1]] = R.hum;
    var v = max(board, deep-1);
    board[p[0]][p[1]] = R.empty;
    if(v < best ) {
      best = v;
    }
  }
  return best ;
}

var max = function(board, deep) {
  var v = evaluate(board);
  if(deep <= 0 || win(board)) {
    return v;
  }

  var best = MIN;
  var points = gen(board, deep);

  for(var i=0;i<points.length;i++) {
    var p = points[i];
    board[p[0]][p[1]] = R.com;
    var v = min(board, deep-1);
    board[p[0]][p[1]] = R.empty;
    if(v > best) {
      best = v;
    }
  }
  return best;
}

源码里面是有 Alpha Beta剪枝的，不过剪枝代码其实就几行，能够直接看源码，在 js/max-min.js 里面。

评估函数

在源码中 js/evaluate.js 就是评估函数，它接受一个二维数组，返回一个整型数。

咱们对五子棋的评分是简单的把棋盘上的各类连子的分值加起来获得的，对各类连子的基本评分规则以下：

• 成五，100000
• 活四, 10000
• 活三 1000
• 活二 100
• 活一 10

若是一侧被封死可是另外一侧没有，则评分降一个档次，也就是死四和活三是相同的分

• 死四, 1000
• 死三 100
• 死二 10

score.js 中是对各类状况估值的定义。

按照这个规则把棋盘上电脑的全部棋子打分，之和即为电脑的单方面得分 scoreComputer，而后对玩家的棋子一样打分 获得 scoreHuman。

scoreComputer - scoreHuman 即为当前局势的总分数。

那么如何找出全部的连子呢，目前个人方式是先把二维的棋盘按照横竖撇捺四个方向变成N个一维数组，这个过程称为 flat。flat.js 是一个专门实现这个功能的模块。
而后咱们就能够对全部的一维数组进行得分计算。
评分函数代码领比较大，请自行参考 evalute.js

请注意，这里咱们说的评估函数是对整个棋局的评估，后面讲启发式搜索的时候还会有一个启发式评估函数是对某一个位置的评估。这两个评估函数是不一样的

generator函数

generator顾名思义，就是在每一步生成全部能够落子的点。并非全部的空位咱们又要搜索，不少位置明显不合适的咱们能够直接排除。
这个函数很是重要，是优化性能的关键。不过目前咱们只作一个最简单的实现。就是把全部周围有邻居的空位认为是合适的位子。

有邻居的定义是：想个两步之内至少有一个不为空的点便可。好比 b[7,7] 有一个子，那么 b[6,7]是他的邻居，b[5,7] 也是，可是 b[4,7] 就不是，由于相隔了三步。

var gen = function(board, deep) {

  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)) { //必须是有邻居的才行
            neighbors.push([i, j]);
        } else if(deep >= 2 && hasNeighbor(board, [i, j], 2, 2)) {
          nextNeighbors.push([i, j]);
        }
      }
    }
  }
  return  neighbors.concat(nextNeighbors)
}

这里作了一个简单的优化，就是按照邻居的远近作了一个排序，为何要排序。后面讲AB剪枝的时候会讲到。排序对AB剪枝的效率起了决定性做用。

另一些简单的函数，没有列出，直接去看源码就好了

下面咱们将讲一个重点： Alpha Beta 剪枝算法。