Learn

Advanced Minimax

Depth and Base Case

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.

Sign up to start coding

Or sign up using:

Already have an account?