It is hard to imagine an Arduino with only 2k RAM capable of playing tic tac toe better then most of us. That is right, an unbeatable Tic Tac Toe player with a memory footprint of less than 2 kilobytes. In this tutorial we will implement a perfect Tic Tac Toe player which will never lose, it can only win or draw.
In such simple games, where the amount of possible moves are limited and respectively small, the minimax algorithm comes very handy. The minimax algorithm works best when the end of the game can be predicted. A board game such as tic tac toe is relatively simple with only 9 steps. So the decision tree off all possible moves needs to have a depth of only 9 levels. That said, the total permutations amount to 9! (Factorial) which is 362,880 although there are many games that end before the grid is filled up so that number is actually much less.
So, we at Runtime Projects decided to have a go with this by creating an invincible Tic Tac Toe player. The game will be outputted using the serial port so as not to complicate matters. However feel free to use this code to create your own version with LCDs or LEDs. We are not going into the details of implementing the algorithm here. This is pure C programming with a little thought about keeping a very small memory footprint. To make the game a little interesting, we have assigned a difficulty level for the AI to give us humans, a chance to win. The difficulty level is set from 1 to 8. 1 being the easiest and 8 being impossible. First the user is asked to state who is starting the game. Then, placing the X’s is simply entering the number of the box from 0 to 8.
Download the code from here