Iterative Deepening

Iterative deepening is a search strategy that repeatedly applies depth-limited search with increasing depth limits — first depth 1, then depth 2, then depth 3, and so on until a solution is found or resources are exhausted. In the context of the minimax algorithm, iterative deepening solves a paradox: the depth-limited minimax search requires choosing a depth in advance, but the optimal depth depends on the position. Iterative deepening discovers the appropriate depth dynamically.

The technique is computationally efficient despite apparent redundancy. In tree search, the cost of searching to depth d is dominated by the cost of the deepest level. The sum of costs for all shallower searches is a small fraction of the total. Iterative deepening therefore achieves the completeness of breadth-first search with the space efficiency of depth-first search. It is the standard architecture of modern chess engines and the prototype for any adaptive search procedure that must allocate limited computational resources across an unknown problem depth.

Iterative deepening is not merely an engineering optimization. It is a formal model of adaptive depth of processing — the cognitive phenomenon that humans and animals allocate more computation to harder decisions. The algorithm's depth is not a fixed parameter but a response to the problem's difficulty, discovered through interaction. This makes iterative deepening a bridge between algorithmic search and bounded rationality.