Iterative Deepening Search, in depth: IDA* thresholds, the real-valued-cost iteration explosion, (1+eps) bound growth and iterative-deepening alpha-beta

One loop, three kinds of bound

Every iterative deepening variant has the same shape: a bounded search, a rule for the next bound, and a stopping condition.

Memory is linear in the bound for all of them, because each iteration is a depth-first search that keeps only the current path. That is the whole reason to accept repetition. A* on the same problems keeps every generated node, and on a 15-puzzle that exhausts memory long before time.

IDA*: the next bound is the smallest overflow

IDA* replaces the depth bound with an f-bound. The search prunes any node whose f exceeds the bound, and while doing so it records the smallest f among the pruned nodes. That minimum becomes the next bound: it is the smallest value that admits at least one new node. With an admissible heuristic (one that never overestimates), the first goal found has optimal cost. Every node on an optimal path has f at most C*, so while the bound is below C* some node on that path must have been pruned, which keeps the next bound at most C*. Goals are only accepted within the bound.

import math

def ida_star(start, h, succ, is_goal, eps=0.0):
    """Returns (path, cost, [(bound, expanded), ...]). eps > 0 gives cost <= (1+eps)*optimal."""
    path, stats = [start], []
    bound = h(start)
    def search(g, prev):
        nonlocal expanded
        node = path[-1]
        f = g + h(node)
        if f > bound:
            return None, f
        if is_goal(node):
            return g, f
        expanded += 1
        nxt = math.inf
        for child, cost in succ(node):
            if child == prev:                 # never undo the last move
                continue
            path.append(child)
            found, r = search(g + cost, node)
            if found is not None:
                return found, r
            path.pop()
            nxt = min(nxt, r)
        return None, nxt
    while True:
        expanded = 0
        found, nxt = search(0, None)
        stats.append((bound, expanded))
        if found is not None:
            return path, found, stats
        if nxt == math.inf:
            return None, math.inf, stats
        bound = max(nxt, bound * (1 + eps))

The prev check stops the search from undoing its last move, the cheapest cycle there is. Longer cycles and transpositions are still searched repeatedly. That is the price of linear memory, and the reason real solvers add a small transposition table or a pattern of forbidden move sequences.

Worked example: unit costs

On the 8-puzzle with unit move costs and the Manhattan-distance heuristic, f values move in steps of 2: each move changes g by 1 and h by plus or minus 1. Few iterations are needed. Six start states, each scrambled with 200 random moves, took 2 to 8 iterations. For example, the seed-21 state has optimal cost 26 and was solved in 5 iterations with 4,180 expansions in total. The seed-25 state has cost 24 and took 8 iterations and 4,352 expansions. The last iteration dominates. On a shallower start state (80 random moves from seed 7, optimal cost 24) the per-iteration log reads bound 20: 5 expansions, bound 22: 165, bound 24: 631. The final iteration did 79% of the 801 expansions; the two earlier ones added 27% on top of it. The last raise multiplied the work by 3.8. When work grows by a factor B per iteration, the repeated iterations cost about 1 / (B - 1) of the last one, 36% for B = 3.8, the same order as measured.

Real-valued costs and bounded threshold growth

Now give each tile its own move cost, drawn uniformly from 1 to 2, and weight each tile's Manhattan distance by its cost (still admissible). The puzzles are the same; only the costs changed. The f values are now almost all distinct, so each raise of the bound admits only a handful of new nodes, and every iteration repeats all the work before it.

The fix in the code is the eps parameter: the next bound is the larger of the smallest overflowing f and the old bound times 1 + eps. The guarantee follows from the same argument as before. The previous bound was below C*, or the goal would have been found, so the new bound is at most max(C*, (1 + eps)C*), and any goal accepted within it costs at most (1 + eps)C*. In these runs eps = 0.02 returned the optimal cost on every start state while cutting expansions by between 2x and 29x. With eps = 0.1 the cost was still optimal on all six of these states. On a seventh state, scrambled 30 moves from seed 12, it returned 29.294 against an optimum of 27.748: 5.6% worse, inside the 10% bound.

The problem is flagged briefly in A* variants; the measurements above show its size. Other remedies exist. IDA*_CR picks the next bound from a histogram of pruned f values, so that each iteration roughly doubles the work. Recursive best-first search (RBFS) keeps linear memory but backs up f values so it re-expands less. Rounding costs to a coarser grid gives the same effect as eps, with a bound you can compute from the rounding step.

Iterative deepening under a clock: game search

A chess or Go engine does not know how deep it can search; it knows how long it may think. Iterative deepening turns depth-limited alpha-beta into an anytime algorithm. Search depth 1, then 2, then 3, and whenever the clock expires, play the best move from the last depth that finished. A depth abandoned halfway gives no trustworthy answer, because unsearched moves might be better.

The surprise is that the iterations are cheaper in total than one direct search, because alpha-beta's pruning depends on move order. Searching the best move first gives the tightest bounds and the most cut-offs. Each finished iteration records the best move at every node it searched, and the next iteration tries that move first.

def negamax(node, depth, alpha, beta, best_move):
    if depth == 0:
        return evaluate(node)                 # from the side to move
    order = list(moves(node))
    bm = best_move.get(node)
    if bm is not None:                        # previous iteration's best move first
        order.remove(bm); order.insert(0, bm)
    best, arg = -math.inf, None
    for m in order:
        v = -negamax(play(node, m), depth - 1, -beta, -alpha, best_move)
        if v > best:
            best, arg = v, m
        alpha = max(alpha, v)
        if alpha >= beta:
            break
    best_move[node] = arg
    return best

def think(root, deadline):
    table, move = {}, None
    for depth in range(1, 64):
        if time.monotonic() > deadline:
            break
        negamax(root, depth, -math.inf, math.inf, table)
        move = table[root]                    # only a finished depth is trusted
    return move

This was measured on a synthetic game tree with branching factor 8 and an incremental evaluation, where each move adds a fixed pseudo-random value, so shallow scores correlate with deep ones as they do in real games. The baseline was a single fixed-depth alpha-beta search with no move ordering. Totals over five roots:

Both searches returned identical values at every root. Real engines also order moves with transposition tables, killer moves and history heuristics, so the gap against a realistic baseline is smaller than this. The direction holds, though: the shallow iterations pay for themselves. Background on the pruning itself is in alpha-beta pruning, and the minimax framing in game tree search with minimax.

Engines also reuse the previous iteration's score. An aspiration window searches the next depth with a narrow alpha-beta window centred on the last score; most of the time the true value lands inside it and the search is cheaper, and when it falls outside, the engine re-searches with a wider window. The previous iteration's principal variation, the line of best moves from the root, is also searched first at every depth, which is the move ordering above applied along the most likely line.

Operational guidance

• Do not start an iteration you cannot finish. Estimate the next iteration's time as the last one's time multiplied by the effective branching factor (the ratio of the last two iterations' node counts). If that would pass the deadline, stop now.
• Abort cleanly. Check the clock every few thousand nodes and unwind with a flag or exception. Discard the aborted iteration's result, except for a best move it has already proven better than the previous one.
• Cap the side tables. The best-move table grows with every node searched. Use a fixed-size hash table with replacement, as engines do, not an unbounded dictionary.
• Log per-iteration stats. Record the bound, nodes expanded and elapsed time for each iteration. A sudden jump in the iteration count (the 260-iteration case) shows up immediately in these logs.
• Pick eps from the business tolerance. If a route 2% over optimal is acceptable, eps = 0.02 is free speed, with a stated guarantee.

Failure modes

• Real-valued costs with the exact rule. Iteration counts in the hundreds; fix with eps, rounding or IDA*_CR.
• Inadmissible heuristic. IDA* still returns a path, just not an optimal one, and the test suite will not notice unless you compare costs against A* on small cases.
• Graphs with many transpositions. Linear memory means re-expanding the same state through different paths; on grid maps that can be exponential. Use A* when memory allows.
• Trusting a partial iteration. Playing the best move from an unfinished depth can pick a move whose refutation had not been searched yet.
• Floating-point bounds. Comparing f against the bound with exact floats can loop on a value that never quite admits the node. Use integers, or a tolerance.

Trade-offs

For the A* side of this comparison, see A* search, in depth.

What to do next

1. Run the IDA* code on your own puzzle or planner and print the per-iteration (bound, expanded) list.
2. If the iteration count exceeds about 20, add eps = 0.02 and compare cost and time.
3. Check the heuristic for admissibility on small instances by comparing with an exact A* run.
4. For a game, wrap your alpha-beta in the think() loop and measure node counts with and without the best-move table.
5. Add a deadline and a next-iteration time estimate; test that it never returns a move from an unfinished depth.