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)
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
We’ve given you a
minimax() function that recurses to the leaves. Edit it so it has a third parameter named
Change the recursive call to decrease
1 each time.
Change your base case — the recursion should stop when the game is over or when
Outside the function, call
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.