It is quite possible that after hundreds of tic-tac-toe games you wondered: what is the optimal algorithm? But if you are here, then you probably also tried to write an implementation of this game. We will go ahead and write a bot that will be impossible to beat at tic-tac-toe. Having predicted your question “why?”, We will answer: thanks to the “minimax” algorithm.
Like a professional chess player, this algorithm calculates the opponent’s actions several moves ahead – until it reaches the end of the game, be it a victory, a defeat or a draw. Once in this final state, the AI will award itself a positive number of points (in our case, +10) for a win, a negative (-10) for a defeat, and a neutral (0) for a draw.
At the same time, the algorithm performs similar calculations for the player’s moves. He will choose the move with the highest score if the AI is walking, and the move with the lowest score if the player is walking. Using this strategy minimax avoids defeat.
The minimax algorithm is most easily described as a recursive function that:
- returns a value if the final state is found (+10, 0, -10),
- goes through all empty cells on the field,
- calls the minimax function for each of them (recursion),
- evaluates the obtained values
- and returns the best of them.
If you are not familiar with recursion, then you should watch this lecture from the Harvard CS50 course:
To understand how the minimax works, let’s write its implementation and simulate its behavior. We will deal with this in the next two sections.
