'Minimax Algorithm - Tic Tac Toe AI not selecting best move

I've been working on writing a minimax algorithm for my tictactoe game, but it doesn't seem to be choosing the correct move. It is possible to win against the computer, so I must have something mixed up here.

I based my algorithm off this article (I had to alter my minimax code since my code was different from the example in the article)

// Checking if there are any moves remaining on the board. Returns false if there are no moves left to play
  const isMovesLeft = function () {
    if (gameBoard._moves === 9) {
      return false;
    } else {
      return true;
    }
  };

  // Evaluates if the maximiser or minimiser has won or draw - returns a number if there is a win or draw
  const evaluate = function () {
    if (gameBoard._roundWon && gameBoard._currentPlayer === gameBoard._player1)
      return +10;
    if (gameBoard._roundWon && gameBoard._currentPlayer === gameBoard._player2)
      return -10;
    if (gameBoard._roundTie) return 0;
  };

  // Minimax function - considers all the possible ways the game can go and returns the value of the board
  const minimax = function (board, depth, isMax) {
    let score = evaluate();

    // If maximiser has won the game - return evaluated score
    if (score === 10) return score;

    // If minimiser has won the game - return evaluated score
    if (score === -10) return score;

    // If there are no moves left and there is no winner - then return as a tie
    if (isMovesLeft() === false) return 0;

    // If it is the maximiser's turn
    if (isMax) {
      let bestScore = -1000;
      let availableTiles = [];
      // Looping through all tiles
      tile.forEach((tile, index) => {
        // Check if cell is empty
        if (tile.textContent === '') {
          availableTiles.push(index);
        }
      });

      // Make the move
      const chosenEmptyTile =
        availableTiles[Math.floor(Math.random() * availableTiles.length)];
      renderAITile(tile, chosenEmptyTile);
      addPlayerMoves(chosenEmptyTile);

      // Calling minimax recursively and choose the maximum value
      bestScore = Math.max(bestScore, minimax(board, depth + 1, false));
      console.log(bestScore);

      // Undo the move
      undoAIMove(tile, chosenEmptyTile);
      return bestScore;
    } else {
      let bestScore = 1000;
      let availableTiles = [];

      // Looping through all tiles
      tile.forEach((tile, index) => {
        // Check if cell is empty
        if (tile.textContent === '') {
          availableTiles.push(index);
        }
      });

      // Make the move
      const chosenEmptyTile =
        availableTiles[Math.floor(Math.random() * availableTiles.length)];
      renderAITile(tile, chosenEmptyTile);
      addPlayerMoves(chosenEmptyTile);

      // Calling minimax recursively and choose the maximum value
      bestScore = Math.min(bestScore, minimax(board, depth + 1, false));

      // Undo the move
      undoAIMove(tile, chosenEmptyTile);
      return bestScore;
    }
  };

  const undoAIMove = function (tile, chosenEmptyTile) {
    tile[chosenEmptyTile].textContent = '';
    tile[chosenEmptyTile].classList.remove(`playerX`);
    tile[chosenEmptyTile].classList.remove(`playerO`);
    gameBoard._board[chosenEmptyTile] = '';
    gameBoard._moves -= 1;
  };

  // Return the best possible move for the AI
  const findBestMove = function (board) {
    let bestVal = -1000;
    let bestMove = [];
    let availableTiles = [];

    // Traverse all cells, evaluate minimax function for all empty cells. And return the cell with optimal value.
    tile.forEach((tile, index) => {
      if (tile.textContent === '') {
        availableTiles.push(index);
      }
    });

    // Make the move
    console.log(`Empty Tile: ${availableTiles}`);
    const chosenEmptyTile =
      availableTiles[Math.floor(Math.random() * availableTiles.length)];
    console.log(`Chosen tile: ${chosenEmptyTile}`);
    renderAITile(tile, chosenEmptyTile);
    addPlayerMoves(chosenEmptyTile);
    console.log(gameBoard._board);

    // Compute evaluation function for this move
    let moveVal = minimax(board, 0, false);

    // Undo the move
    undoAIMove(tile, chosenEmptyTile);

    // If value of the current move is more than the best value, then update best
    if (moveVal > bestVal) {
      bestVal = moveVal;
      bestMove.push(chosenEmptyTile);
      gameBoard._board[chosenEmptyTile] = 'X';
      renderAITile(tile, bestMove);
    }
    return bestMove;
  };

  const startGameAI = function () {
    if (gameBoard._aiTurn && gameBoard._opponent === 'AI') {
      // Finding best move
      findBestMove(gameBoard._board);

      // Store AI moves in data
      addPlayerMoves();
      console.log(gameBoard._moves);

      // Check if game over or tie
      checkGameOver();

      // Switch players
      switchPlayers();

      renderScoreBoard();
    }
  };

  // Renders the tile AI selects
  const renderAITile = function (tile, randomEmptyTileIndex) {
    if (gameBoard._roundWon || gameBoard._roundTie || !gameBoard._isGameActive)
      return;

    if (gameBoard._aiTurn) {
      tile[randomEmptyTileIndex].textContent = 'X';
      tile[randomEmptyTileIndex].classList.add(
        `player${gameBoard._currentPlayer}`
      );
    }
  };

Full code on Codepen



Sources

This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.

Source: Stack Overflow

Solution Source