使用极小极大算法提高国际象棋机器人的性能

Question

我有一个带 alpha-beta 修剪的极小极大算法，但它非常低效。

class MiniMaxBot
{
constructor(chessGame,player_color)
{
this.chess = chessGame;
this.color = player_color == "w"? 'b': 'w';
this.depthLimit = 3;
}



move()
{ let maxIndex = 0;
  let maxScore = -Infinity;
  let moves = this.chess.moves();
  let fen = this.chess.fen();
  for(let i = 0; i < moves.length; i++)
  { 
    let chess = new Chess();
    chess.load(fen);
    chess.move(moves[i]);
    let score = this.minimax(fen,this.depthLimit,-Infinity, Infinity, true);
    if(maxScore < score )
    {
      maxScore = score;
      maxIndex = i;
    }
    console.log(score);

  }
    return moves[maxIndex];
}

minimax(fen,depth, alpha, beta, max)
{
  let chess  = new Chess();
  chess.load(fen);
 
if(depth <= 0 || this.leafNode(fen) == true)
{
  let value = this.evaluation(fen);
  
  return value;
}


if (max == true)
{
  let moves = chess.moves();
  let bestValue = -Infinity;
  for(let i = 0; i < moves.length; i++)
  {  chess.load(fen);
    chess.move(moves[i]);
    let value = this.minimax(chess.fen(),depth-1, alpha, beta, false);
    bestValue =  Math.max(value,bestValue);

    alpha = Math.max(alpha, bestValue);
    if(beta <= alpha)
     break;
  }
  return bestValue;
  
} 
else if( max == false)
{
  let moves = chess.moves();
  let bestValue = Infinity;
  for(let i = 0; i < moves.length; i++)
  {
    chess.load(fen);
    chess.move(moves[i]);
    let value = this.minimax(chess.fen(),depth-1, alpha, beta, true);
    bestValue = Math.min(value,bestValue);
    beta = Math.min(beta, bestValue);
    if(beta <= alpha)
    break;
  }
  return bestValue;

}




}




leafNode(fen)
{
let chess = new Chess();
 chess.load(fen);

 if(chess.in_checkmate() || chess.in_stalemate() || chess.in_threefold_repetition() )
    return true;
  else
    return false;
  
}

evaluation(fen) {
 let pieceValues = this.pieceValues();
  let score = 0;
  const boardState = fen.split(' ')[0];
  const rows = boardState.split('/');
  for (let i = 0; i < rows.length; i++) {
    let columnIndex = 0;
    const row = rows[i];
    for (let j = 0; j < row.length; j++) {
      const currentChar = row[j];
      if (currentChar in pieceValues) {
        score += pieceValues[currentChar];
      } else {
        columnIndex += parseInt(currentChar);
      }
    }
  }
  return score;
}

pieceValues()
{let black = {
  'p': -10,
  'n': -30,
  'b': -30,
  'r': -50,
  'q': -90,
  'P': 10,
  'N': 30,
  'B': 30,
  'R': 50,
  'Q': 90
};

let white = {
  'p': -10,
  'n': -30,
  'b': -30,
  'r': -50,
  'q': -90,
  'P': 10,
  'N': 30,
  'B': 30,
  'R': 50,
  'Q': 90
};
return this.color == 'b' ? black:white;
}

}

我知道我没有正确实现 minimax 函数，因为它总是选择我提供的移动数组中的第一步。

有人知道我做错了什么吗？

这里是存储库的链接：

https://github.com/jakmo3000/chessAI

Answer 1

您的代码的主要问题是，在调用

fen

函数内的

minimax()

函数时，您正在使用初始棋盘位置

move()

进行所有移动。相反，您应该在每次移动后使用新的棋盘位置。

修改你的

move()

函数如下：

move() {
    let maxIndex = 0;
    let maxScore = -Infinity;
    let moves = this.chess.moves();
    let fen = this.chess.fen();
    for (let i = 0; i < moves.length; i++) {
      let chess = new Chess();
      chess.load(fen);
      chess.move(moves[i]);
      let newFen = chess.fen(); // Get the new FEN after the move
      let score = this.minimax(newFen, this.depthLimit, -Infinity, Infinity, true);
      if (maxScore < score) {
        maxScore = score;
        maxIndex = i;
      }
      console.log(score);
    }
    return moves[maxIndex];
  }

通过此更改，您的机器人现在应该能够根据 minimax 算法做出更好的决策。您可以通过实施更复杂的评估函数来进一步提高机器人的性能，该函数会考虑棋子的位置和影响游戏的其他因素。目前的评价函数只考虑棋盘上棋子的物质价值。高级评估功能可能包括以下因素：

1. Piece-Square tables：这些表格为每个棋子的棋盘上的每个方格分配一个分数。这使您的机器人可以更好地了解棋子的最佳放置位置，从而做出更好的动作。
2. 机动性：考虑每件棋子可用的合法移动次数。这可以帮助识别具有更多可能性和潜在威胁的职位。
3. King safety：添加代表King safety的分数，考虑到与敌方棋子的距离，pawn结构和casting status等因素。
4. 兵结构：为连接的兵、孤立的兵和双兵添加分数，因为这些会对游戏产生重大影响。

此外，当您有更多可用时间时，请考虑使用迭代加深在游戏树中进行更深入的搜索。该技术涉及逐渐增加深度限制并重新搜索游戏树。它允许机器人在必要时快速采取行动，但也利用额外的时间进行更深入的搜索并找到更好的行动。