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

Iterative Deepening in Games

Progressively searching deeper until time runs out, combining benefits of depth-first and breadth-first approaches.

Iterative Deepening in Games

What you'll learn: How game-playing agents can search smarter by gradually increasing search depth until time runs out, blending the memory efficiency of depth-first search with the optimality guarantees of breadth-first approaches.

The Core Idea

In real-world games like chess or Go, you can't search the entire game tree—it's astronomically large. You also face strict time constraints: you must move within seconds or minutes. Iterative deepening solves this by running depth-limited minimax searches repeatedly, increasing the depth limit each iteration (depth 1, then 2, then 3...) until time expires.

When the clock runs out, you simply use the best move from the deepest completed search. This ensures you always have a valid move ready.

Why This Works So Well

You might think searching depth 1, then depth 2, then depth 3 wastes effort by re-exploring shallow nodes. Surprisingly, the overhead is negligible—typically only about 50% extra work—because game trees grow exponentially. The deepest level dominates all previous levels combined.

Benefits you get:

  • Anytime algorithm: You have a best move at every moment
  • Better move ordering: Earlier shallow searches inform alpha-beta pruning in deeper searches, making pruning more effective
  • Memory efficient: Only stores one depth level at a time, like DFS
  • Adaptive: Automatically uses available time optimally

In Practice

Combine iterative deepening with alpha-beta pruning and good evaluation functions. Store the best moves from shallower searches in a transposition table to improve move ordering for deeper iterations—creating a powerful positive feedback loop.

Key Takeaway: Iterative deepening transforms game search from "how deep can I go?" into "how deep can I go in the time available?"—a practical, elegant solution that wastes little computation while guaranteeing you're never caught without a move.