极小极大算法的井字游戏

Question

我对极小极大算法感到困惑。我已经花了 2 天，仍然找不到错误。你能看一下我的代码来帮助我找出任何错误吗？

export default class TicTacToeController {
  /*@ngInject*/
  constructor($scope) {
    this.board = new Array(3);

    this.players = {
      ai: "x",
      player: "o"
    };

    this.move = {
      row: "",
      cell: ""
    };

    this.currentPlayer = this.players.ai;
    this.humanMove = false;

    this.fillBoard();
    this.board[0][0] = "x";
    this.board[0][1] = "o";
    this.board[0][2] = "x";
    this.board[1][0] = "x";
    this.board[1][1] = "x";
    this.board[1][2] = "o";
    this.board[2][0] = "o";

    $scope.$watch("ticTac.currentPlayer", player => {
      if(player === this.players.player) {
        this.humanMove = true;
      } else {
        this.aiMove(this.board);
      }
    })

  }

  fillBoard() {
    for (var i = 0; i < 3; i++) {
      this.board[i] = new Array(3);

      for (var j = 0; j < 3; j++) {
        this.board[i][j] = " ";
      }
    }
  }

  evaluate(board) {
    //check rows
    for (var row = 0; row < 3; row++) {
      if (board[row][0] === board[row][1] && board[row][1] === board[row][2]) {
        if (board[row][0] === this.players.ai) {
          return 10;
        } else if (board[row][0] === this.players.player) {
          return -10;
        }
      }
    }

    //check columns
    for (var col = 0; col < 3; col++) {
      if (board[0][col] === board[1][col] && board[1][col] === board[2][col]) {
        if (board[0][col] === this.players.ai) {
          return 10;
        } else if (board[0][col] === this.players.player) {
          return -10;
        }
      }
    }

    //check for diagonals
    if (board[0][0] === board[1][1] && board[1][1] === board[2][2]) {
      if (board[0][0] === this.players.ai) {
        return 10;
      } else if (board[0][0] === this.players.player) {
        return -10;
      }
    }

    if (board[0][2] === board[1][1] && board[1][1] === board[2][0]) {
      if (board[0][2] === this.players.ai) {
        return 10;
      } else if (board[0][2] === this.players.player) {
        return -10;
      }
    }

    //if no player won return 0
    return 0;
  }

  minimax(board, isMax) {
    var score = this.evaluate(board);

    if (score === 10 || score === -10) {
      return score;
    }

    if(!this.isMoveLeft(board)) {
      return 0;
    }

    if (isMax) {

      var best = -1000;

      for (var i = 0; i < 3; i++) {
        for (var j = 0; j < 3; j++) {

          if (board[i][j] === " ") {
            board[i][j] = this.players.ai;

            best = Math.max(best, this.minimax(board, !isMax));

            board[i][j] = " ";
          }
        }
      }
      return best;

    } else {

      var best = 1000;

      for (var i = 0; i < 3; i++) {
        for (var j = 0; j < 3; j++) {

          if (board[i][j] === " ") {
            board[i][j] = this.players.player;

            best = Math.min(best, this.minimax(board, !isMax));

            board[i][j] = " ";
          }
        }
      }

      return best;
    }
  }

  isMoveLeft(board) {
    for (var i = 0; i < 3; i++) {
      for (var j = 0; j < 3; j++) {
        if (board[i][j] === " ")
          return true;
      }
    }
    return false;
  }

  makeBestMove(board) {
    var bestVal = -1000;

    this.move.row = -1;
    this.move.cell = -1;

    for(var i = 0; i < 3; i++) {
      for (var j = 0; j < 3; j++) {
        if(board[i][j] === " ") {
          board[i][j] === this.currentPlayer;

          var moveVal = this.minimax(board, false);

          board[i][j] === " ";

          if(moveVal > bestVal) {
            this.move.row = i;
            this.move.cell = j;
            bestVal = moveVal;
          }
        }
      }
    }

    return this.move;
  }

  aiMove(board) {
    var currentMove;

    if(!this.isMoveLeft(this.board)) {

      return;
    }

    currentMove = this.makeBestMove(board);
    board[currentMove.row][currentMove.cell] = this.currentPlayer;
    this.currentPlayer = this.players.player;
  }

  makeMove(row, cell) {

    if(this.board[row][cell] === " ") {
      this.board[row][cell] = this.players.player;
    }
    this.currentPlayer = this.players.ai;
  }
}

export default TicTacToeController;

启动板看起来是：

如你所见，下一个最佳着法应该是 (2,2)，但是 minimax 算法将值设置为 (2,0)。

我试过调试，还是找不到错误。

Answer 1

在您的 makeBestMove 方法中，这些行：

board[i][j] === this.currentPlayer;
...
board[i][j] === " ";

应该使用赋值等于：

board[i][j] = this.currentPlayer;
...
board[i][j] = " ";

=== 是比较运算符。因此，您正在比较这些值并在不更改任何内容的情况下获得 true。

目前，由于您没有在调用 minimax 之前进行赋值，因此每次都会返回相同的 best 结果。

极小极大算法的井字游戏

Tic tac toe with minimax algorithm

javascript

algorithm

tic-tac-toe

minimax

angular