Nice work! You implemented the minimax algorithm to create an unbeatable Tic Tac Toe AI! Here are some major takeaways from this lesson.
- A game can be represented as a tree. The current state of the game is the root of the tree, and each potential move is a child of that node. The leaves of the tree are game states where the game has ended (either in a win or a tie).
- The minimax algorithm returns the best possible move for a given game state. It assumes that your opponent will also be using the minimax algorithm to determine their best move.
- Game states can be evaluated and given a specific score. This is relatively easy when the game is over — the score is usually a
1,-1depending on who won. If the game is a tie, the score is usually a0.
In our next lesson on the minimax algorithm, we’ll look at games that are more complex than Tic Tac Toe. How does the algorithm change if it’s too computationally intensive to reach the leaves of the game tree? What strategies can we use to traverse the tree in a smarter way? We’ll tackle these questions in our next lesson!
Instructions
Take a look at our Connect Four AI for a sneak preview of our next minimax lesson. In the terminal type python3 minimax.py to play against the AI.
You can make your move by typing the number of the column that you want to put your piece in.
In the code, you can change the “intelligence” of the AI by changing the parameter of play_game(). The parameter should be a number greater than 0. If you make it greater than 6 or 7, it will take the computer a long time to find their best move.
Make sure to click the Run button to save your code before running your file in the terminal!
You can also set up an AI vs AI game by commenting out play_game() and calling two_ai_game(). This function takes two parameters — the “intelligence” of each AI players. Try starting a game with a bad X player and a smart O player by calling two_ai_game(2, 6) and see what happens.
Feel free to test out more games with different AIs.