Minimax 算法中的 Alpha-Beta 剪枝不会提高性能

Question

我正在尝试在我的国际象棋引擎中实施 alpha-beta 修剪，但没有性能差异，我可能做错了什么？我尝试在控制台记录算法切割一个分支的次数，但它是数百次，所以它正确地修剪了搜索树。即使这样，该算法也没有明显的性能改进。

电路板评估平均需要大约 80 毫秒。使用 alpha-beta 修剪 minimax/alpha beta 算法需要 1.8 秒查看深度 3，而没有 minimax/alpha-beta 需要 1.5 秒。

代码如下：

const board = [
  [{pieceName: "blackCastle"}, {pieceName: "blackHorse"}, {pieceName: "blackBishop"}, {pieceName: "blackQueen"}, {pieceName: "blackKing"}, {pieceName: "blackBishop"}, {pieceName: "blackHorse"}, {pieceName: "blackCastle"}],
  [{pieceName: "blackPawn"}, {pieceName: "blackPawn"}, {pieceName: "blackPawn"}, {pieceName: "blackPawn"}, {pieceName: "blackPawn"}, {pieceName: "blackPawn"}, {pieceName: "blackPawn"}, {pieceName: "blackPawn"}],
  ["vacant", "vacant", "vacant", "vacant", "vacant", "vacant", "vacant", "vacant"],
  ["vacant", "vacant", "vacant", "vacant", "vacant", "vacant", "vacant", "vacant"],
  ["vacant", "vacant", "vacant", "vacant", "vacant", "vacant", "vacant", "vacant"],
  ["vacant", "vacant", "vacant", "vacant", "vacant", "vacant", "vacant", "vacant"],
  [{pieceName: "whitePawn"}, {pieceName: "whitePawn"}, {pieceName: "whitePawn"}, {pieceName: "whitePawn"}, {pieceName: "whitePawn"}, {pieceName: "whitePawn"}, {pieceName: "whitePawn"}, {pieceName: "whitePawn"}],
  [{pieceName: "whiteCastle"}, {pieceName: "whiteHorse"}, {pieceName: "whiteBishop"}, {pieceName: "whiteQueen"}, {pieceName: "whiteKing"}, {pieceName: "whiteBishop"}, {pieceName: "whiteHorse"}, {pieceName: "whiteCastle"}]
];

function pawnMoves(piecePosition, board){
  let moves = getEnpassantMoves(piecePosition, board);
  let pieceType = getPieceType(piecePosition, board);

  if(piecePosition.y - 1 >= 0 && piecePosition.x - 1 >= 0){
    var isEnemyInTopLeft = !isItemInArray(pieceType, board[piecePosition.y - 1][piecePosition.x - 1].pieceName) && board[piecePosition.y - 1][piecePosition.x - 1] != "vacant";
  }
  if(piecePosition.y - 1 >= 0 && piecePosition.x + 1 < 8){
    var isEnemyInTopRight = !isItemInArray(pieceType, board[piecePosition.y - 1][piecePosition.x + 1].pieceName) && board[piecePosition.y - 1][piecePosition.x + 1] != "vacant";
  }
  if(piecePosition.y + 1 < 8 && piecePosition.x - 1 >= 0){
    var isEnemyInBottomLeft = !isItemInArray(pieceType, board[piecePosition.y + 1][piecePosition.x - 1].pieceName) && board[piecePosition.y + 1][piecePosition.x - 1] != "vacant";
  }
  if(piecePosition.y + 1 < 8 && piecePosition.x + 1 < 8){
    var isEnemyInBottomRight = !isItemInArray(pieceType, board[piecePosition.y + 1][piecePosition.x + 1].pieceName) && board[piecePosition.y + 1][piecePosition.x + 1] != "vacant";
  }

function copyBoardArray(board){
  return JSON.parse(JSON.stringify(board));
}

function reverse(array){
  return array.reverse();
}

const whitePieces = ["whitePawn", "whiteCastle", "whiteHorse", "whiteBishop", "whiteQueen", "whiteKing"];
const blackPieces = ["blackPawn", "blackCastle", "blackHorse", "blackBishop", "blackQueen", "blackKing"];

function isItemInArray(array, object){
  return (array.indexOf(object) == -1 ? false : true);
}

let whiteKingPieceSquareTable = [
  [-3, -4, -4, -5, -5, -4, -4, -3],
  [-3, -4, -4, -5, -5, -4, -4, -3],
  [-3, -4, -4, -5, -5, -4, -4, -3],
  [-3, -4, -4, -5, -5, -4, -4, -3],
  [-2, -3, -3, -4, -4, -3, -3, -2],
  [-1, -2, -2, -2, -2, -2, -2, -1],
  [2, 2, 0, 0, 0, 0, 2, 2],
  [2, 3, 1, 0, 0, 1, 3, 2]
];
let whiteQueenPieceSquareTable = [
  [-2, -1, -1, -0.5, -0.5, -1, -1, -2],
  [-1, 0, 0, 0, 0, 0, 0, -1],
  [-1, 0, 0.5, 0.5, 0.5, 0.5, 0, -1],
  [-0.5, 0, 0.5, 0.5, 0.5, 0.5, 0, -0.5],
  [0, 0, 0.5, 0.5, 0.5, 0.5, 0, -0.5],
  [-1, 0.5, 0.5, 0.5, 0.5, 0.5, 0, -1],
  [-1, 0, 0.5, 0, 0, 0, 0, -1],
  [-2, -1, -1, -0.5, -0.5, -1, -1, -2]
];
let whiteCastlePieceSquareTable = [
  [0, 0, 0, 0, 0, 0, 0, 0],
  [0.5, 1, 1, 1, 1, 1, 1, 0.5],
  [-0.5, 0, 0, 0, 0, 0, 0, -0.5],
  [-0.5, 0, 0, 0, 0, 0, 0, -0.5],
  [-0.5, 0, 0, 0, 0, 0, 0, -0.5],
  [-0.5, 0, 0, 0, 0, 0, 0, -0.5],
  [-0.5, 0, 0, 0, 0, 0, 0, -0.5],
  [0, 0, 0, 0.5, 0.5, 0, 0, 0]
];
let whiteBishopPieceSquareTable = [
  [-2, -1, -1, -1, -1, -1, -1, -2],
  [-1, 0, 0, 0, 0, 0, 0, -1],
  [-1, 0, 0.5, 1, 1, 0.5, 0, -1],
  [-1, 0.5, 0.5, 1, 1, 0.5, 0.5, -1],
  [-1, 0, 1, 1, 1, 1, 0, -1],
  [-1, 1, 1, 1, 1, 1, 1, -1],
  [-1, 0.5, 0, 0, 0, 0, 0.5, -1],
  [-2, -1, -1, -1, -1, -1, -1, -2]
];
let whiteHorsePieceSquareTable = [
  [-5, -4, -3, -3, -3, -3, -4, -5],
  [-4, -2, 0, 0, 0, 0, -2, -4],
  [-3, 0, 1, 1.5, 1.5, 1, 0, -3],
  [-3, 0.5, 1.5, 2, 2, 1.5, 0.5, -3],
  [-3, 0, 1.5, 2, 2, 1.5, 0, -3],
  [-3, 0.5, 1, 1.5, 1.5, 1, 0.5, -3],
  [-4, -2, 0, 0.5, 0.5, 0, -2, -4],
  [-5, -4, -3, -3, -3, -3, -4, -5],
];
let whitePawnPieceSquareTable = [
  [0, 0, 0, 0, 0, 0, 0, 0],
  [5, 5, 5, 5, 5, 5, 5, 5],
  [1, 1, 2, 3, 3, 2, 1, 1],
  [0.5, 0.5, 1, 2.5, 2.5, 1, 0.5, 0.5],
  [0, 0, 0, 2, 2, 0, 0, 0],
  [0.5, -0.5, -1, 0, 0, -1, -0.5, 0.5],
  [0.5, 1, 1, -2, -2, 1, 1, 0.5],
  [0, 0, 0, 0, 0, 0, 0, 0]
];
let blackKingPieceSquareTable = reverse(getNegativePieceSquareTable(whiteKingPieceSquareTable));
let blackQueenPieceSquareTable = reverse(getNegativePieceSquareTable(whiteQueenPieceSquareTable));
let blackCastlePieceSquareTable = reverse(getNegativePieceSquareTable(whiteCastlePieceSquareTable));
let blackBishopPieceSquareTable = reverse(getNegativePieceSquareTable(whiteBishopPieceSquareTable));
let blackHorsePieceSquareTable = reverse(getNegativePieceSquareTable(whiteBishopPieceSquareTable));
let blackPawnPieceSquareTable = reverse(getNegativePieceSquareTable(whitePawnPieceSquareTable));



  let boardPosition = board[piecePosition.y][piecePosition.x];
  let isPieceInBackOfBoard = piecePosition.y == 6;
  let isPieceInTopOfBoard = piecePosition.y == 1;
  humanPlayer == whitePieces ? pawnInBottom = "whitePawn" : pawnInBottom = "blackPawn";
  if(boardPosition.pieceName == pawnInBottom){
    if(isPieceInBackOfBoard){
      if(board[piecePosition.y - 1][piecePosition.x] == "vacant"){
        moves.push({node: {board: update(board, piecePosition, {x: piecePosition.x, y: piecePosition.y - 1}), hasPawnMoved: true, hasPieceBeenCaptured: false}, to: {x: piecePosition.x, y: piecePosition.y - 1}});
      }
      if(board[piecePosition.y - 2][piecePosition.x] == "vacant" && board[piecePosition.y - 1][piecePosition.x] == "vacant"){
        moves.push({node: {board: update(board, piecePosition, {x: piecePosition.x, y: piecePosition.y - 2}), hasPawnMoved: true, hasPieceBeenCaptured: false}, to: {x: piecePosition.x, y: piecePosition.y - 2}});
      }
    } else if(piecePosition.y - 1 >= 0){
      if(board[piecePosition.y - 1][piecePosition.x] == "vacant"){
        moves.push({node: {board: update(board, piecePosition, {x: piecePosition.x, y: piecePosition.y - 1}), hasPawnMoved: true, hasPieceBeenCaptured: false}, to: {x: piecePosition.x, y: piecePosition.y - 1}});
      }
    }
    if(isEnemyInTopLeft){
      moves.push({node: {board: update(board, piecePosition, {x: piecePosition.x - 1, y: piecePosition.y - 1}), hasPawnMoved: true, hasPieceBeenCaptured: true}, to: {x: piecePosition.x - 1, y: piecePosition.y - 1}});
    }
    if(isEnemyInTopRight){
      moves.push({node: {board: update(board, piecePosition, {x: piecePosition.x + 1, y: piecePosition.y - 1}), hasPawnMoved: true, hasPieceBeenCaptured: true}, to: {x: piecePosition.x + 1, y: piecePosition.y - 1}});
    }
  } else {
    if(isPieceInTopOfBoard){
      if(board[piecePosition.y + 1][piecePosition.x] == "vacant"){
        moves.push({node: {board: update(board, piecePosition, {x: piecePosition.x, y: piecePosition.y + 1}), hasPawnMoved: true, hasPieceBeenCaptured: false}, to: {x: piecePosition.x, y: piecePosition.y + 1}});
      }
      if(board[piecePosition.y + 2][piecePosition.x] == "vacant" && board[piecePosition.y + 1][piecePosition.x] == "vacant"){
        moves.push({node: {board: update(board, piecePosition, {x: piecePosition.x, y: piecePosition.y + 2}), hasPawnMoved: true, hasPieceBeenCaptured: false}, to: {x: piecePosition.x, y: piecePosition.y + 2}});
      }
    } else if(piecePosition.y + 1 < 8){
      if(board[piecePosition.y + 1][piecePosition.x] == "vacant"){
        moves.push({node: {board: update(board, piecePosition, {x: piecePosition.x, y: piecePosition.y + 1}), hasPawnMoved: true, hasPieceBeenCaptured: false}, to: {x: piecePosition.x, y: piecePosition.y + 1}});
      }
    }
    if(isEnemyInBottomLeft){
      moves.push({node: {board: update(board, piecePosition, {x: piecePosition.x - 1, y: piecePosition.y + 1}), hasPawnMoved: true, hasPieceBeenCaptured: true}, to: {x: piecePosition.x - 1, y: piecePosition.y + 1}});
    }
    if(isEnemyInBottomRight){
      moves.push({node: {board: update(board, piecePosition, {x: piecePosition.x + 1, y: piecePosition.y + 1}), hasPawnMoved: true, hasPieceBeenCaptured: true}, to: {x: piecePosition.x + 1, y: piecePosition.y + 1}})
    }
  }

  return moves;
}

function castleMoves(piecePosition, board){
  let moves = [];
  let pieceType = getPieceType(piecePosition, board);

  for(i = piecePosition.x + 1; i < 8; i++){
    if(board[piecePosition.y][i] != "vacant" && isItemInArray(pieceType, board[piecePosition.y][i].pieceName)){
      break;
    }
    if(board[piecePosition.y][i] != "vacant" && !isItemInArray(pieceType, board[piecePosition.y][i].pieceName)){
      moves.push({node: {board: update(board, piecePosition, {x: i, y: piecePosition.y}), hasPawnMoved: false, hasPieceBeenCaptured: true}, to: {x: i, y: piecePosition.y}});
      break;
    }
    moves.push({node: {board: update(board, piecePosition, {x: i, y: piecePosition.y}), hasPawnMoved: false, hasPieceBeenCaptured: false}, to: {x: i, y: piecePosition.y}});
  }

  for(i = piecePosition.x - 1; i >= 0; i--){
    if(board[piecePosition.y][i] != "vacant" && isItemInArray(pieceType, board[piecePosition.y][i].pieceName)){
      break;
    }
    if(board[piecePosition.y][i] != "vacant" && !isItemInArray(pieceType, board[piecePosition.y][i].pieceName)){
      moves.push({node: {board: update(board, piecePosition, {x: i, y: piecePosition.y}), hasPawnMoved: false, hasPieceBeenCaptured: true}, to: {x: i, y: piecePosition.y}});
      break;
    }
    moves.push({node: {board: update(board, piecePosition, {x: i, y: piecePosition.y}), hasPawnMoved: false, hasPieceBeenCaptured: false}, to: {x: i, y: piecePosition.y}});
  }

  for(i = piecePosition.y + 1; i < 8; i++){
    if(board[i][piecePosition.x] != "vacant" && isItemInArray(pieceType, board[i][piecePosition.x].pieceName)){
      break;
    }
    if(board[i][piecePosition.x] != "vacant" && !isItemInArray(pieceType, board[i][piecePosition.x].pieceName)){
      moves.push({node: {board: update(board, piecePosition, {x: piecePosition.x, y: i}), hasPawnMoved: false, hasPieceBeenCaptured: true}, to: {x: piecePosition.x, y: i}});
      break;
    }
    moves.push({node: {board: update(board, piecePosition, {x: piecePosition.x, y: i}), hasPawnMoved: false, hasPieceBeenCaptured: false}, to: {x: piecePosition.x, y: i}});
  }

  for(i = piecePosition.y - 1; i >= 0; i--){
    if(board[i][piecePosition.x] != "vacant" && isItemInArray(pieceType, board[i][piecePosition.x].pieceName)){
      break;
    }
    if(board[i][piecePosition.x] != "vacant" && !isItemInArray(pieceType, board[i][piecePosition.x].pieceName)){
      moves.push({node: {board: update(board, piecePosition, {x: piecePosition.x, y: i}), hasPawnMoved: false, hasPieceBeenCaptured: true}, to: {x: piecePosition.x, y: i}});
      break;
    }
    moves.push({node: {board: update(board, piecePosition, {x: piecePosition.x, y: i}), hasPawnMoved: false, hasPieceBeenCaptured: false}, to: {x: piecePosition.x, y: i}});
  }

  return moves; 
}

function update(board, from, to){  
  let boardCopy = copyBoardArray(board);
  boardCopy = setEnpassantTargetSquares(boardCopy, from, to);
  let piece = boardCopy[from.y][from.x];
  boardCopy[from.y][from.x] = "vacant";
  boardCopy[to.y][to.x] = piece;
  boardCopy[to.y][to.x].hasClicked = true;
  return boardCopy;
}

function returnCastledBoard(kingPos, to, board){
  boardDeepClone = copyBoardArray(board);
  let king = boardDeepClone[kingPos.y][kingPos.x];
  if(to.x > kingPos.x){
    castlingCastle = boardDeepClone[to.y][7];
    boardDeepClone[kingPos.y][kingPos.x] = "vacant";
    boardDeepClone[kingPos.y][kingPos.x + 2] = king;
    boardDeepClone[kingPos.y][kingPos.x + 2].hasClicked = true;
    boardDeepClone[kingPos.y][7] = "vacant";
    boardDeepClone[kingPos.y][kingPos.x + 1] = castlingCastle;
  } else {
    castlingCastle = boardDeepClone[to.y][7];
    boardDeepClone[kingPos.y][kingPos.x] = "vacant";
    boardDeepClone[kingPos.y][kingPos.x - 2] = king;
    boardDeepClone[kingPos.y][kingPos.x - 2].hasClicked = true;
    boardDeepClone[kingPos.y][0] = "vacant";
    boardDeepClone[kingPos.y][kingPos.x - 1] = castlingCastle;
  }
  return boardDeepClone;
}

function returnEnpassantBoard(board, target, from, to){
  let boardCopy = copyBoardArray(board);
  boardCopy[target.y][target.x] = "vacant";
  boardCopy = update(boardCopy, from, to);
  return boardCopy;
}

function castlingMoves(pieceType, board){
  let castlingMoves = [];
  pieceType == blackPieces ? king = "blackKing" : king = "whiteKing";
  let kingPos = getPiecePosition(king, board);
  let isPieceBlocking;
  let playerInCheck;
  if(board[kingPos.y][kingPos.x].hasClicked === undefined){
    if(board[kingPos.y][0].hasClicked === undefined &&
      (board[kingPos.y][0].pieceName == "blackCastle" || board[kingPos.y][0].pieceName == "whiteCastle")
    ){
      for(xPos = kingPos.x - 1; xPos >= 1; xPos--){
        if(board[kingPos.y][xPos] == "vacant"){
          isPieceBlocking = false;
        } else if(board[kingPos.y][xPos] != "vacant"){
          isPieceBlocking = true;
          break;
        }
      }
      if(!isPieceBlocking){
        for(xPos = kingPos.x; xPos >= kingPos.x - 2; xPos--){
          bCopy = copyBoardArray(board);
          bCopy = update(board, kingPos, {x: xPos, y: kingPos.y});
          if(isPlayerInCheck(pieceType, bCopy)){
            playerInCheck = true;
            break;
          } else {
            playerInCheck = false;
          }
        }
      }
      if(!isPieceBlocking && !playerInCheck){
        castlingMoves.push({node: {
          board: returnCastledBoard(kingPos, {x: kingPos.x - 2, y: kingPos.y}, board)},
          to: {x: kingPos.x - 2, y: kingPos.y}
        });
      }
    }
    if(board[kingPos.y][7].hasClicked === undefined && 
      (board[kingPos.y][7].pieceName == "blackCastle" || board[kingPos.y][7].pieceName == "whiteCastle")
    ){
      for(xPos = kingPos.x + 1; xPos <= 6; xPos++){
        if(board[kingPos.y][xPos] == "vacant"){
          isPieceBlocking = false;
        } else if(board[kingPos.y][xPos] != "vacant"){
          isPieceBlocking = true;
          break;
        }
      }
      if(!isPieceBlocking){
        for(xPos = kingPos.x; xPos <= kingPos.x + 2; xPos++){
          bCopy = copyBoardArray(board);
          bCopy = update(board, kingPos, {x: xPos, y: kingPos.y});
          if(isPlayerInCheck(pieceType, bCopy)){
            playerInCheck = true;
            break;
          } else {
            playerInCheck = false;
          }
        }
      }
      if(!isPieceBlocking && !playerInCheck){
        castlingMoves.push({node: {
          board: returnCastledBoard(kingPos, {x: kingPos.x + 2, y: kingPos.y}, board)},
          to: {x: kingPos.x + 2, y: kingPos.y}
        });
      }
    }
  }
  return castlingMoves;
}

function bishopMoves(piecePosition, board){
  let moves = [];
  let pieceType = getPieceType(piecePosition, board);

  x = piecePosition.x + 1;
  y = piecePosition.y + 1;

  while(x < 8 && y < 8){
    if(board[y][x] != "vacant" && isItemInArray(pieceType, board[y][x].pieceName)){
      break;
    }
    if(board[y][x] != "vacant" && !isItemInArray(pieceType, board[y][x].pieceName)){
      moves.push({node: {board: update(board, piecePosition, {x: x, y: y})}, to: {x: x, y: y}});
      break;
    }
    moves.push({node: {board: update(board, piecePosition, {x: x, y: y})}, to: {x: x, y: y}});
    x += 1;
    y += 1;
  }

  x = piecePosition.x - 1;
  y = piecePosition.y - 1;

  while(x >= 0 && y >= 0){
    if(board[y][x] != "vacant" && isItemInArray(pieceType, board[y][x].pieceName)){
      break;
    }
    if(board[y][x] != "vacant" && !isItemInArray(pieceType, board[y][x].pieceName)){
      moves.push({node: {board: update(board, piecePosition, {x: x, y: y})}, to: {x: x, y: y}});
      break;
    }
    moves.push({node: {board: update(board, piecePosition, {x: x, y: y})}, to: {x: x, y: y}});
    x -= 1;
    y -= 1;
  }

  x = piecePosition.x - 1;
  y = piecePosition.y + 1;

  while(x >= 0 && y < 8){
    if(board[y][x] != "vacant" && isItemInArray(pieceType, board[y][x].pieceName)){
      break;
    }
    if(board[y][x] != "vacant" && !isItemInArray(pieceType, board[y][x].pieceName)){
      moves.push({node: {board: update(board, piecePosition, {x: x, y: y})}, to: {x: x, y: y}});
      break;
    }
    moves.push({node: {board: update(board, piecePosition, {x: x, y: y})}, to: {x: x, y: y}});
    x -= 1;
    y += 1;
  }

  x = piecePosition.x + 1;
  y = piecePosition.y - 1;

  while(x < 8 && y >= 0){
    if(board[y][x] != "vacant" && isItemInArray(pieceType, board[y][x].pieceName)){
      break;
    }
    if(board[y][x] != "vacant" && !isItemInArray(pieceType, board[y][x].pieceName)){
      moves.push({node: {board: update(board, piecePosition, {x: x, y: y})}, to: {x: x, y: y}});
      break;
    }
    moves.push({node: {board: update(board, piecePosition, {x: x, y: y})}, to: {x: x, y: y}});
    x += 1;
    y -= 1;
  }

  return moves; 
}

function horseMoves(piecePosition, board){
  let moves = [];
  let pieceType = getPieceType(piecePosition, board);

  if(piecePosition.x + 1 < 8 && piecePosition.y + 2 < 8){
    if(board[piecePosition.y + 2][piecePosition.x + 1] == "vacant" || !isItemInArray(pieceType, board[piecePosition.y + 2][piecePosition.x + 1].pieceName)){
      moves.push({node: {board: update(board, piecePosition, {x: piecePosition.x + 1, y: piecePosition.y + 2})}, to: {x: piecePosition.x + 1, y: piecePosition.y + 2}});
    }
  }

  if(piecePosition.x - 1 >= 0 && piecePosition.y + 2 < 8){
    if(board[piecePosition.y + 2][piecePosition.x - 1] == "vacant" || !isItemInArray(pieceType, board[piecePosition.y + 2][piecePosition.x - 1].pieceName)){
      moves.push({node: {board: update(board, piecePosition, {x: piecePosition.x - 1, y: piecePosition.y + 2})}, to: {x: piecePosition.x - 1, y: piecePosition.y + 2}});
    }
  }

  if(piecePosition.x + 1 < 8 && piecePosition.y - 2 >= 0){
    if(board[piecePosition.y - 2][piecePosition.x + 1] == "vacant" || !isItemInArray(pieceType, board[piecePosition.y - 2][piecePosition.x + 1].pieceName)){
      moves.push({node: {board: update(board, piecePosition, {x: piecePosition.x + 1, y: piecePosition.y - 2})}, to: {x: piecePosition.x + 1, y: piecePosition.y - 2}});
    }
  }

  if(piecePosition.x - 1 >= 0 && piecePosition.y - 2 >= 0){
    if(board[piecePosition.y - 2][piecePosition.x - 1] == "vacant" || !isItemInArray(pieceType, board[piecePosition.y - 2][piecePosition.x - 1].pieceName)){
      moves.push({node: {board: update(board, piecePosition, {x: piecePosition.x - 1, y: piecePosition.y - 2})}, to: {x: piecePosition.x - 1, y: piecePosition.y - 2}});
    }
  }

  if(piecePosition.x + 2 < 8 && piecePosition.y + 1 < 8){
    if(board[piecePosition.y + 1][piecePosition.x + 2] == "vacant" || !isItemInArray(pieceType, board[piecePosition.y + 1][piecePosition.x + 2].pieceName)){
      moves.push({node: {board: update(board, piecePosition, {x: piecePosition.x + 2, y: piecePosition.y + 1})}, to: {x: piecePosition.x + 2, y: piecePosition.y + 1}});
    }
  }

  if(piecePosition.x - 2 >= 0 && piecePosition.y + 1 < 8){
    if(board[piecePosition.y + 1][piecePosition.x - 2] == "vacant" || !isItemInArray(pieceType, board[piecePosition.y + 1][piecePosition.x - 2].pieceName)){
      moves.push({node: {board: update(board, piecePosition, {x: piecePosition.x - 2, y: piecePosition.y + 1})}, to: {x: piecePosition.x - 2, y: piecePosition.y + 1}});
    }
  }

  if(piecePosition.x + 2 < 8 && piecePosition.y - 1 >= 0){
    if(board[piecePosition.y - 1][piecePosition.x + 2] == "vacant" || !isItemInArray(pieceType, board[piecePosition.y - 1][piecePosition.x + 2].pieceName)){
      moves.push({node: {board: update(board, piecePosition, {x: piecePosition.x + 2, y: piecePosition.y - 1})}, to: {x: piecePosition.x + 2, y: piecePosition.y - 1}});
    }
  }

  if(piecePosition.x - 2 >= 0 && piecePosition.y - 1 >= 0){
    if(board[piecePosition.y - 1][piecePosition.x - 2] == "vacant" || !isItemInArray(pieceType, board[piecePosition.y - 1][piecePosition.x - 2].pieceName)){
      moves.push({node: {board: update(board, piecePosition, {x: piecePosition.x - 2, y: piecePosition.y - 1})}, to: {x: piecePosition.x - 2, y: piecePosition.y - 1}});
    }
  }

  return moves;
}

function kingMoves(piecePosition, board){
  moves = [];

  let pieceType = getPieceType(piecePosition, board);

  if(piecePosition.x + 1 < 8){
    if(board[piecePosition.y][piecePosition.x + 1] == "vacant" || !isItemInArray(pieceType, board[piecePosition.y][piecePosition.x + 1].pieceName)){
      moves.push({node: {board: update(board, piecePosition, {x: piecePosition.x + 1, y: piecePosition.y})}, to: {x: piecePosition.x + 1, y: piecePosition.y}});
    }
  }

  if(piecePosition.x - 1 >= 0){
    if(board[piecePosition.y][piecePosition.x - 1] == "vacant" || !isItemInArray(pieceType, board[piecePosition.y][piecePosition.x - 1].pieceName)){
      moves.push({node: {board: update(board, piecePosition, {x: piecePosition.x - 1, y: piecePosition.y})}, to: {x: piecePosition.x - 1, y: piecePosition.y}});
    }
  }

  if(piecePosition.y + 1 < 8){
    if(board[piecePosition.y + 1][piecePosition.x] == "vacant" || !isItemInArray(pieceType, board[piecePosition.y + 1][piecePosition.x].pieceName)){
      moves.push({node: {board: update(board, piecePosition, {x: piecePosition.x, y: piecePosition.y + 1})}, to: {x: piecePosition.x, y: piecePosition.y + 1}});
    }
  }

  if(piecePosition.y - 1 >= 0){
    if(board[piecePosition.y - 1][piecePosition.x] == "vacant" || !isItemInArray(pieceType, board[piecePosition.y - 1][piecePosition.x].pieceName)){
      moves.push({node: {board: update(board, piecePosition, {x: piecePosition.x, y: piecePosition.y - 1})}, to: {x: piecePosition.x, y: piecePosition.y - 1}});
    }
  }

  if(piecePosition.y - 1 >= 0 && piecePosition.x - 1 >= 0){
    if(board[piecePosition.y - 1][piecePosition.x - 1] == "vacant" || !isItemInArray(pieceType, board[piecePosition.y - 1][piecePosition.x - 1].pieceName)){
      moves.push({node: {board: update(board, piecePosition, {x: piecePosition.x - 1, y: piecePosition.y - 1})}, to: {x: piecePosition.x - 1, y: piecePosition.y - 1}});
    }
  }

  if(piecePosition.y + 1 < 8 && piecePosition.x + 1 < 8){
    if(board[piecePosition.y + 1][piecePosition.x + 1] == "vacant" || !isItemInArray(pieceType, board[piecePosition.y + 1][piecePosition.x + 1].pieceName)){
      moves.push({node: {board: update(board, piecePosition, {x: piecePosition.x + 1, y: piecePosition.y + 1})}, to: {x: piecePosition.x + 1, y: piecePosition.y + 1}});
    }
  }

  if(piecePosition.y + 1 < 8 && piecePosition.x - 1 >= 0){
    if(board[piecePosition.y + 1][piecePosition.x - 1] == "vacant" || !isItemInArray(pieceType, board[piecePosition.y + 1][piecePosition.x - 1].pieceName)){
      moves.push({node: {board: update(board, piecePosition, {x: piecePosition.x - 1, y: piecePosition.y + 1})}, to: {x: piecePosition.x - 1, y: piecePosition.y + 1}});
    }
  }

  if(piecePosition.y - 1 >= 0 && piecePosition.x + 1 < 8){
    if(board[piecePosition.y - 1][piecePosition.x + 1] == "vacant" || !isItemInArray(pieceType, board[piecePosition.y - 1][piecePosition.x + 1].pieceName)){
      moves.push({node: {board: update(board, piecePosition, {x: piecePosition.x + 1, y: piecePosition.y - 1})}, to: {x: piecePosition.x + 1, y: piecePosition.y - 1}});
    }
  }

  return moves;
}

function queenMoves(piecePosition, board){
  let castleMovesForQueen = castleMoves(piecePosition, board);
  let bishopMovesForQueen = bishopMoves(piecePosition, board);
  let moves = castleMovesForQueen.concat(bishopMovesForQueen);
  return moves;
}

function getValidMoves(piecePosition, board){
  let boardPos = board[piecePosition.y][piecePosition.x]
  let pieceType = getPieceType(piecePosition, board);
  let unfilteredMoveSet;

  if(castlingMoves(pieceType, board).length != 0 && (boardPos.pieceName == "whiteKing" || boardPos.pieceName == "blackKing")){
    unfilteredMoveSet = castlingMoves(pieceType, board);
    let unfilteredMoveSetAddon = getUncheckedMoves(piecePosition, board).move;
    unfilteredMoveSet = unfilteredMoveSet.concat(unfilteredMoveSetAddon);
  } else {
    unfilteredMoveSet = getUncheckedMoves(piecePosition, board).move;
  }

  for(index = unfilteredMoveSet.length - 1; index >= 0; index--){
    if(isPlayerInCheck(pieceType, unfilteredMoveSet[index].node.board)){
      unfilteredMoveSet.splice(index, 1);
    }
  }
  return {from: piecePosition, move: unfilteredMoveSet};
}

function isCheckmate(pieceType, board){
  let validSpots = availableValidSpots(board, pieceType);
  if(validSpots.length == 0 && isPlayerInCheck(pieceType, board)){
    return true;
  }
  return false;
}

function isPlayerInCheck(player, board){
  setPlayerInfo(player, board);

  for(opponentMove = 0; opponentMove < opponentMoves.length; opponentMove++){
    for(square = 0; square < opponentMoves[opponentMove].move.length; square++){
      if(opponentMoves[opponentMove].move[square].to.x == kingPosition.x && opponentMoves[opponentMove].move[square].to.y == kingPosition.y){
        return true;
      }
    }
  }
  return false;
}

function findBestMove(board, player){
  player == blackPieces ? isMaximisingPlayer = false : isMaximisingPlayer = true;
  let availSpots = availableValidSpots(board, player);
  if(isMaximisingPlayer){
    let bestScore = -Infinity;
    for(availSpot = 0; availSpot < availSpots.length; availSpot++){
      let value = alphaBeta(availSpots[availSpot].node, 2, -Infinity, Infinity, true);
      if(value > bestScore){
        bestScore = value;
        bestMove = availSpots[availSpot];
      }
    }
  } else {
    let bestScore = Infinity;
    for(availSpot = 0; availSpot < availSpots.length; availSpot++){
      let value = alphaBeta(availSpots[availSpot].node, 2, -Infinity, Infinity, false);
      if(value < bestScore){
        bestScore = value;
        bestMove = availSpots[availSpot];
      }
    }
  }
  return bestMove;
}

function isTerminalNode(node){
  return isCheckmate(blackPieces, node) || isCheckmate(whitePieces, node);
}

function alphaBeta(node, depth, alpha, beta, isMaximisingPlayer){
  if(depth == 0 || isTerminalNode(node)){
    return evaluateBoard(node);
  }
  isMaximisingPlayer ? player = whitePieces : player = blackPieces;
  let availableSpots = availableValidSpots(node, player);
  if(isMaximisingPlayer){
    value = -Infinity;
    for(availableSpot = 0; availableSpot < availableSpots.length; availableSpot++){
      let child = availableSpots[availableSpot].node;
      value = Math.max(value, alphaBeta(child, depth - 1, alpha, beta, false));
      alpha = Math.max(alpha, value);
      if(beta <= alpha){
        //console.log("BREAK");
        break;
      }
    }
    return value;
  } else {
    value = Infinity;
    for(availableSpot = 0; availableSpot < availableSpots.length; availableSpots++){
      let child = availableSpots[availableSpot].node;
      value = Math.min(value, alphaBeta(child, depth - 1, alpha, beta, true));
      beta = Math.min(beta, value);
      if(beta <= alpha){
        //console.log("BREAK");
        break;
      }
    }
    return value;
  }
}

Answer 1

现在您正在执行两次递归调用，一次用于获取分数，一次用于移动。删除 findBestMove 函数并在您的 alphaBeta 中编写如下内容（伪代码）：

function minimax(board, .....):
    availableMoves = getAvailableMoves(board, player)

    if depth == 0 or isCheckMate or isDraw:
        return None, evaluation(board)

    if maxPlayer:
        bestValue = -inf
        for move in availableMoves:
            boardCopy = deepcopy(board)
            boardCopy.move(move)
            value = minimax(boardCopy, ....)[1]

            if value > bestValue:
                bestValue = value
                bestMove = move

        return bestMove, bestValue

    else:
        .......

Minimax 算法中的 Alpha-Beta 剪枝不会提高性能

No performance increase with Alpha-Beta pruning in Minimax algorithm

javascript

performance

minimax

alpha-beta-pruning