当前位置: 首页 > 知识库问答 >
问题:

极小极大算法中的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修剪的minimax算法,现在我正尝试使用negamax方法重写它。我希望这两者是等价的,因为negamax只是一种编写minimax的技术。但由于某种原因,我的两种算法表现不同。当我在相同的输入上运行它们时,negamax版本似乎评估了更多的状态,所以我认为alpha-beta修剪一定有问题。 下面的代码显示了这两种算法(

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