If you read my last post and checked out my Tic Tac Toe game, then your were probably less than impressed that you were pretty much playing the game by yourself. I decided to implement an AI for the game so it’d be a bit more fun.

Tic-Tac-Toe is a much more interesting game than it first appears, at least from the AI and computing perspective. According to the Wikipedia article on Tic-Tac-Toe, there are 26,830 possible boards after removing all of the reflections and rotations which produce duplicates. That number is staggering when you consider that most adults can play the optimal game of tic-tac-toe without even thinking about it.

The game is also very interesting because the best case scenario when two optimal players compete is a draw, this makes testing of the algorithm pretty easy as the AI player should only win if the player makes a move that creates an opening for the AI by playing sub-optimally.

## Enter the MiniMax Algorithm

The MiniMax(MM) algorithm is a recursive tree based algorithm to evaluate all of the possible moves available. Each possible move for the AI player is evaluated in turn. Each terminal node in the tree is assigned a value. One player attempting to maximize this value and the opposing player attempting to minimize this value. The AI will evaluate the optimal play one turn at a time, starting with itself and alternating between optimal plays for each player until an end node is achieved and a point value assigned.

There are 3 outcomes of a game of Tic-Tac-Toe (Leafs or End Nodes)

1. X wins 10 points (Player)
2. O wins -10 points (AI)
3. Game ends in a draw 0 points

For my implementation, the Human player is treated as the maximizing player and the AI is the minimizing player. Evaluation of the board starts with the minimizing player (the computer). The computer player considers all plays with an equivalent score to be equal and therefore just picks the first move that would produce that score, even if there are multiple moves that would produce the same result.

As each possible board state is evaluated by the AI, if it is an end node it is assigned a point value and if it is not an end node the algorithm re-calls the function to evaluate all of the possible resulting board states but from the perspective of the Human player and therefore attempts to make a move that would maximize the resulting score rather than minimize it. This pattern repeats until an end node is reached and the scores propagate back up to the top level for loop which picks the node with the lowest possible value.

Code is provided below. Testing against the AI there were some things that stand out. The AI behavior sometimes appears to be a bit odd. It is only when you recall that the AI plays to tie and also to take advantage of a player who does not play the optimal game that the play makes sense. It is also important to remember that when two plays would result in the same outcome, the AI simply takes the first option it finds. A simple improvement might be to store all moves equivalent to the best in an array and then select from them randomly.

The next step in the project will be to take the code below and integrate an AI in our React project. Look for that project here soon or on my YouTube Channel.