无法获得适用于井字游戏的 minimax 函数

Question

const grabEmptySquares = (array) => {
  var emptyGameSquares = [];
  for (i = 0; i < 9; i++) {
    if (!array[i]) emptyGameSquares.push(i);
  }
  return emptyGameSquares;
};

function findBestMove(board) {
  var bestMove = {
    index: null,
    evaluation: null,
  };
  var availableMoves = grabEmptySquares(board);
  availableMoves.forEach((move) => {
    const simulGameboard = JSON.parse(JSON.stringify(board));
    simulGameboard[move] = "o";
    const evaluation = minimax(simulGameboard, 1, false);
    const moveDetails = {
      index: move,
      evaluation: evaluation,
    };
    console.log(moveDetails)

    if (evaluation > bestMove.evaluation || bestMove.evaluation === null) {
      bestMove.index = move;
      bestMove.evaluation = evaluation;
    }
  });

  return bestMove.index;
}

function evaluate(board, isMaximizingPlayer, depth) {
  var gameStatus = isGameOver(board);
  if (gameStatus[0] != true) return;
  if (gameStatus[1] === "win")
    return isMaximizingPlayer ? +10 - depth : -10 + depth;
  if (gameStatus[1] === "tie") return 0;
}

function minimax(board, depth, isMaximizingPlayer) {
  var gameStatus = isGameOver(board);
  if (gameStatus[0] == true) {
    const evaluation = evaluate(board, !isMaximizingPlayer, depth);
    return evaluation;
  }

  var simulGameboard = JSON.parse(JSON.stringify(board));
  var availableMoves = grabEmptySquares(simulGameboard);

  if (isMaximizingPlayer) {
    bestVal = -Infinity;
    availableMoves.forEach((move) => {
      depth % 2 === 0
        ? (simulGameboard[move] = "o")
        : (simulGameboard[move] = "x");
      value = minimax(simulGameboard, depth + 1, false);
      bestVal = Math.max(bestVal, value);

      const moveDetails = {
        index: move,
        evaluation: bestVal,
        depth: depth,
      };
      console.log(moveDetails);
    });
    return bestVal;
  } else {
    bestVal = Infinity;
    availableMoves.forEach((move) => {
      depth % 2 === 0
        ? (simulGameboard[move] = "o")
        : (simulGameboard[move] = "x");

      value = minimax(simulGameboard, depth + 1, true);
      bestVal = Math.min(bestVal, value);

      const moveDetails = {
        index: move,
        evaluation: bestVal,
        depth: depth,
      };
      console.log(moveDetails);
    });
    return bestVal;
  }
}

function isGameOver(array) {
  var gameOver = false;
  if (
    (array[0] && array[0] === array[1] && array[0] === array[2]) ||
    (array[3] && array[3] === array[4] && array[3] === array[5]) ||
    (array[6] && array[6] === array[7] && array[6] === array[8])
  ) {
    return (gameOver = [true, "win"]);
  }
  if (
    (array[0] && array[0] === array[4] && array[0] === array[8]) ||
    (array[2] && array[2] === array[4] && array[2] === array[6])
  ) {
    return (gameOver = [true, "win"]);
  }
  if (
    (array[1] && array[1] === array[4] && array[4] === array[7]) ||
    (array[0] && array[0] === array[3] && array[3] === array[6]) ||
    (array[2] && array[2] === array[5] && array[5] === array[8])
  ) {
    return (gameOver = [true, "win"]);
  }
  if ([...array].every((index) => index)) {
    return (gameOver = [true, "tie"]);
  }
  return (gameOver = [false, null]);
}

我按照https://www.geeksforgeeks.org/minimax-algorithm-in-game-theory-set-3-tic-tac-toe-ai-finding-optimal-move/的方向，据我所知，逻辑是一样的。

我的代码仍然没有给出正确的动作。我的 minimiax 函数对每一步的评估是错误的。这是错误的，我什至无法开始弄清楚代码在哪里关闭。请帮忙。过去两周我一直在研究这个。

例如：

var gameboard = [ null, "o", null, "x", "x", null, null, null, null ]

If I run findBestMove(gameboard), the expected output should be

bestMove = {index: 5,
            evaluation: 0}

What I get instead is 

bestMove = {index: 1,
            evaluation: -8}.

In fact, every single move has the same evaluation.

Answer 1

这不是最容易阅读的代码，但 AFAICT minimax 函数将游戏板状态复制一次然后循环遍历可能的移动 availableMoves.forEach.这意味着在评估每个可能的着法时，它的行为就好像每个先前考虑的着法 已经做出 一样。将副本移动到 forEach 中，事情应该更有意义。

您在 findBestMove 函数中已经有了这个。我强烈建议统一 findBestMove 和 minimax（以及 minimax 内 isMaximizingPlayer 分支的两侧）。在多个地方使用非常相似的代码会让人很难记住你在哪里修复了哪些东西还没有修复。

我还建议将 isMaximizingPlayer 和 depth%2 逻辑替换为可以是“x”或“o”的 player 变量，并将优度分数乘以 - 1 根据需要。它会更容易跟踪。

无法获得适用于井字游戏的 minimax 函数

Cannot get minimax function to work for tic tac toe game

javascript

algorithm

tic-tac-toe

minimax