Iterative Deepening runs the same depth-limited search over and over, one ply deeper each time: search to depth 1, stop and remember the best move found; search to depth 2, stop and remember that; keep going until either time runs out or the search limit reaches the end of the game. Every entry on this site's Game Trees list so far — Minimax, Monte Carlo Tree Search, Expectimax, Transposition Tables, Principal Variation Search — could afford to search this page's fixed tic-tac-toe board all the way to a real win, loss, or draw, because the board only has four empty cells left. Real games rarely offer that luxury: a chess engine given a few seconds per move cannot search to checkmate, so it needs an answer that's only as deep as time allows, evaluated by a heuristic — an educated static guess at a position's value — wherever the search runs out of time before the game runs out of moves. Iterative deepening is how that search gets structured: instead of guessing a depth limit up front and hoping it fits the time budget, run depth 1, then depth 2, then depth 3, and so on, always having a complete, usable answer on hand the instant the clock runs out.
Same fixed board as Minimax, Transposition Tables, and Principal Variation Search — O to move, four empty cells. The search below runs depth limit 1, then 2, then 3, then 4 (deep enough to reach every real outcome, identical to a full search). A node reached exactly at the current depth limit without the game being over is a cutoff: its value comes from the heuristic described below, not from playing the game out. Toggle whether each iteration reuses the previous iteration's best root move as its own first move to try. Press Step or Run.
The heuristic used at a cutoff node here looks at all eight lines (three rows, three columns,
two diagonals) and scores each one independently: a line containing marks from both sides
is dead — nobody can ever complete it — and contributes nothing. A line with only X marks in it
contributes 3^(X's marks in that line); a line with only O marks contributes the same
amount negatively. The cubic-feeling jump from a lone mark (contributing 3) to two marks in the
same still-open line (contributing 9, not 6) is deliberate: two in a row is one move from winning,
which is a much bigger deal than two separate one-in-a-rows, and squaring the exponent rather than
the count reflects that directly. Summing all eight lines gives one number: positive favors X,
negative favors O, and it's computed instantly from the board alone — no recursion, no lookahead,
just a snapshot judgment about who currently controls more still-winnable lines.
Reusing a finished iteration's best root move to reorder the next one costs nothing to compute and pays for itself the same way Principal Variation Search's own closing paragraph predicted: "a cached move from a previous, shallower search is a strong first guess at what to try first." Transposition Tables get that same strong first guess by hashing the exact board into a cache; iterative deepening gets it for free from its own structure, since the previous iteration's answer is sitting right there in memory the instant the next one starts. A better move tried first at the root means alpha-beta cuts off more of the remaining candidates sooner — the same ordering-sensitivity Minimax's own Pitfalls section demonstrated (31 vs. 40 vs. 44 nodes on that page's identical board, purely from move order), now paid for by the search's own previous round instead of by hand-picking an order in advance.
function heuristic(board) {
let score = 0;
for (const [a, c, d] of LINES) {
const cells = [board[a], board[c], board[d]];
const x = cells.filter(v => v === 'X').length;
const o = cells.filter(v => v === 'O').length;
if (x > 0 && o > 0) continue; // dead line — both sides present, nobody can complete it
if (x > 0) score += 3 ** x;
else if (o > 0) score -= 3 ** o;
}
return score;
}
function alphabeta(board, depth, maximizing, alpha, beta, depthLimit, rootOrder) {
const w = winner(board);
const empties = emptyCells(board);
if (w || empties.length === 0) return score(w, depth); // real outcome, not a guess
if (depth >= depthLimit) return heuristic(board); // out of search budget — guess instead
let cells = empties;
if (depth === 0 && rootOrder) {
// try last iteration's best move first, then everything else in the usual order
cells = rootOrder.filter(c => empties.includes(c))
.concat(empties.filter(c => !rootOrder.includes(c)));
}
const mark = maximizing ? 'X' : 'O';
let best = maximizing ? -Infinity : Infinity;
let bestCell = null;
for (const cell of cells) {
board[cell] = mark;
const value = alphabeta(board, depth + 1, !maximizing, alpha, beta, depthLimit, rootOrder);
board[cell] = null;
const improved = maximizing ? value > best : value < best;
if (improved) { best = value; bestCell = cell; }
if (maximizing) alpha = Math.max(alpha, best); else beta = Math.min(beta, best);
if (beta <= alpha) break;
}
return { value: best, bestCell }; // simplified — real code threads bestCell out separately
}
function iterativeDeepening(board, maxDepth) {
let rootOrder = null;
let result = null;
for (let depthLimit = 1; depthLimit <= maxDepth; depthLimit++) {
result = alphabeta(board, 0, false, -Infinity, Infinity, depthLimit, rootOrder);
rootOrder = [result.bestCell, ...emptyCells(board)]; // this iteration's pick goes first next time
// result is a complete, usable answer here — safe to stop early if time runs out
}
return result;
}A shallower iteration landing on the right move doesn't mean the search is converging monotonically toward it — checked directly, it isn't. On this page's own board, depth 1 picks cell 6 (heuristic value -12) — the true best move, but for the wrong reason: the heuristic likes cell 6 because it opens two live two-in-a-row threats for O one ply out, not because it sees the forced win three plies later. Depth 2 then flips to cell 3 (value +6, favoring X) — a genuinely worse move than depth 1's own answer, because the heuristic at two plies now sees X's best immediate reply to cell 6 and doesn't yet see far enough past it to find O's follow-up. Only at depth 3 does the search recover cell 6 for good, with a value (-7) that already matches the true, fully-searched answer Minimax's own page confirms. A caller that stops after depth 1 under a tight time budget gets the right move by accident; a caller that stops one round later, after depth 2, gets a worse move with exactly the same amount of apparent confidence. Depth alone doesn't certify quality — only reaching a depth that actually resolves the position does, and there's no way to tell from the outside which kind of depth you've stopped at.
Redoing every shallower search is real, measurable overhead here — not the "nearly free"
saving textbooks describe for larger games. Summed across all four iterations, this board
costs 94 total nodes without root-move reuse, 84 with it — both
well over double the 40 nodes a single direct search straight to depth 4 costs
alone. The usual justification for iterative deepening's overhead is a geometric-series argument:
if each ply multiplies the node count by a large branching factor b, the deepest
iteration alone accounts for roughly a b/(b-1) fraction of the total work, which
approaches 100% as b grows — a large enough branching factor makes every shallower
iteration combined cost only a few percent more than searching to the final depth just once. That
argument needs a large, roughly stable b to pay off, and tic-tac-toe never offers one:
this board's own branching factor starts at 4 and shrinks by one every ply, nowhere near large
enough for the shallow iterations to become negligible. Run from a completely empty board instead
(branching factor starting at 9, so the argument gets more room to work) and the ratio barely moves —
54,607 total nodes without reuse, 47,534 with it, against
20,866 for one direct depth-9 search: still over double, not the near-zero overhead
the textbook argument promises for a bigger, steadier branching factor like chess's.
Time: O(b^d), the same asymptotic order as a single search to depth
d — every shallower iteration is strictly smaller than the deepest one, so summing them
never changes the dominant term, only its constant factor. That constant is measured directly above:
2.35x this board's own direct-search cost without root-move reuse (94 vs. 40),
2.10x with it (84 vs. 40); the empty-board sweep lands at a similar
2.62x and 2.28x. Root-move reuse pays off almost entirely in the single most expensive iteration: checked
depth-by-depth on this board, reuse costs one extra node at depth 2 (13 vs. 14) and changes nothing
at depths 1 and 3, but at depth 4 — the deepest, priciest pass — it drops from 40
nodes to 29 (27.5% fewer), an 11-node saving that alone accounts for the entire
net 10-node improvement (94 → 84) once depth 2's one-node cost is subtracted back out.
Space:
O(d), unchanged from Minimax and
Principal Variation Search — only the
single line of recursion currently being explored is held in memory; the previous iteration's best
move is the only thing carried forward, one integer, not a whole search tree.
This is the site's sixth Game Trees entry, and the first to deliberately search less than the whole tree and guess the rest. Minimax, Principal Variation Search, and Transposition Tables all search this exact board to a real, final outcome; Monte Carlo Tree Search samples instead of exhausting the tree, but every sample it runs still plays a game out to a real result. Iterative deepening is the first entry whose intermediate answers are frank estimates, backed by a heuristic rather than a finished game — the approach every engine for a game actually too large to solve exhaustively has to fall back on, tic-tac-toe included, the moment the search budget runs out before the board fills up. A seventh entry, Zobrist Hashing, pairs naturally with this page's own repeated shallower passes: each pass re-explores positions the previous one already touched, exactly the repeat a transposition table catches, and Zobrist hashing is what keeps that table's key cheap to maintain across every one of those passes instead of rebuilt from scratch each time. See Choosing a Game Tree Search Algorithm for how all ten compare side by side, including when a reliable heuristic like this page's own line-counting one should send you here instead of Monte Carlo Tree Search's random playouts.