minimax - Minimax 单独有效，但带有 alpha-beta 修剪的 minimax 不起作用

Question

当我在没有 alpha beta 修剪的情况下运行我的代码时，它运行得非常好。但是，当我尝试添加 alpha beta 修剪时，我开始收到类似“tictactoe:349 Uncaught TypeError: Cannot read property '0' of undefined at bestMove (tictactoe:349) at :1:1”之类的错误我一直在使用 Sebastian Lague 关于极小极大和 alpha-beta 修剪的视频。

board = boardBackup;

function eval(){
  var i;
  for(i=0; i<3; i++){
    if(board[0][i] == board[1][i] && board[0][i] == board[2][i] && board[0][i] != null){
      if(board[0][i] == "o"){
        return 1;
      } else{
        return -1;
      }
    }
    else if(board[i].join("") == "xxx" || board[i].join("") == "ooo"){
      if(board[i][0] == "o"){
        return 1;
      } else{
        return -1;
      }
    }
    else if(board[0][0] == board[1][1] && board[1][1] == board[2][2] && board[0][0] != null){
      if(board[0][0] == "o"){
        return 1;
      } else{
        return -1;
      }
    }
    else if(board[0][2] == board[1][1] && board[1][1] == board[2][0] && board[0][2] != null){
      if(board[0][2] == "o"){
        return 1;
      } else{
        return -1;
      }
    }
    }
    if(!board[0].includes(null) && !board[1].includes(null) && !board[2].includes(null)){
return 0;
  }
}

function bestMove(){
  var topMove;
  var value = -Infinity;
  var movesLegal = legalMoves();
  var currentMove;
  var i;
  for(i=0; i<movesLegal.length; i++){
    board[legalMoves()[i][0]][legalMoves()[i][1]] = "o";
    move = minimax(board, 9, -Infinity, Infinity, false)
    if(move>value){
      topMove = JSON.parse(JSON.stringify(board))
      value = move;
    }
board[movesLegal[i][0]][movesLegal[i][1]] = null;
  }
board = topMove;
}

function minimax(position, depth, alpha, beta, maximizing){
  var value;
if(depth == 0 || eval() != undefined){
  return eval()
}
if(maximizing){
  value = -Infinity
  var movesLegal = legalMoves();
  var i;
  for(i=0; i<movesLegal.length; i++){
    board[movesLegal[i][0]][movesLegal[i][1]] = "o";
    evaluation = minimax(board, depth -1, alpha, beta, false)
    value = Math.max(value, evaluation);
    alpha = Math.max(alpha, evaluation)
    if(beta <= alpha){
      break
    }
    board[movesLegal[i][0]][movesLegal[i][1]] = null;
  }
  return value;
}
else{
  value = Infinity
  var movesLegal = legalMoves();
  var i;
  for(i=0; i<movesLegal.length; i++){
    board[movesLegal[i][0]][movesLegal[i][1]] = "x";
    evaluation = minimax(board, depth-1, alpha, beta, true)
    value = Math.min(value, evaluation)
    beta = Math.min(beta, evaluation)
    if(beta <= alpha){
      break
    }
    board[movesLegal[i][0]][movesLegal[i][1]] = null;
  }
  return value;
}
}
function legalMoves(){
  var movesLegal = [];
  var i;
  var j;
  for(i=0; i<3; i++){
    for(j=0; j<3; j++){
      if(board[i][j] == null){
        movesLegal[movesLegal.length] = i.toString() + j;
      }
    }
  }
  return movesLegal;
}
function tictac(input){
  board[input[0]][input[1]] = "x";
}
function gameWin(){
  if(eval() == 1){
    alert("O Wins!")
  }
  else if(eval() == -1){
    alert("X Wins!")
  }
  else if(eval() == 0){
    alert("Tie!")
  }
}

编辑：我第一次发布了错误的代码

标签： minimaxalpha-beta-pruning