Tic-Tac-Toe 中的 Minimax 没有返回正确的值

Question

我正在尝试编写一个井字游戏，并决定使用 MiniMax 算法，但我在实现它时遇到了问题。例如：在

  board = [
          "E", "E", "X",
          "E", "E", "X",
          "E", "O", "O"
          ];

轮到 AI 了，函数 returns AiMove { score: -10, coordinates: 0 } 是最佳着法。我已经尝试调试了很长一段时间，但是函数的递归性质和可能的游戏树数量，尤其是早期游戏状态，很难跟踪和调试。

有人可以帮忙吗？

https://jsfiddle.net/LdLqk1z8/4/

var factions = {
  AIplayer: "X",
  humanPlayer: "O"
};

var gameResults = {
  winner: ""
};

var emptyCells = function(board) { //check for empty cells and return an array with the number of empty cells
  var indices = [];
  for (var itr = 0; itr < 9; itr++) {
    if (board[itr] === "E") {
      indices.push(itr);
    }
  }
  return indices;
};

var isGameOver = function(board) {
  var tile = board;

  //check for victory conditions
  for (var i = 0; i <= 6; i = i + 3) {
    if (tile[i] !== "E" && tile[i] === tile[i + 1] && tile[i + 1] === tile[i + 2]) {
      if (factions.AIplayer === tile[i]) {
        gameResults.winner = "AIplayer";
      } else if (tile[i] === factions.humanPlayer) {
        gameResults.winner = "humanPlayer";
      }
      return true;
    }
  }

  for (var i = 0; i <= 2; i++) {
    if (tile[i] !== "E" && tile[i] === tile[i + 3] && tile[i + 3] === tile[i + 6]) {
      if (factions.AIplayer === tile[i]) {
        gameResults.winner = "AIplayer";
      } else if (tile[i] === factions.humanPlayer) {
        gameResults.winner = "humanPlayer";
      }
      return true;
    }
  }

  for (var i = 0, j = 4; i <= 2; i = i + 2, j = j - 2) {
    if (tile[i] !== "E" && tile[i] === tile[i + j] && tile[i + j] === tile[i + 2 * j]) {
      if (factions.AIplayer === tile[i]) {
        gameResults.winner = "AIplayer";
      } else if (tile[i] === factions.humanPlayer) {
        gameResults.winner = "humanPlayer";
      }
      return true;
    }
  }

  var check = emptyCells(board); //check if the game ended with a draw
  if (check.length === 0) {
    gameResults.winner = "draw";
    return true;
  } else {
    return false; //if no condition is matched the game has not concluded
  }
};

var getBestMove = function(board, player) {

  // return an AiMove object initialized to 10 if the AI player wins, -10 if the human player wins and 0 if the game is a draw
  if (isGameOver(board)) {
    if (gameResults.winner === "AIplayer") {
      return new AiMove(10);
    } else if (gameResults.winner === "humanPlayer") {
      return new AiMove(-10);
    } else if (gameResults.winner === "draw") {
      return new AiMove(0);
    }
  }

  var moves = []; //array to store all moves
  var currentPlayer = player;
  for (var i = 0, l = board.length; i < l; i++) { //iterate over the board
    if (board[i] == "E") { //if the tile is empty
      var move = new AiMove; //create new AiMove object and assign a coordinate
      move.coordinates = i;
      board[i] = currentPlayer; //update board
      //call getBestMove recursively with the next player
      if (currentPlayer === factions.AIplayer) {
        move.score = getBestMove(board, factions.humanPlayer).score;
      } else if (currentPlayer === factions.humanPlayer) {
        move.score = getBestMove(board, factions.AIplayer).score;
      }
      moves.push(move);

      board[i] = "E"; //clear tile after move is pushed in to the moves array
    }
  }

  //if it's the AI player's turn select biggest value from the moves array, if it's the human player's turn select the smallest value
  if (currentPlayer === factions.AIplayer) {
    var bestMove = 0;
    var bestScore = -10000;
    for (var i = 0; i < moves.length; i++) {
      if (moves[i].score > bestScore) {
        bestScore = moves[i].score;
        bestMove = i;
      }
    }
  } else if (currentPlayer === factions.humanPlayer) {
    var bestMove = 0;
    var bestScore = 10000;
    for (var i = 0; i < moves.length; i++) {
      if (moves[i].score < bestScore) {
        bestMove = i;
        bestScore = moves[i].score;
      }
    }
  }
  return moves[bestMove]; //return best move
};

var board = [
              "E", "E", "X",
              "E", "E", "X",
              "E", "O", "O"
              ];

function AiMove(score) {
  this.coordinates,
    this.score = score;
}

console.log(getBestMove(board, factions.AIplayer))

编辑：难道是因为棋盘设置是无法取胜的，AI 是宿命论的，所以 "gives-up"？实施 "depth" 的概念会解决这个问题吗？

Answer 1

在等式中引入深度的想法确实是正确的。

在执行 moves.push(move) 之前添加以下行：

  move.score = Math.sign(move.score) * (Math.abs(move.score) - 1);

这将使得分降低 1 分（-10 变为 -9，10 变为 9，等等）。表达了离输越远越不严重，离赢越近越好的意思。

在您提供的示例棋盘设置中，这将 return 6 作为最佳着法，从而避免了人类玩家的立即获胜。当然，AI还是会输给best play，游戏会继续这样下去：

. . X     . . X     . . X     X . X     X O X
. . X  →  . . X  →  . O X  →  . O X  →  . O X
. O O     X O O     X O O     X O O     X O O

为了更好的调试可能性，我会编写一个将电路板打印到控制台的函数。例如：

function printBoard(board) {
    console.log(board.slice(0, 3).join (' ').replace(/E/g, '.'));
    console.log(board.slice(3, 6).join (' ').replace(/E/g, '.'));
    console.log(board.slice(6, 9).join (' ').replace(/E/g, '.'));
    console.log('');
}

您还可以考虑使代码更加面向对象，在 Game 对象上编写方法等。

Tic-Tac-Toe 中的 Minimax 没有返回正确的值

Minimax in Tic-Tac-Toe not returning correct value

javascript

algorithm

recursion

tic-tac-toe

minimax