Tic Tac Toe AI with a Depth-First Search
This is my first post, so please don’t be too rough or judge too harshly.
This can be used to solve a game, to find the best possible move or simply who wins given ideal gameplay. This form of game AI is amongst the easiest to implement, since it doesn’t require the construction of a tree. Since this algorithm works bottom up without rechecking any nodes, it is typically using a recursive function and a function that checks if the game is over.
For the game of Tic Tac Toe, consider the following method:
This recursive method does the following:
- Check if the game is over—if either player won or if the board is fully filled
- If so, return the result of the game
- Iterate through all board squares
- If the square is occupied, continue to the next one
- Set the square to either an ‘X’ or an ‘O’ depending on the current player’s color
- Get the outcome of the game by recursing, calling the same method with the updated board, and with the turn boolean swapped
- Update the best result of this branch, trying to maximize the result for the current player
In short, it finds the results by assuming that both players will play moves that maximize their game. Note that it is very simple to change this algorithm to play Misère or Anti Tic Tac Toe, a game played like Tic Tac Toe except that the goal of the game is to lose.
Since this solution is written for simplicity, it can take nearly half a second to run on Tic Tac Toe, although it can relatively easily be implemented to run in less than a hundredth of a second (see Kesav Viswanadha’s implementation). Of course for larger games such as Connect Four and Gomoku (connect five), it will take much, much longer. This is because the fact that the complexity of depth-first search is O(bd), where b is the branching factor (average number of possible moves in any given board position) and d is the average depth or moves played in a game before it is over.
If the time it takes to run on Tic Tac Toe is 1, then the relative runtimes for different games would roughly be:
- Connect Four: 1.80 * 1016
- Othello (Reversi): 3.81 * 1052
- Gomoku: 1.77 * 1064
- Chess: 1.28 * 10118
- Go (Weiqi): 1.87 * 10354
To put it into comparison, if you were to move one hair-length, solve Tic Tac Toe completely, then move another hair-length and repeat, while someone else was trying to solve Connect Four, the other person would be done when you move the distance from Earth to the Moon one thousand times! In other words, you aren’t going to get far trying to solve Connect Four, nor any other complex game, using pure depth-first search.
The moral of the story is: while depth-first search can be used to solve Tic Tac Toe, it ultimately fails for more complex games—I doubt your Connect Four player would want to wait years for the computer to think. That’s why AI’s use algorithms such as minimax and Monte Carlo tree search to find good moves. While the moves they find are often not perfect, they can still be very good and, more importantly, be evaluated in just a few seconds.
If you want to check out my Connect Four AI (which boasts as much stronger than any other AI you’ll find online), be sure to check it out.
A complete Tic Tac Toe depth-first search AI sample can be found here!
If you have any questions, advice, or feedback at all, feel free to leave a comment down below!