Course contentsShow
← Computer Science
Lesson 2771 of 2,87261. AI and Search AlgorithmsFree lesson

Depth-Limited Minimax

Applying fixed depth cutoffs with evaluation functions to make adversarial search tractable in deep games.

Depth-Limited Minimax

What you'll learn: How to make minimax practical for complex games by stopping early and estimating positions instead of searching to the end.


The Problem with Pure Minimax

In the ideal world, minimax explores game trees all the way to terminal states (wins, losses, draws). But in chess, there are roughly 10⁴⁰ possible board positions—searching that deeply is impossible within reasonable time limits.

Applying Fixed Depth Cutoffs

Depth-limited minimax solves this by setting a maximum search depth (say, 6 ply). When you hit that limit, instead of continuing, you:

  1. Stop the recursion early at that depth
  2. Call an evaluation function to estimate how favorable the position is
  3. Treat that estimate like a terminal utility value

Think of it like a chess coach who can't analyze every possible endgame but can look 6 moves ahead and say "this position looks +2 pawns better for White"—that's good enough to make strong moves.

How It Works

Instead of:

if state.is_terminal():
    return state.utility()

You do:

if state.is_terminal():
    return state.utility()
elif depth == 0:
    return evaluate(state)  # Heuristic estimate

The evaluation function (covered in the previous lesson) assigns numeric scores to non-terminal positions based on material count, piece positioning, king safety, etc.

The Tradeoff

Deeper searches yield more accurate decisions but take exponentially longer. Shallower searches are fast but rely heavily on evaluation function quality. Most game engines dynamically tune depth based on time constraints.

Key Takeaway: Depth-limited minimax makes adversarial search tractable by capping recursion depth and using evaluation functions to approximate the value of positions beyond the search horizon.