Home/Game AI/Iterative deepening
Search algorithmsCTRL K

Iterative deepening

· depth 1, then 2, then 3, until time runs out
/gameai/iterative-deepening
DEPTH LIMIT
1/ 3
plies of the current iteration
THIS PASS
0
nodes visited in the iteration
TOTAL
0
nodes over all iterations
ROOT VALUE
—
at the current depth
BEST MOVE
—
child chosen so far
currentevaluatedbest lineunvisited
b = 3 · depth 3 · seed 7 · 82 steps
step 0 / 81
Depth3
iterative_deepening.ts
1
function iterativeDeepening(root: Node, maxDepth: number, deadline: number) {
2
  let bestMove = root.children[0];
3
  for (let limit = 1; limit <= maxDepth && Date.now() < deadline; limit++) {
4
    bestMove = depthLimitedMinimax(root, limit).move!;
5
  }
6
  return bestMove;
7
}
8
function depthLimitedMinimax(node: Node, limit: number, maximizing = true): { value: number; move?: Node } {
9
  if (node.isLeaf) return { value: node.value };
10
  if (limit === 0) return { value: heuristic(node) };
11
  const scored = node.children.map((child) => ({ child, value: depthLimitedMinimax(child, limit - 1, !maximizing).value }));
12
  const best = scored.reduce((a, b) => (maximizing ? (b.value > a.value ? b : a) : (b.value < a.value ? b : a)));
13
  return { value: best.value, move: best.child };
14
}
CURRENT STEP
line 3

Iteration 1: search 1 ply deep. The move found so far stays valid if time runs out.

// how it works

Understanding Iterative deepening

iterative deepening · always have an answer ready, then improve it
01

The idea

A game engine never knows how deep it can afford to search before the clock runs out. Iterative deepening searches to depth 1, then again to depth 2, then 3, keeping the best move of the last completed iteration. Whenever time is up, an answer from a full search at some depth is ready.

It looks wasteful, but the tree grows geometrically with depth, so all the shallow passes together cost less than the last one alone. And the shallow passes are not wasted: their best moves are used to order the children of the next pass, which is what makes alpha-beta prune well. Every serious chess engine works this way.

02

The four stages

1
limitsearch only L plies deep
2
cut offat the limit, estimate with the static evaluation
3
keepthe best move of the completed pass
4
deepenL + 1, while there is time
03

Complexity

best
O(bᵈ)the last iteration dominates
average
O(bᵈ)shallow passes add a factor of b / (b − 1)
worst
O(bᵈ)the same as one full-depth search
space
O(d)depth-first at every iteration
04

Versus its siblings

NODES VISITED · b = 3, d = 4
minimax d = 4
121
iterative deepening to 4
160
alpha-beta d = 4
61
alpha-beta, ordered by id
33
the shallow passes cost a third extra and pay it back through move ordering
05

Pseudocode

ITERATIVEDEEPENING(root, maxDepth, deadline)
  for limit ← 1, 2, …, maxDepth while time remains
    bestMove ← DEPTHLIMITEDMINIMAX(root, limit)
  return bestMove
DEPTHLIMITEDMINIMAX(node, limit): a leaf returns its score; at limit 0 return the static evaluation; else minimax over the children with limit − 1
06

When to use

Any search under a time limit: chess, go, planning, where 'best move so far' must always be available.
Memory-limited search: iterative deepening depth-first search finds shortest solutions with BFS's optimality and DFS's memory.
07

Pitfalls

Without move ordering the repeated passes are pure overhead; the payoff comes from feeding each pass's results into the next.
A static evaluation at a violent position (mid-capture) lies; engines extend the search there (quiescence).
Interrupting mid-iteration must return the previous iteration's move, never a half-searched one.
08

History

David Slate and Larry Atkin used iterative deepening in Chess 4.5 in 1975 to manage clock time, and Richard Korf analysed the general technique in 1985, showing the overhead is a constant factor. Every engine since, from Deep Blue to Stockfish, deepens iteratively.

Back to Game AI