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.
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.
tree_size() function using
"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
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 column
"X" has taken their turn, it is now
"O"‘s turn. Change the second parameter in the
tree_size() function to be