Cannot get minimax function to work for tic tac toe game

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]);
}

I followed https://www.geeksforgeeks.org/minimax-algorithm-in-game-theory-set-3-tic-tac-toe-ai-finding-optimal-move/ for direction, and as far as I can see, the logic is the same.

Still, my code doesn't come up with the correct moves. The evaluation my minimiax function gives to each move is wrong. And it is sooo wrong I cannot even begin to figure out where the code is off. Please help. I've spent the last two weeks working on this.

Ex:

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

This isn't the easist code to read, but AFAICT the minimax function copies the game board state once and then loops through possible moves with availableMoves.forEach. This means that when evaluating each possible move, it acts as if each previously considered move had been made. Move the copy inside the forEach and things should make somewhat more sense.

You already have this in the findBestMove function. I'd strongly suggest unifying findBestMove and minimax (and the sides of the isMaximizingPlayer branch inside minimax). Having very similar code in multiple places makes it hard to remember where you have and haven't fixed things.

I'd also suggest replacing the isMaximizingPlayer and depth%2 logic with a player variable that can be either "x" or "o", and multiplying goodness scores by -1 as needed. It'll be easier to keep track of.