In our first lesson on the minimax algorithm, we wrote a program that could play the perfect game of Tic-Tac-Toe. Our AI looked at all possible future moves and chose the one that would be most beneficial. This was a viable strategy because Tic Tac Toe is a small enough game that it wouldn’t take too long to reach the leaves of the game tree.
However, there are games, like Chess, that have much larger trees. There are 20 different options for the first move in Chess, compared to 9 in Tic-Tac-Toe. On top of that, the number of possible moves often increases as a chess game progresses. Traversing to the leaves of a Chess tree simply takes too much computational power.
In this lesson, we’ll investigate two techniques to solve this problem. The first technique puts a hard limit on how far down the tree you allow the algorithm to go. The second technique uses a clever trick called pruning to avoid exploring parts of the tree that we know will be useless.
Before we dive in, let’s look at the tree of a more complicated game — Connect Four!
If you’ve never played Connect Four before, the goal is to get a streak of four of your pieces in any direction — horizontally, vertically, or diagonally. You can place a piece by picking a column. The piece will fall to the lowest available row in that column.
Instructions
We’ve imported a Connect Four game engine along with a board that’s in the middle of a game.
To start, let’s call the print_board() function using half_done as a parameter.
Call the tree_size() function using half_done and "X" as parameters. Print the result. This will show you the number of game states in the tree, assuming half_done is the root of the tree and it is "X"‘s turn.
Let’s make a move and see how the size of the tree changes. Let’s place an "X" in column 6. Before calling the tree_size() function, call the select_space() function with the following three parameters:
half_done— The board that you’re making the move on.6— The column you’re selecting."X"— The type of piece you’re putting in column6.
Since "X" has taken their turn, it is now "O"‘s turn. Change the second parameter in the tree_size() function to be "O".