TicTacToe — Unbeatable Minimax Algorithm

If you want to implement the minimax algorithm, it will bust your balls…

Step 1: Don’t think about the minimax algorithm! (Whattt?)

Before implementing minimax for the AI move, build the game. I made it with the AI choosing a completely random move from the available squares. As you can imagine, not very difficult to beat… but effective for putting together all the styles and other logic. At this point, you might also be content and happy to leave out the algorithm. But this just didn’t feel right for me.

After hours/days of frustration implementing (trying to) minimax I felt defeated. I couldn’t work out what was wrong and I ended up scrapping all my Javascript code and starting again. This turned out to be a great idea.

I recommend you set up the game-board to a point where it’s close to completion and there’s only a few possible moves— this makes testing much easier. Pass this game-board into the minimax algorithm and ensure this works before proceeding. Once done you can go back and add everything else back in (or rewrite and make improvements).

Minimax is a recursive function . Recursive functions continually call themselves until a value is returned to the original function call. In this case the best move is returned. If you need further explanation on recursion here is a great video by CS50.

In basic terms, what happens in this algorithm is:

1. You pass the current state of the game-board when it’s the AI’s turn to the function.
2. It will look to see if the game-board is in a winning state (useless in the initial function call but essential for recursive function calls).
3. Find all the empty squares and save in a variable — so that all possible moves are known.
4. Create a blank array to save the results of all possible moves. — Each possible move will be an object in this array, including the moves index (0–8) on game-board and the resultant score (win/lose/draw).
5. Loop over each possible move.

— Create a move object to save the index and score — later pushed to moves array (above).

— Save index to move object.

— Place either x/o in possible move square.

— Find the score of this move (this is where the magic happens):

• Minimax function called on this new board — has x/o added to the possible move square.
• The current function will pause it’s execution waiting for a return value from this new function call. Once returned, the score from this move will be saved in the move object.
• This will keep happening on each successive function call until a win/draw/loss game-board is found and a value will be returned.
• It might be easier to picture from the end and work back. Each level of the function call before the value is returned will end up an array of varying values. From this, the best move will be selected. Example:

moves[
{index: 0, score: 10},
{index: 4, score: -10},
{index: 9, score: 0}
]

• Once the loop has ended and has an array of all possible moves scores/indexes it will proceed to the next section.

6. Create a variable for the best move.

7. Loop over each move in the moves array to find the best move.

• You will be looking for the highest score if it’s the AI’s turn or lowest if humans turn (you are also simulating human turns and assuming they will make the best move each time).
• Once the best move is found this is returned and that function is ended.

8. If you are back to the original function call this value will be passed back to your AI move call and you will use the index from your move object for the AI to make the best possible move. If it is one of the recursive calls, the score of this result will be saved into the move object with the move index and used to calculate the best move.

Here’s the resources which saved my life on this algorithm. P.S. If you can see mine ends up being very similar to these it’s not because I was copying and pasting (don’t!) it’s because I had to read/watch the explanation and code about 100 times to understand it.

This is a great article by someone else who tackled this algorithm and provides a great write-up and examples.

This video is based off the above article and really helps understanding by watching somebody type out the code (skip to 39.25 for minimax).

Another life-saving tool for me was the Debugger for Chrome in VSCode (if you’re using another editor or browser I’m sure they have their own version). This will let you set breakpoints in your Javascript code and step through each line of code to see exactly what is happening.This is invaluable for seeing exactly what happens and is also why I recommend starting from a nearly finished board (you will have hundreds less function calls to sift through and follow what is happening).

Here is my final code.

miniMax = (board, player) => {
 // find squares that are blank
 const availableSquares = board.filter(s => s !== "x" && s !== "o");
 // check for winning move or draw
 if (checkWin(aiPlayer, board)) return { score: 10 };
 if (checkWin(huPlayer, board)) return { score: -10 };
 if (checkDraw(board)) return { score: 0 };
 // save all the possible moves from current board in an array
 let moves = [];
 // loop over available moves
 for (let i = 0; i < availableSquares.length; i++) {
  // save each possible moves data in an object
  let move = {};
  // save the squares location (index in array
  move.index = board[availableSquares[i]];
  // fill in square with current player
  board[availableSquares[i]] = player;
  // find score of move
  if (player === aiPlayer) {
   const result = miniMax(board, huPlayer);
   move.score = result.score;
  }
  if (player === huPlayer) {
   const result = miniMax(board, aiPlayer);
   move.score = result.score;
  } 
  // reset board to original
  board[availableSquares[i]] = move.index;
  // save results of this move to array
  moves.push(move);
 }
 // to save bestMove in
 let bestMove;
 // if player is ai - bestScore is set to -100 - else if human 100
 let bestScore = player === aiPlayer ? -100 : 100;
 // find best move from possible moves
 moves.forEach(move => {
  if (player === aiPlayer) {
   if (move.score > bestScore) {
    bestScore = move.score;
    bestMove = move;
   }
 } else {
   if (move.score < bestScore) {
    bestScore = move.score;
    bestMove = move;
   }
  }
 });
 return bestMove;
};

Hope you’ve found this helpful and you’ll be able to implement it yourself as well. Here is the final live version you can play/test and the final code that includes everything on GitHub.