The first strategy we’ll use to handle these enormous trees is stopping the recursion early. There’s no need to go all the way to the leaves! We’ll just look a few moves ahead.
Being able to stop before reaching the leaves is critically important for the efficiency of this algorithm. It could take literal days to reach the leaves of a game of chess. Stopping after only a few levels limits the algorithm’s understanding of the game, but it makes the runtime realistic.
In order to implement this, we’ll add another parameter to our function called depth
. Every time we make a recursive call, we’ll decrease depth by 1
like so:
def minimax(input_board, minimizing_player, depth): # Base Case if game_is over(input_bopard): return ... else: # … # Recursive Call hypothetical_value = minimax(new_board, True, depth - 1)[0]
We’ll also have to edit our base case condition. We now want to stop if the game is over (we’ve hit a leaf), or if depth
is 0
.
Instructions
We’ve given you a minimax()
function that recurses to the leaves. Edit it so it has a third parameter named depth
.
Change the recursive call to decrease depth
by 1
each time.
Change your base case — the recursion should stop when the game is over or when depth
is 0
.
Outside the function, call minimax()
on new_board
as the maximizing player with a depth of 3
and print the results. Remember, minimax()
returns a list of two numbers. The first is the value of the best possible move, and the second is the move itself.