Alpha-Beta 剪枝极小极大算法无法在 Tic-Tac-Toe AI 中提供正确的最佳移动

Question

我正在使用 Alpha-Beta 剪枝 Minimax 算法开发 Tic-Tac-Toe AI 实现。目标是在给定的棋盘上找到 AI 玩家 (X) 的最佳走法。但是，我遇到了一个问题，算法没有返回正确的最佳移动索引。

AI 玩家 (X) 的最佳移动应该是索引 4，但我的 minimax 函数返回 bestAIMove.index = 8。

这是我的代码：

let humanPlayer = "O";
let aiPlayer = "X";
let origBoard = ["X", "O", 2, "X", 4, 5, "O", 7, 8];
let MAX = {index: 99, score: 1000};
let MIN = {index: 99, score: -1000}
let fc = 0;

function checkAvailableMoves(board) {
    return board.filter(s => s !== "O" && s !== "X");
  }

function winning(board, player) {
    const winningCombinations = [
      [0, 1, 2],
      [3, 4, 5],
      [6, 7, 8],
      [0, 3, 6],
      [1, 4, 7],
      [2, 5, 8],
      [0, 4, 8],
      [2, 4, 6]
    ];
    return winningCombinations.some(combination =>
      combination.every(cell => board[cell] === player)
    );
  }

function max(a,b) {return a.score > b.score ? a : b;}
function min(a,b) {return a.score < b.score ? a : b;}

function minimax(newBoard, depth, player, alpha, beta) {
    const availableMoves = checkAvailableMoves(newBoard);
    let theBestMove = {};
    fc++
    if (winning(newBoard, humanPlayer)) {return { score: -10 + depth }}
    else if (winning(newBoard, aiPlayer)) {return { score: 10 - depth }}
    else if (availableMoves.length === 0) {return { score: 0 }};

    if (player === aiPlayer) {
      for (let i = 0; i < availableMoves.length; i++) {
        const index = availableMoves[i];
        newBoard[index] = player;
        let result = minimax(newBoard, depth + 1, humanPlayer, alpha, beta);
        result.index = index;
        alpha = max(alpha,result)
        newBoard[index] = index;
        if (alpha.score >= beta.score) {break}
      }
      theBestMove = alpha;
    } else if (player === humanPlayer) {
      for (let i = 0; i < availableMoves.length; i++) {
        const index = availableMoves[i];
        newBoard[index] = player;
        let result = minimax(newBoard, depth + 1, aiPlayer, alpha, beta);
        result.index = index;
        beta = min(beta, result);
        newBoard[index] = index;
        if (alpha.score >= beta.score){break}
      }
      theBestMove = beta;
    }
    return theBestMove;
  }

  bestAIMove = minimax(origBoard,0,aiPlayer,MIN,MAX)
  console.log(bestAIMove)
  console.log(fc)

我已经检查了我的代码并尝试调试它，但我似乎无法识别问题。有人可以帮助我了解可能导致问题的原因吗？

Answer 1

您的代码中有两个相关问题：

当分数相等时，

1. min

   和

   max

   函数将选择

   b

   。但是当您使用

   min

   作为第二个参数来调用

   max

   和

   result

   时，这始终会优先考虑较新的分数。由于 alpha beta 修剪，您可能会得到 相同 分数，因此您应该优先考虑“设置标准”的移动，即

   alpha

   或

   beta

   。因此，要么交换传递给

   min

   和

   max

   的参数，要么更改这些函数，以便在分数相同的情况下它们选择

   a

   。

2. result.index = index

   变异 一个可能是

   alpha

   或

   beta

   的对象。你不希望这种事发生。将这些对象视为不可变的。所以改为

   result = {...result, index}

通过这两个修复，它就可以工作了。