Motivation
A program that chooses actions needs a precise account of what counts as success. For a delivery robot, success may mean reaching a location with minimum travel cost. For a game player, it may mean choosing an action that survives the opponent's best reply. Both tasks involve exploring possible futures, but their mathematical objectives differ. A short route is a property of one path; a sound game move must account for several possible continuations selected by somebody else.
Exhaustive exploration soon becomes expensive. With at most successors per position and depth , a full tree can contain nodes. A heuristic can direct attention toward promising states, but a plausible numerical score is not automatically a certificate. We need to know which inequalities make a search result trustworthy and which implementation choices preserve those inequalities. This unit develops those conditions before using them in examples.
Basic finite graphs, induction and asymptotic notation are assumed.
Definitions
Definition 1.1.1
(Search problem and optimal remaining cost)
A deterministic search problem consists of a state set , an initial state , goal states, directed legal transitions and transition costs . A path accumulates the sum of its transition costs. The optimal remaining cost is the infimum of costs of goal-reaching paths from , with value infinity when no such path exists. In the finite, nonnegative setting used below, every reachable goal with finite optimum has a cheapest simple path after cycles of nonnegative cost are removed.
Definition 1.1.2
(State versus search node)
A search node records a particular path, whereas a state records the information needed to determine legal futures. Several nodes may therefore represent the same state. Merging them is justified only when the state representation really is sufficient: if fuel affects future actions, location alone is not an adequate state. A graph-search implementation keeps the smallest discovered path cost and records a predecessor for reconstruction.
Definition 1.1.3
(Admissible and consistent heuristics; A*)
A heuristic is admissible if for every state, and we require at every goal . It is consistent if every transition satisfies
For a goal-reaching path, repeatedly applying consistency shows admissibility. An admissible heuristic may nevertheless be inconsistent. A* prioritizes discovered but unexpanded states by . Relaxing an edge means replacing by whenever this is smaller, and updating the predecessor. A reopened state is placed back in the frontier after such an improvement even if it was expanded before.
Definition 1.1.4
(Local search and hill-climbing)
Local search makes a different commitment. Hill-climbing stores a current candidate and moves to a neighbor with a better objective score. It need not retain alternative paths. A local maximum has no strictly better neighbor, but may be much worse than another region. Plateaux require a stated tie policy; allowing arbitrary sideways moves can create cycles.
Definition 1.1.5
(Minimax value)
For games, assume a finite rooted tree, deterministic transitions, perfect information, alternating MAX and MIN turns, and a numerical payoff to MAX at each leaf. The minimax value of a leaf is its payoff; an internal MAX node takes the maximum of its children's values and a MIN node takes their minimum. This is a zero-sum model: MIN is assumed to minimize exactly the quantity MAX maximizes. Chance outcomes and hidden information require different models.
Theorem/Proposition
Theorem 1.1.6
(A* with a consistent heuristic)
On a finite directed graph with nonnegative edge costs and a consistent nonnegative heuristic that is zero at goals, A* with strict cost-improvement updates may permanently close each state when it is removed with minimum . Every removed state's is optimal. If it stops when a goal is removed, the returned goal-reaching path is cheapest. Stale priority-queue entries must be ignored.
Proposition 1.1.7
(A* with an admissible heuristic and reopening)
On a finite directed graph with nonnegative edge costs, let be admissible and zero at goals, and suppose a goal is reachable from . Consider A* in which every strict improvement of a label puts back into the frontier, even if was expanded before, and which stops when a goal is removed. Then it stops, and the returned path is cheapest.
Proposition 1.1.8
(Minimax and the - cutoff)
On a finite alternating game tree with the preceding assumptions, minimax is the payoff MAX can guarantee against optimal opposition. During depth-first evaluation, a MAX node may stop once its accumulated lower bound is at least an ancestor MIN choice's upper bound; dually, a MIN node may stop once its accumulated upper bound is at most an ancestor MAX choice's lower bound. Such cutoffs preserve the root minimax value.
The search theorem does not assert efficiency independent of the graph size. A finite graph may still be enormous. Similarly, - changes how many leaves need evaluation, while leaving the underlying worst-case exponential tree possible. These results establish correctness under stated models, not universal practical speed.
Proof sketch or proof idea
Proof
(Reweighting turns A* into Dijkstra)
Define a reweighted transition cost
Consistency says exactly that . On a path from to , all intermediate heuristic terms cancel, so its reweighted cost is the original cost plus . Consequently comparing A* priorities is equivalent to comparing tentative reweighted path costs. A* is therefore Dijkstra's label-setting argument on nonnegative reweighted edges.
For completeness, suppose a removed state had a strictly cheaper path. On that path take the first state not yet closed; its predecessor was already closed with optimal cost. Relaxation therefore placed an optimal tentative cost at . Nonnegativity of the remaining reweighted path implies the tentative reweighted cost at is no greater than the optimal reweighted cost at , which is strictly below the entry being removed. This contradicts minimum-priority removal. The start state begins with cost zero, so induction proves the claim. At a goal the heuristic is zero; a cheaper reachable goal would still have a frontier prefix with priority below the selected goal. Thus stopping on removal is sound.
Proof X-ray
What the heuristic inequality actually buys
The decisive assumption is edgewise consistency, not a vague tendency to underestimate distances. It converts every transformed edge into a nonnegative number. The proof can then commit to a state permanently because later paths cannot sneak through a negative transformed edge and lower its settled cost. Admissibility alone supplies a frontier bound for a goal proof, but does not justify the same permanent-closing step.
Proof
(Settled prefixes keep a frontier state below the optimum)
Termination. Every label is the cost of a walk built by chained relaxations. By induction these walks are simple paths: if the walk reaching already contained , then already had a label no larger than the cost of that prefix, and labels never increase, so relaxing through would not be a strict improvement. A finite graph has finitely many simple paths, so each state has finitely many possible labels. Each insertion follows a strict decrease, so only finitely many insertions occur.
Optimality. Let be a cheapest goal path, of cost . Each prefix is a cheapest path to its endpoint, with cost . Call settled once it has been expanded while its label equalled . Suppose no goal has been removed yet. Then is not settled, so there is a first unsettled vertex on the path. If , then is on the frontier with label . If , then was expanded with its optimal label, so received a label at most . Labels are costs of paths, so the label equals . Since has not been expanded with that label, and every strict improvement re-inserts a state, it is on the frontier. Its priority satisfies
because the rest of the path reaches the goal at cost . So until a goal is removed, the frontier is nonempty and its minimum priority is at most . A goal removed with label has priority , since at goals. Removal of a minimum-priority entry gives , and because is the cost of some path from to a goal. Hence .
Proof
(Induction on height, then bound propagation)
For minimax, use induction on tree height. At a leaf the guarantee equals the specified payoff. At a MAX node, MAX can choose a child attaining the largest guaranteed value, and MIN can hold every other choice to its corresponding child value. At a MIN node the dual argument applies. These two directions establish both attainability and the opponent's matching bound.
For pruning, suppose an earlier root choice already guarantees . Within a new MIN child, finding any response of value at most establishes an upper bound on that whole child. Further responses can only lower its value, so MAX cannot gain a strictly larger root payoff by choosing it. At a MAX node the argument reverses. Equality permits pruning for computing a value or one optimal move; enumerating every tied optimal move may require retaining more branches. A cutoff return may be a bound rather than the exact value of the pruned subtree.
The following trace uses a separate eight-leaf tree. Compare an exact root value with the bounds returned by pruned subtrees.
Worked examples
Worked example 1.1.9
(A consistent route estimate)
Let edges be of cost , of cost , of cost , of cost , and of cost . Set . Every edge passes consistency, including on . A* removes , then with . It improves to , and discovers with . Expanding improves to . Removing certifies the path of cost . Discovering a goal of cost earlier was insufficient grounds to stop.
Worked example 1.1.10
(An admissible heuristic that requires reopening)
Take cost , cost , cost , and cost . Use . The true remaining costs at are , so the heuristic is admissible. A* first closes at cost because its priority is , below 's . It discovers a goal of cost . Expanding then finds at cost . If closed states cannot reopen, this improvement never reaches , and the result is instead of . The inconsistent edge is : . Reopening repairs the result.
The following interactive uses different graphs from the two examples above. In its consistent graph, the optimum is 7 and the first generated goal costs 10; in its inconsistent graph, reopening gives 5 while rejecting improvements to closed states gives 6. Compare both stopping policies and trace the queue rather than transferring the preceding examples’ numeric values.
Worked example 1.1.11
(A genuine - cutoff)
A root MAX node has two MIN children. The left child's leaves, visited first, have payoffs , so its value is and the root's lower bound becomes . In the right child, the first visited leaf has payoff . This child now has upper bound , regardless of its unvisited leaves. It can be pruned, and MAX chooses the left child with value . If the right child's second payoff were , its MIN value would still be . If it were , its value would be . Neither possibility improves the root choice.
Common mistakes
Counterexample mode
A local improvement need not lead to the best state
On the chain of neighboring states , let scores be . Strict hill-climbing from moves to and stops: both neighbors have lower score. The global maximum is at . The correct conclusion from stopping is only that no allowed local step improves the current state. Random restarts or a richer neighborhood may help empirically, but need separate success guarantees.
Common mistake
(Stopping when a goal is first generated)
A* must test for a goal when a state is removed from the frontier, not when it is generated. In the consistent route example above, the goal is generated first with , but the cheapest path costs and is found only after is expanded.
Common mistake
(Testing admissibility against a known route)
Admissibility compares with the true optimum , not with the cost of a route already found. In the reopening example the first route found from costs , while . A claimed value passes the test but violates .
Common mistake
(Treating every level as MAX)
Taking the maximum at every level models an opponent who cooperates. For a MAX root with two MIN children whose leaves are and , the minimax value is , whereas the maximum at every level would claim , a payoff the opponent never has to allow.
A state key must preserve future possibilities. A depth-limited minimax search with a heuristic leaf evaluator is exact for that truncated tree, while its prediction about the full game depends on evaluation error and unsearched tactics.
Search-space complexity and storage complexity also differ. Ordinary A* may retain a large frontier and a cost table. A depth-first game search can keep a stack proportional to depth, apart from move generation and optional tables. A transposition table must distinguish exact values from lower and upper bounds, particularly when values came from pruned searches or different remaining depths.
With the best move ordering, pruning examines about the square root of the leaves of a full tree.
A natural next question
How many leaves can pruning save?
With the best move ordering, pruning examines about the square root of the leaves of a full tree.
In a uniform tree with branching factor and depth , with distinct leaf values, the least number of leaves that - can examine is , against for full minimax. For and this gives of leaves. The best case needs a favorable move ordering, which is not known in advance; the worst case still examines every leaf.
Summary
Search algorithms become easier to assess when each numerical label is given a meaning. A*'s is a discovered path cost, is a lower estimate, and consistency permits permanent closing. Minimax values express guarantees against opposition; - uses bounds to avoid irrelevant work. Local search scores guide improvement but do not, by themselves, prove a global result. Always state the state model, stopping rule and handling of repeated states alongside an algorithm name.
Exercises
Exercise 1.1.12
(On a four-neighbor rectangular grid with unit-cost legal moves, prove that Manhattan distance to a fixed target is consistent even when some cells are blocked. Explain what happens at states from which the target is unreachable.)
FoundationProof
Solution(3)
- 1
Check one legal move
Key step
Write . Neighboring states differ by one in exactly one coordinate, so the triangle inequality for absolute values gives .
Because: Only one coordinate term changes, and by at most one.
- 2
Blocked cells and paths
Blocked cells only delete edges, so the inequality remains valid on every surviving edge, and is zero at the target. Along a legal path of moves from to the target, applying the inequality times gives , hence .
- 3
Unreachable states
∎If no path to the target exists from , then , so the finite estimate still satisfies . Admissibility does not assert that a path exists.
Exercise 1.1.13
(For the inconsistent example above, compute all true remaining costs, identify every failed consistency inequality, and trace A* with reopening until the goal is removed.)
Core
Solution(3)
- 1
Compute the true remaining costs
Key step
. From the only route is , so . From the only route is , so . From the routes and cost and , so .
- 2
Test every edge
: . : . : . : is false. Only fails consistency.
- 3
Trace A* with reopening
Write labels as . Expanding gives and . Expanding inserts . Expanding improves to and reopens it; expanding again improves to . Removing returns cost . The priority fell after expansion because consistency fails.
Quick check
(A MAX root has three MIN children with leaf lists , and , searched left to right. Give the minimax value and identify the leaves skipped by - with initial bounds minus and plus infinity.)
Solution · Answer
The child values are , so the root value is . Both left leaves are visited, which establishes the root lower bound . In the middle child the first leaf is already at most , so the leaf is skipped. In the last child the first leaf does not justify a cutoff, so the leaf must be read and determines the value. Exactly one leaf, , is skipped. A high first response at a MIN node gives no guarantee about the remaining responses.
Exercise 1.1.14
(If and are nonnegative consistent goal-zero heuristics on the same graph, prove that their pointwise maximum is consistent. Is their sum necessarily admissible? Give a specific example.)
Core
Solution(3)
- 1
Choose the maximizing index
Key step
Let and fix an edge . Choose with . Then .
Because: Each is consistent, and because is the maximum.
- 2
Check the other properties
The maximum of nonnegative functions is nonnegative, and at a goal both values are zero, so is zero there. Hence is a consistent goal-zero heuristic.
- 3
Test the sum
Take a single edge of cost , with both heuristics equal to at and at . Each is exact and consistent, but their sum is at , exceeding the true cost . Combining lower bounds by a maximum is safe here; adding them needs a separate decomposition argument. The sum is therefore not necessarily admissible.