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
There are 3 outcomes of a game of Tic-Tac-Toe (Leafs or End Nodes)
X wins 10 points (Player)
O wins -10 points (AI)
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
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.