登录
当前位置： 首页 > 知识库问答 >
问题：

极小极大算法中的Alpha-Beta修剪不会提高性能

谢翰学
2023-03-14

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

董事会评估平均需要80毫秒左右。使用alpha-beta修剪，查看深度3时，minimax/alpha-beta算法需要1.8秒，而不使用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;
  }
}

共有1个答案

贲骏喆
2023-03-14

现在，您正在执行两次递归调用，一次用于获取分数，一次用于移动。删除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:
        .......
 类似资料：
  • 使用alpha beta修剪转换极大极小值到负极

    我已经为游戏跳棋编写了一个带有alpha-beta修剪的minimax算法，现在我正尝试使用negamax方法重写它。我希望这两者是等价的，因为negamax只是一种编写minimax的技术。但由于某种原因，我的两种算法表现不同。当我在相同的输入上运行它们时，negamax版本似乎评估了更多的状态，所以我认为alpha-beta修剪一定有问题。 下面的代码显示了这两种算法（

  • 使用alpha beta修剪PYTHON实现迭代深化与极小极大算法

    我已经实现了一个带有alpha beta修剪的NegaMax算法（这只是一个较短版本的极小值算法）。现在我想实现迭代深化，这样我就可以为每个深度找到最佳移动，然后根据之前层的分数重新排序树下的节点，以便我的alphabeta修剪工作更有效。 以下是我迄今为止所做的工作： 这里gs是随每一步移动而变化的游戏属性，包含了所有关于游戏在t点的信息，比如是否可以施法或者是否有可能的内移。我的egamax算

  • 极大极小与阿尔法贝塔修剪算法

    我最近实现了极小极大和阿尔法贝塔修剪算法，我100%确定（自动分级器）我正确地实现了它们。但是当我执行我的程序时，它们的行为不同。我99%确定极小极大和阿尔法贝塔的结束状态应该是相同的。我说得对吗？它们在实现结果的路径上会有所不同吗？因为我们忽略了min将选择的一些值，而max不会选择这些值，反之亦然。

  • 极小极大αβ算法

    我想我终于对minimax和Alpha-beta修剪有所了解了，但实现它完全是另一回事！ 根据我的理解，基础是：您为某些动作分配一个启发式函数分数（Gomoku为例）。 如果一行有5个，我们应该分配一个高值，比如9999，因为这是一个胜利的举动 当我们必须在Java中实现这一点时，我的问题来了！ 我有一块彩色[][]板（8x8），其中黑色是播放器1，白色是播放器2，null表示空白，我不知道我们应

  • 极大极小算法的优缺点

    极小极大算法的一个缺点是每个板状态必须被访问两次：一次查找其子级，第二次评估启发式值。 极小极大算法还有其他缺点或优点吗？对于像象棋这样的游戏，还有更好的选择吗？（当然是带有α-β修剪的极小极大算法，但还有其他吗？）

  • 如何用极小极大算法解决Tic-Tac-Toe 4x4游戏。α-β修剪

    我做了一个Tic-Tac-Toe游戏，使用Minimax和Alpha-Beta修剪。我想为Tic-Tac-Toe（10x10）游戏制作一个计算机AI，但它的游戏树大得离谱。 我的代码是这样的，我只需要更改两个变量就可以更改一行中所需的板大小单元格。例子： 和 我希望你明白了。 所以，我把我的计划从10x10改为3x3，效果很好。 然后我改变和，使其成为（4x4）井字游戏。 现在，我认为使用Alph

相关问答

极大极小算法的优缺点如何用极小极大算法解决Tic-Tac-Toe 4x4游戏。α-β修剪在Tictoe minimax算法中实现alpha-beta修剪具有α-β剪枝问题的极小极大通过 alpha beta 修剪了解最小最大值

相关文章

不添加不必要极值的插值方法极大似然估计和最小二乘估计的关系？总结Pyinstaller的坑及终极解决方法(小结)JNI方法实现图片压缩（压缩率极高）解析极大的Excel 2007文件的最佳语言

相关阅读

8.17美团算法笔试 极差思路小米高性能计算滴滴算法岗 一面拒（体验极差）极米一面面经吉利极氪一面

相关工具

极点CMS极致CMS太极语言极速连连看倒计时极简版

相关文档

Kotlin 极简教程JFinal 极速开发框架收藏 v4.9.01Java 提高篇十大经典排序算法数据挖掘十大算法
快捷导航： 新手教程 算法原理 架构设计 Java进阶 数据库进阶 大厂专栏 面试经验 编程笔记 编程问答 所有专题 文档资料 工具软件 电子书籍 小牛导航
在线工具： 房贷计算器 个税计算器 Linux命令查询 Json格式化 正则表达式 颜色转换 AES加解密 SHA1加密 MD5加密 毒鸡汤 字数统计 随机密码生成 进制转换 Base64编解码 励志句子
Copyright © 2019-2024 小牛知识库@xnip.cn. All Rights Reserved.