= Solution
\b[<Depth-first search> computes <minimax search> values with much less live storage and naturally supports <alpha-beta pruning>.] A parent's value needs only its current best child value and the next child to visit. Once a child subtree has been evaluated, its internal <search nodes> can be discarded; a final value cannot usually be computed from a nonterminal frontier alone.
With <branching factor> $b$ and horizon $d$, <breadth-first search> stores a frontier of order $b^d$. A <depth-first search> implementation storing sibling lists uses $O(bd)$ <space complexity>; lazy successor generation can reduce this to $O(d)$ frames plus game-state storage. Both unpruned traversals have $O(b^d)$ <time complexity> for $b>1$. <Depth-first search> also supplies a completed sibling outcome early, allowing <alpha-beta pruning> to reject later subtrees before generating them.
Back to article page
