AI-2048

针对目前火爆的2048游戏，有人实现了一个AI程序，可以以较大概率（高于90%）赢得游戏，并且作者在
stackoverflow上简要介绍了AI的算法框架和实现思路。

有博客介绍了其中涉及的算法，讲的很好

其中算法的主要是在ai.js文件中。我加了很多的注释在其中，方便大家理解。

function AI(grid) {
  this.grid = grid;
}

// static evaluation function
AI.prototype.eval = function() {
  var emptyCells = this.grid.availableCells().length;
  //各种计算的权重，可以自己手动的调试
  var smoothWeight = 0.1,
      //monoWeight   = 0.0,
      //islandWeight = 0.0,
      mono2Weight  = 1.0,
      emptyWeight  = 2.7,
      maxWeight    = 1.0;

  return this.grid.smoothness() * smoothWeight
       //+ this.grid.monotonicity() * monoWeight
       //- this.grid.islands() * islandWeight
       + this.grid.monotonicity2() * mono2Weight
       + Math.log(emptyCells) * emptyWeight
       + this.grid.maxValue() * maxWeight;
};

// alpha-beta depth first search
AI.prototype.search = function(depth, alpha, beta, positions, cutoffs) {
  var bestScore;
  var bestMove = -1;
  var result;

  // the maxing player
  if (this.grid.playerTurn) {
    bestScore = alpha;
    //遍历四个方向
    for (var direction in [0, 1, 2, 3]) {
      var newGrid = this.grid.clone();
      //逐一搜寻方向
      if (newGrid.move(direction).moved) {
        positions++;
        //如果已经赢了直接返回
        if (newGrid.isWin()) {
          return { move: direction, score: 10000, positions: positions, cutoffs: cutoffs };
        }
        //如果还没有赢得话就继续想下走
        var newAI = new AI(newGrid);
        //当深度为0的时候停止
        if (depth == 0) {
          result = { move: direction, score: newAI.eval() };
        } else {//继承父节点的alpha
          //递归的搜寻  注意每移动一次轮次翻转 player->computer->player->computer->....
          result = newAI.search(depth-1, bestScore, beta, positions, cutoffs);
          if (result.score > 9900) { // win
            result.score--; // to slightly penalize higher depth from win
          } 
          positions = result.positions;
          cutoffs = result.cutoffs;
        }
        //如果返回的分数>当前最好分数则给bestScore和bestMove重新赋值
        if (result.score > bestScore) {
          bestScore = result.score;
          bestMove = direction;
        }
        //如果最好的分数大于beta也即意味着上一层节点不会继续向下走 切分
        if (bestScore > beta) {
          cutoffs++
          //既然不会往这儿走，那么分数还是你上层的beta

          return { move: bestMove, score: beta, positions: positions, cutoffs: cutoffs };
        }
      }
    }
  }

  else { // computer's turn, we'll do heavy pruning to keep the branching factor low
    bestScore = beta;

    // try a 2 and 4 in each cell and measure how annoying it is
    // with metrics from eval
    var candidates = [];
    //得到可以填充块的坐标
    var cells = this.grid.availableCells();
    //分数为2 或者 4
    var scores = { 2: [], 4: [] };
    for (var value in scores) {
      for (var i in cells) {
        scores[value].push(null);
        var cell = cells[i];
        var tile = new Tile(cell, parseInt(value, 10));
        this.grid.insertTile(tile);
        //算出分数，下面的计算可以看出要算出分数最大的，我们知道min节点是使游戏变得更难
        //那么smoothness要越小越好，所以加上符号(越大越好) islands意味着有数字的格子，当然越多越好
        //通俗理解就是不能合并在一起的越多越好
        scores[value][i] = -this.grid.smoothness() + this.grid.islands();
        this.grid.removeTile(cell);
      }
    }

    // now just pick out the most annoying moves
    var maxScore = Math.max(Math.max.apply(null, scores[2]), Math.max.apply(null, scores[4]));
    for (var value in scores) { // 2 and 4
      //将最大分数的候选者选出来（满足最大分数的可能不止一个）
      for (var i=0; i<scores[value].length; i++) {
        if (scores[value][i] == maxScore) {
          candidates.push( { position: cells[i], value: parseInt(value, 10) } );
        }
      }
    }

    // search on each candidate
    for (var i=0; i<candidates.length; i++) {
      var position = candidates[i].position;
      var value = candidates[i].value;
      var newGrid = this.grid.clone();
      var tile = new Tile(position, value);
      newGrid.insertTile(tile);
      newGrid.playerTurn = true;
      positions++;
      newAI = new AI(newGrid);
      //min节点往下的alpha还是上层的，beta是最好的分数，也就是说下层节点如果你取得的最大值只能是beta，
      //如果大于beta我会把你pass掉
      result = newAI.search(depth, alpha, bestScore, positions, cutoffs);
      positions = result.positions;
      cutoffs = result.cutoffs;
      //竟然有比beta还小的分数，好，我选择你
      if (result.score < bestScore) {
        bestScore = result.score;
      }
      //如果最好的分数小于上层的下界 意味着上层节点肯定不会继续向下走
      if (bestScore < alpha) {
        cutoffs++;
        //返回的分数是还是上层的值也就是说你反正不会走我这条路，那你的分数还是你原来的分数
        //关于此处的move:null 注意上面的result的depth是继承父节点的，意味着depth>0
        //也就是说最后一步必为max节点，min节点是不会有move操作的，所以直接返回null
        return { move: null, score: alpha, positions: positions, cutoffs: cutoffs };
      }
    }
  }
//计算到最好返回这些计算的值
  return { move: bestMove, score: bestScore, positions: positions, cutoffs: cutoffs };
}

// performs a search and returns the best move
AI.prototype.getBest = function() {
  return this.iterativeDeep();
}

// performs iterative deepening over the alpha-beta search
AI.prototype.iterativeDeep = function() {
  var start = (new Date()).getTime();
  var depth = 0;
  var best;
  //没有规定固定的depth 而是规定了计算时间，在规定时间内能计算到的深度
  do {
    var newBest = this.search(depth, -10000, 10000, 0 ,0);
    if (newBest.move == -1) {
      break;
    } else {
      best = newBest;
    }
    depth++;
  } while ( (new Date()).getTime() - start < minSearchTime);
  return best
}

AI.prototype.translate = function(move) {
 return {
    0: 'up',
    1: 'right',
    2: 'down',
    3: 'left'
  }[move];
}

以上就是根据我的理解所做的注释，供大家参考如果有错误请大家指正！