1 Introduction

1.1 Motivation and historical context

Iterative deepening was developed in the 1970s as a practical response to the memory limitations of breadth‑first search and the incompleteness of depth‑first search in large state spaces. Early work in artificial intelligence, particularly in game‑playing programs, required a search strategy that could find solutions without exhausting memory and that would eventually find a solution if one existed. The technique was independently described by several researchers, with formal analysis appearing in the context of chess programming and automated theorem proving.

1.2 Basic concept

The core idea of iterative deepening is to repeatedly run a depth‑limited depth‑first search, each time increasing the depth limit by one, until a goal state is found. This approach combines the memory efficiency of depth‑first search (linear in the depth of the search) with the completeness of breadth‑first search (guaranteeing that a solution at any finite depth will be found). The algorithm is often called iterative deepening depth‑first search (IDDFS) when applied to tree or graph search.

2 Algorithm

2.1 Pseudocode

The following pseudocode outlines the iterative deepening algorithm:

function IDDFS(root, goal)
    for depth = 0 to ∞
        result := DLS(root, goal, depth)
        if result ≠ cutoff then
            return result

function DLS(node, goal, limit)
    if goalTest(node) then
        return node
    else if limit = 0 then
        return cutoff
    else
        for each child in successors(node)
            result := DLS(child, goal, limit - 1)
            if result ≠ cutoff then
                return result
        return cutoff

The outer loop increments the depth limit, and the inner subroutine performs a depth‑first search up to that limit. If no goal is found at the current limit, the depth limit is increased and the search restarts.

2.2 Depth‑limited depth‑first search subroutine

The depth‑limited depth‑first search (DLS) is a recursive algorithm identical to standard depth‑first search except that it stops expanding nodes beyond a given depth limit. It returns either a solution path, a special value indicating that no solution was found within the limit (often called a "cutoff"), or a failure signal if the entire limit was exhausted without finding a goal.

2.2.1 Termination conditions

A depth‑limited search terminates under three conditions:

  • Goal found: The current node satisfies the goal condition; the algorithm returns the solution.
  • Depth limit reached: The current depth equals the limit; the algorithm returns a cutoff value (not a failure), because a deeper search might succeed.
  • No successors: The node has no children (leaf node) and is not a goal; the algorithm backtracks and continues.

The cutoff value is distinguished from a failure to allow the outer iterative deepening loop to distinguish between "no solution at this depth" and "no solution at any depth" (which would require additional handling, e.g., when the search space is finite and fully explored without success).

2.3 Iterative deepening depth‑first search (IDDFS)

IDDFS is the most common instantiation of iterative deepening. It is memory‑efficient because it only stores a single path from the root to the current node, plus auxiliary information for backtracking. It is complete for finite state spaces and for infinite spaces where the goal is reachable at some finite depth.

2.3.1 Time complexity

The time complexity of IDDFS is \(O(b^d)\), where \(b\) is the branching factor and \(d\) is the depth of the shallowest goal. Although the algorithm expands nodes repeatedly at shallower depths, the overhead is modest: the total number of node expansions is

\[ \sum_{k=0}^{d} (d - k + 1) b^k = \frac{b^{d+2} - (d+2)b + (d+1)}{(b-1)^2} \]

which is \(O(b^d)\). For a typical branching factor \(b > 1\), the repeated expansions of the shallow levels constitute a constant factor overhead of at most \(b/(b-1)\), which is close to 2 for \(b=2\) and approaches 1 for large \(b\).

2.3.2 Space complexity

The space complexity of IDDFS is \(O(d)\), where \(d\) is the depth of the goal. This is because the algorithm only needs to store the current path from the root to the node being explored, along with recursion stack information. This linear memory requirement is a major advantage over breadth‑first search, which requires exponential memory (\(O(b^d)\)).

3 Properties

3.1 Completeness

IDDFS is complete for finite state spaces and for infinite state spaces in which a goal exists at some finite depth. Because the depth limit increases monotonically, if a goal is reachable, it will eventually be found when the limit reaches or exceeds its depth. For infinite state spaces with no guarantee of a finite solution (e.g., cycles without a goal), the algorithm may run forever, but such cases are typically handled by ad‑hoc bounds.

3.2 Optimality (for uniform cost)

If all step costs are equal (uniform cost), IDDFS is optimal: it finds the shallowest goal, which corresponds to the solution with the fewest steps. This follows from the incremental increase of the depth limit. For non‑uniform step costs, IDDFS is not optimal unless modified (e.g., using iterative deepening A* with a heuristic that accounts for cost).

3.3 Comparison with other search strategies

Breadth‑first search (BFS) explores nodes layer by layer and is also complete and optimal for uniform cost. However, BFS requires memory exponential in the depth of the solution, whereas IDDFS uses linear memory. When memory is limited, IDDFS is preferred over BFS despite the overhead of re‑expanding nodes.

Depth‑first search (DFS) uses linear memory but is not complete in infinite spaces (it may dive into a deep branch indefinitely) and is not optimal. IDDFS retains the linear memory of DFS while becoming complete and optimal, at the cost of re‑expanding nodes at shallower depths.

Best‑first search (e.g., greedy or A*) uses a heuristic to guide exploration. Unlike IDDFS, it typically requires memory proportional to the number of generated nodes (exponential in the worst case). IDDFS does not rely on heuristics, making it simpler and memory‑efficient, but it may have worse time performance if a good heuristic is available.

4 Variants

4.1 Iterative deepening A* (IDA*)

IDA* is a variant that replaces the depth limit with a cost threshold based on a heuristic evaluation function. It performs depth‑first search with a bound on the total estimated cost \(f(n) = g(n) + h(n)\), where \(g(n)\) is the cost from the root to node \(n\) and \(h(n)\) is a heuristic estimate of the remaining cost to a goal.

4.1.1 Use of heuristic functions

IDA* benefits from heuristic functions in the same way as A*: a good heuristic reduces the number of explored nodes. The threshold is updated after each iteration to the smallest \(f\)-value that exceeded the previous threshold. This allows IDA* to find optimal solutions under admissible heuristics while keeping memory linear.

4.1.2 Threshold vs. depth limit

In standard IDDFS the limit is an integer depth; in IDA* the limit is a cost threshold (often a real number). The threshold is incremented not by a fixed step but by the minimal increase that allows new nodes to be considered. This makes IDA* suitable for problems with non‑uniform costs, whereas IDDFS is only optimal for uniform cost.

4.2 Iterative deepening depth‑first search on trees vs. graphs

When applied to a tree (no cycles), IDDFS is straightforward because each node is visited at most once per iteration. For graphs, the algorithm must handle cycles to avoid infinite loops.

4.2.1 Handling cycles

Two common approaches to handle cycles in graph search are:

  • Visited‑node tracking: Maintain a set of visited nodes (or visited paths) for each depth‑limited traversal. This increases memory usage but prevents re‑expansion within one iteration.
  • Depth‑first search with cycle detection: Use a path‑based check to avoid retracing the same path that leads back to an ancestor. This is the typical method in IDDFS where the recursion stack is used for detection.

Both approaches preserve completeness but may alter the asymptotic memory requirements depending on implementation.

5 Applications

Iterative deepening is widely used in two‑player adversarial games, where the state space is huge and a fixed depth limit is often unknown in advance.

5.1.1 Chess engine (e.g., minimax with alpha‑beta pruning)

Chess programs use IDDFS to implement iterative deepening in the minimax algorithm with alpha‑beta pruning. The search starts at a small depth (e.g., 3 plies) and increments the limit until time runs out. This allows the engine to return a move based on the deepest search completed, ensuring a useful result even if interrupted. Alpha‑beta pruning benefits from iterative deepening because move ordering can be improved by storing the principal variation from the previous iteration (transposition tables and killer heuristics).

5.1.2 Go and other combinatorial games

In Go, where the branching factor is very high, IDDFS is less common than in chess, but it is still used in some proof‑number search variants and in problems with limited depth (e.g., tsumego). The technique is also applied in games like checkers, Othello, and shogi, where the depth of search is critical and memory is limited.

5.2 Automated planning

In classical automated planning, iterative deepening is used for state‑space search when the plan length is unknown. By incrementally increasing the plan horizon, the planner can find a shortest plan without storing all reachable states. It is particularly useful for strips‑style planning where the state space is large and heuristics may be weak.

5.3 Theorem proving and logic puzzles

In automated theorem proving, iterative deepening is applied to proof search (e.g., in resolution‑based systems) to find a proof of minimal length. Logic puzzles such as the 15‑puzzle, Rubik’s Cube, and Sokoban are often solved using IDA* or IDDFS when the solution depth is unknown and memory is constrained.

6 Limitations and enhancements

6.1 Repeated expansion overhead

The principal drawback of iterative deepening is that nodes at shallow depths are expanded multiple times. Although the overhead is a constant factor asymptotically, for very deep solutions (e.g., depth 100 with branching factor 4) the repeated expansions can be significant. The overhead can be mitigated by using transposition tables to store results from previous iterations, but this increases memory usage.

6.2 Memory‑bound variants

Several memory‑bound variants attempt to reduce the overhead of repeated expansions or to handle larger state spaces. Examples include:

  • Iterative deepening with partial expansion: Only re‑expand nodes when necessary.
  • Recursive best‑first search (RBFS): Uses linear memory and backtracks based on cost bounds.
  • **Memory‑bounded A* (MA*)**: Combines iterative deepening with a memory‑bound to manage stored nodes.

These variants trade off between time and memory, often achieving better performance in practice.

6.3 Parallel iterative deepening

Parallel implementations of iterative deepening distribute the search across multiple processors. One common approach is to let different threads or processes run depth‑limited searches at different depth limits simultaneously, or to parallelize the depth‑first search within a single iteration. Load balancing and synchronization are key challenges, but parallel IDDFS has been successfully applied in game engines and automated planning to exploit multi‑core architectures.