Explain Chess Engine Iterative Deepening

A fixed-depth search either finishes or it doesn't — if the clock runs out at depth 7, you have nothing. Iterative deepening searches depth 1, then restarts at depth 2, then 3, and so on, always keeping the last fully-completed result ready to play. It looks wasteful — re-searching shallow depths every time — but it's the backbone of every UCI engine, because the shallow passes are almost free and they make the deep pass dramatically faster.

The problem

What If You Just Searched to Depth N?

⛔ Fixed-depth jump

Search straight to depth 8. No principal variation exists yet, so moves are tried in arbitrary order — alpha-beta prunes far less. Worse: if time runs out before depth 8 finishes, there is no complete result to report at all.

✅ Iterative deepening

Depth 1 finishes almost instantly and produces a principal variation (PV). Depth 2 reuses that PV to try the best move first, so alpha-beta cuts harder. Every completed depth leaves a ready-to-play best move — an anytime algorithm.

Visual

The Deepening Loop

d=1

instant · seeds PV

→

d=2

PV reorders moves

→

d=3

TT mostly warm

→

d=4

searching…

→

⏱

time up — stop

The engine reports depth 3's move immediately — depth 4 was still running when the clock ran out, so its incomplete result is discarded, never reported.

AnytimeA legal best move exists after every depth

PV reuseLast depth's line orders the next depth's moves

TT warmTransposition table fills in during shallow passes

~1 plyRough cost of all shallower passes combined

Why it's (almost) free

The Branching-Factor Paradox

Search trees grow exponentially with depth, so the deepest pass dominates total node count. If the effective branching factor is b, the nodes searched across all depths 1…N sum to a geometric series that converges to about b/(b−1) times the cost of depth N alone — re-doing every shallow depth barely moves the total.

Depth	Nodes at this depth (b=3, illustrative)	Running total
1	`3`	`3`
2	`9`	`12`
3	`27`	`39`
4	`81`	`120`
5	`243`	`363`
6	`729`	`1,092` (≈1.5× depth 6 alone)

With b=3, searching depths 1–6 costs 1,092 nodes total versus 729 for depth 6 alone — a 1.5× overhead (matching b/(b−1) = 3/2). In return, depth 6 starts with a move-ordered PV from depth 5, which usually saves far more than 50% of its own nodes through better alpha-beta cutoffs — a net win.

Mechanics

What Makes the Loop Work

Principal Variation Seeding

Each completed depth stores its best line (the PV) and fills the transposition table. The next depth probes the TT first, so the previous best move is tried before anything else — alpha-beta's pruning power depends entirely on trying good moves first.

TT move tried first at every node Killer/history heuristics also carry over

⏱

Time Management — Soft vs Hard Limits

A soft limit (e.g. target 3s for this move) is checked between iterations — if there's clearly no time left for another full depth, stop and play the last completed move. A hard limit (e.g. absolute 10s cap) is checked periodically inside the search via a node counter, so a single slow iteration can't blow the clock.

// checked every few thousand nodes, mid-search
if (nodeCount % 2048 == 0 && elapsed() > hardLimit) {
  stopRequested = true; // unwind recursion, discard this depth
}

↺

Search Instability & Fail-Lows

Going one ply deeper occasionally reveals that last depth's "best" move was actually a mistake — the score can drop or the PV can change between iterations. Combined with aspiration windows (a narrow [α, β] guess around last depth's score), a fail-low/fail-high triggers a same-depth re-search with a wider window before moving on.

See: Aspiration Windows deep dive

{ }

The Driver Loop

A thin loop around the search function — depth increases by one each pass, and the loop owns the only copy of "best move reported so far."

// outermost driver — runs in its own thread
Move bestMove;
for (depth = 1; depth <= maxDepth; depth++) {
  if (stopRequested) break;
  score = negamax(depth, -INF, +INF);
  if (stopRequested && depth > 1) break; // discard partial depth
  bestMove = pv[0];
  reportInfo(depth, score, pv);
}
return bestMove;

∞

When There's No Clock

Iterative deepening isn't just for time control. go depth N and go infinite (analysis mode, stopped only by a stop command) both still deepen one ply at a time — the GUI streams a new, improving PV after every depth so the user sees the engine's thinking evolve live.

Output

What the GUI Sees, Depth by Depth

UCI info lines arrive once per completed depth

Each line is a complete, valid result on its own — the GUI always has a usable bestmove if it must stop the engine right now.

info depth 1 score cp 18 nodes 24 nps 12000 pv e2e4
info depth 2 score cp 22 nodes 312 nps 156000 pv e2e4 e7e5
info depth 3 score cp 31 nodes 4108 nps 890000 pv e2e4 e7e5 g1f3
info depth 4 score cp 28 nodes 51200 nps 3100000 pv e2e4 e7e5 g1f3 b8c6
bestmove e2e4 ponder e7e5

Reference

Fixed-Depth vs Iterative Deepening

Property	Fixed-depth search	Iterative deepening
If time runs out mid-search	No result at all	Last completed depth's move is ready
Move ordering	None — first attempt is unordered	Seeded by previous depth's PV / TT
Transposition table	Cold	Warmed by every prior shallow pass
Total extra node cost	—	~`b/(b−1)`× one depth (small)
Works with "infinite analysis"	No	Yes — just keeps deepening

Build it after move ordering exists

Iterative deepening only pays off once move ordering and a transposition table exist to carry information between depths — wire it in after negamax/alpha-beta works correctly, not before. Verify with a fixed node or depth limit first, then add the timer.

Get negamax + alpha-beta correct at a single fixed depth first
Add a transposition table so depth N can probe depth N−1's results
Wrap the search in the depth-increasing driver loop
Add soft/hard time checks last, once correctness is verified

Continue the engine series

Iterative deepening ties search to the clock — see how the rest of the search stack fits together.

Search Algorithm Aspiration Windows Transposition Table

Related: Search Algorithm · UCI Protocol · Engine Anatomy · All Blogs