Minimax Algorithm

Minimax is a kind of backtracking algorithm used in decision-making game theory. It calculates the optimal move, assuming that the opponent plays optimally. Using this algorithm, I built simple tictactoe AI.

demo

There are two players in the minimax: Maximizing Player and Minimizing Player. The maximizing Player is the player who wants to win, and the minimizing player is the player who needs to lose, which is the opponent. In this game, AI is the maximizing player and the human player is the minimizing player.

There are 3 final state in TicTacToe: Win, Tie, or Lose. This can be represented as scores. +1 for win, 0 for tie, and -1 for lose. To calculate the optimal move for the AI to make, you want to choose the move that results in the highest score for the AI and the lowest score for the human player. Refer to the diagram below.

minimax-diagram

For X's turn which is the minimizing player, you want to pick a move with the lowest score which sets the parent node's score to -1. For O's turn, you want to pick a move with the highest score, which is +1. Calculating the scores for all possible moves on every turn and maximizing or minimizing accordingly will result in the best move possible.

CalculateWinner

First of all, let's implement a function that checks for the winner. If maximizing player wins, which is 'O', the function returns +1. If minimizing player wins, returns -1. For tie, let's return 0, and if the game is not finished, return null.

/**
 * 'O' wins : 1 // AI
 * 'X' wins : -1 // human player
 *  tie : 0
 *  null : if there is no winner
 */
function calculateWinner(squares) {
  //all possible wins
  const lines = [
    [0, 1, 2],
    [3, 4, 5],
    [6, 7, 8],
    [0, 3, 6],
    [1, 4, 7],
    [2, 5, 8],
    [0, 4, 8],
    [2, 4, 6],
  ];

  // check for all possible wins
  for (let i=0; i < lines.length; i++) {
    const [a, b, c] = lines[i];
    if (squares[a] && squares[a] === squares[b] && squares[a] === squares[c]) {
      return squares[a] === 'X' ? -1 : 1;
    }
  }

  //check for tie
  let availableSpot = 0;
  for(let i=0; i < squares.length; i++) {
    if(!squares[i])
      availableSpot++;
  }
  return availableSpot === 0 ? 0 : null; // return null if game is not finished
}

Minimax

Now, let's implement the minimax algorithm. I set the function to return the best score and the index of the best scoring move.

/**
 * squares is one-dimensional array with a size of 3*3.
 * each square contains either 'O', 'X', or null.
 * 
 * returns bestScore and index of the move as an array
 * 0 : bestScore
 * 1 : index
 */
function minimax(squares, depth, isMaxizing) {
  let result = calculateWinner(squares); // basecase
  if(result !== null) {
    return [result, null];
  }

  if(isMaxizing) {
    let maxI;
    let maxScore = -Infinity;
    for (let i=0; i<squares.length; i++) {
      if (!squares[i]) { // find empty square
        squares[i] = AI; // AI = 'O';
        let score = minimax(squares, depth+1, false)[0]; // recursive call
        squares[i] = null;  // undo the move

        if (score > maxScore) {
          maxScore = score;
          maxI = i;
        }
      }
    }
    return [maxScore, maxI];
  } else {
    let minI;
    let minScore = Infinity;
    for (let i=0; i<squares.length; i++) {
      if (!squares[i]) { // find empty square
        squares[i] = PLAYER; // PLAYER = 'X'
        let score = minimax(squares, depth+1, true)[0]; // recursive call
        squares[i] = null; // undo the move

        if (score < minScore) {
          minScore = score;
          minI = i;
        }
      }
    }
    return [minScore, minI];
  }
}

For entire code, refer to my github repo: here
Game demo: here

References

– Minimax Algorithm in Game Theory
– Algorithm Explained - minimax and alpha-beta pruning
– Tic Tac Toe AI with Minimax Algorithm

CalculateWinner

Minimax

More

References