RAGBAZSearching the Solver Tree
A finite perfect-information game has a value under optimal play. The problem is that the tree is usually too large to read. Search is how we approximate the game-theoretic value we cannot compute exactly.
Game Theory First
For zero-sum, perfect-information games, optimal play pins down a value: win, loss, draw, or a numeric utility. The finite tree can be solved by backward induction.
Why search exists
The exact value is available in principle but not in practice. Chess, checkers, go, and tactical planning trees blow up so quickly that a program needs a budgeted procedure: expand the most useful part of the tree, estimate what cannot be expanded, and preserve enough trace to audit the decision.
The module spine
One-player search teaches frontier discipline. Two-player search adds an opponent who can answer. Alpha-beta shows how exact reasoning can skip irrelevant branches. B* changes the scalar score into an interval and asks which move can be proved best.
The Solver Tree
Branching factor b and depth d produce the wall: b^d. Every technique below is a way to spend less work against that wall.
Vocabulary
A node is a state. An edge is an action. A leaf is a terminal state or a budget boundary where the evaluator is called. The frontier is the set of generated states not expanded yet.
One Player: The Explorer's Path
BFS, Dijkstra, and A* are the same frontier machine with different priorities. Dijkstra is A* with h = 0. BFS is Dijkstra with unit costs.
Admissibility and consistency
An admissible heuristic never overestimates the remaining cost. A consistent heuristic also respects the edge costs between neighboring states. Those two properties are why A* can stop when it expands the goal and still return an optimal path.
IDA* memory note
When the frontier will not fit in memory, IDA* does repeated depth-first passes with increasing f limits. It repeats some work, but its memory footprint is close to the current path instead of the whole frontier.
Two Players: Checkers
Two-player search alternates control. A good move is not just locally attractive; it must survive the opponent's best reply.
Negamax
score(s, d) = max(-score(child, d - 1))Negamax writes minimax with one function. Positive means good for the side to move, so the child score is negated when the turn changes.
Move ordering
Alpha-beta can approach about b^(d/2) work under excellent ordering and degrade toward b^d under poor ordering. That is why engines spend so much effort predicting which move to search first.
B* Interval Search
B* backs up intervals instead of scalar scores. The engine tries to prove one move best or disprove the rest.
SSS* and MTD(f)
B* is not the only best-first adversarial line. SSS* showed how best-first minimax search could reason over solution trees; MTD(f) later reframed repeated zero-window alpha-beta probes around a guessed value. The shared theme is practical: use bounds and memory to avoid treating every branch as equally urgent.
Synthesis And Coda
The same tree vocabulary spans pathfinding, engines, and governance traces. What changes is the backup rule and the proof obligation.
| Line | Core value | Guarantee | When it wins |
|---|---|---|---|
| single-agent search | path cost | optimal path with admissible/consistent heuristic | navigation, planning, routing |
| minimax / alpha-beta | scalar adversarial value | same answer as minimax when bounds are correct | perfect-information games with useful move ordering |
| B* | pessimistic/optimistic interval | choose when one move can be proved to dominate | expensive evaluations with useful value bounds |
| MCTS | sampled value estimate | statistical improvement with more visits | large branching spaces where rollouts or learned priors help |
Checkers is solved
Chinook and Jonathan Schaeffer's team combined search with endgame databases. In 2007, checkers was announced as solved: with optimal play from both sides, the game-theoretic value is a draw.
Reviewer surface
A deployable search engine should expose chosen move, principal variation, depth, node count, cutoffs, cache hits, evaluation terms, and time budget. Governance starts when the solver tree leaves an inspectable trace.