Search, constraint satisfaction, and the classical AI toolkit

Why this subject matters now

The classical AI curriculum is sometimes dismissed as a museum tour, and the dismissal is worth taking seriously enough to refute. The algorithms in this page are not historical context for deep learning. They are running today, at scale, in systems where a wrong answer is unacceptable. Google's OR-Tools CP-SAT solver, a direct descendant of the constraint-propagation and clause-learning ideas derived below, schedules real workloads and has dominated the international constraint-programming competitions for years. SAT and SMT solvers in the CDCL family verify hardware designs at every major chip vendor and check cloud security policies at AWS. A* and its bounded-suboptimal variants route vehicles, plan robot motion, and drive the pathfinding in essentially every shipped video game. Particle filters localize warehouse robots and vacuum cleaners. Monte Carlo tree search, which is minimax search with a learned evaluation, was the backbone of AlphaGo and AlphaZero and now shows up in the reasoning loops of research agents.

The deeper reason to internalize this material is that the modern agent stack is re-deriving it. An agent that chains tool calls toward a goal is doing state-space search over action sequences, whether or not its authors call it that. When it samples several continuations and keeps the best, that is beam search. When it scores partial plans with a learned value model and expands the most promising, that is best-first search with a heuristic, and the questions that mattered in 1968 (is the heuristic admissible, will the search terminate, how much does pruning save) matter again, with the same answers. A practitioner who knows exactly what A* guarantees, what alpha-beta cannot prune, why arc consistency is cheap and full consistency is NP-hard, and what a conflict-learned clause is, can reason precisely about hybrid systems instead of guessing. The mathematics is settled, the proofs are short, and the payoff is a set of guarantees that neural networks alone do not provide.

State-space search, formalized

The problem statement

A search problem is a tuple \( (\mathcal{S}, s_0, A, T, c, \mathcal{G}) \), made up of a set of states \( \mathcal{S} \), an initial state \( s_0 \), a finite set of actions \( A(s) \) available in each state, a deterministic transition function \( T(s,a) \) giving the successor state, a step-cost function \( c(s,a,s') \ge 0 \), and a goal test \( \mathcal{G} \subseteq \mathcal{S} \). A solution is a sequence of actions whose composed transitions lead from \( s_0 \) to a goal state, and an optimal solution minimizes the sum of step costs. The state space is a directed graph whose vertices are states and whose edges are actions, and everything in the first half of this page is a strategy for exploring that graph without building it explicitly, because it is usually astronomically large. The 8-puzzle used as the running example has \( 9!/2 = 181{,}440 \) reachable states, the 15-puzzle has about \( 10^{13} \), and chess has on the order of \( 10^{47} \). The graph is given implicitly by a successor function, and the algorithm's job is to touch as little of it as possible.

Two distinctions organize the whole subject. First, a tree search may revisit states reached by different paths, while a graph search keeps a reached table and never expands a state twice. The choice interacts with optimality guarantees in a way that becomes important for A*. Second, the frontier (the set of generated but unexpanded nodes) is a data structure, and the entire taxonomy of uninformed search algorithms falls out of one decision, which node the frontier yields next. A FIFO queue gives breadth-first search, a LIFO stack gives depth-first, a priority queue keyed on path cost gives uniform-cost search, and a priority queue keyed on path cost plus a heuristic gives A*.

              frontier discipline          algorithm        optimal?

              FIFO queue                   breadth-first    unit costs only
              LIFO stack                   depth-first      no
              priority queue on g(n)       uniform-cost     yes (c ≥ ε > 0)
              priority queue on g(n)+h(n)  A*               yes, if h admissible

Breadth-first search, correctness and the geometric blow-up

Breadth-first search expands nodes in order of depth, all nodes at depth \( k \) before any node at depth \( k+1 \). Its correctness argument is an induction on depth. The claim is that when BFS first generates a state \( s \) at depth \( k \), no path of length less than \( k \) reaches \( s \). For \( k = 0 \) this is trivial. Assume it holds through depth \( k \). A state first generated at depth \( k+1 \) was produced from a depth-\( k \) node, and if a shorter path existed, its endpoint would have been generated at some depth \( j \le k \), contradicting first generation at \( k+1 \). Consequently BFS returns a shallowest goal, which is cost-optimal exactly when all step costs are equal. With variable costs the shallowest goal need not be the cheapest, which is why uniform-cost search exists.

The cost of BFS is the size of the tree it touches. With branching factor \( b \) and shallowest goal depth \( d \), the number of generated nodes is at most

a geometric series dominated by its last term. For \( b = 10 \), each additional level of depth multiplies both time and memory by ten. The memory term is what actually kills BFS in practice, since every generated node stays in the reached table. At \( b = 10 \), \( d = 10 \), and 100 bytes per node, the frontier alone is on the order of a terabyte. Depth-first search trades this away. It stores only the current path and its unexpanded siblings, \( O(bm) \) nodes for maximum depth \( m \), but it abandons both completeness (in infinite spaces it can dive forever) and optimality (it returns the first goal it stumbles into). Iterative deepening runs depth-limited DFS with limits \( 0, 1, 2, \ldots \) and recovers BFS's guarantees at DFS's memory cost. The apparent waste of re-expanding shallow nodes is small because the tree is geometric. The number of nodes generated across all iterations with goal at depth \( d \) is

since a node at depth \( k \) is regenerated in every iteration with limit at least \( k \), of which there are \( d - k + 1 \). For \( b = 10, d = 5 \) this is \( 6 + 50 + 400 + 3{,}000 + 20{,}000 + 100{,}000 = 123{,}456 \) versus \( 111{,}111 \) for a single BFS pass, an 11 percent overhead in exchange for memory linear in depth. The overhead ratio tends to \( \left( \tfrac{b}{b-1} \right) \) as \( d \) grows, which for \( b = 10 \) is roughly 1.11 and even for \( b = 2 \) is only 2.

Uniform-cost search, Dijkstra's algorithm wearing a different name

Uniform-cost search (UCS) orders the frontier by \( g(n) \), the cost of the cheapest known path to \( n \), and expands the minimum. It is Dijkstra's algorithm restricted to a single source and terminated at a goal, and its correctness proof is the same exchange argument. The invariant reads, when UCS pops a node \( n \) for expansion, \( g(n) \) is the optimal path cost to \( n \). Suppose not, and let \( n \) be the first popped node for which some cheaper path \( P \) exists. Since \( P \) starts inside the expanded region (at \( s_0 \)) and ends outside it (at \( n \), not yet expanded), it must cross the frontier at some node \( m \). Every prefix of a path costs no more than the whole path because step costs are nonnegative, so \( g(m) \le \text{cost}(P) < g(n) \), and the priority queue would have popped \( m \) before \( n \), a contradiction. Applying the invariant to the goal state gives optimality. Completeness additionally requires every step cost to be at least some \( \epsilon > 0 \). Otherwise an infinite path of costs \( \tfrac{1}{2}, \tfrac{1}{4}, \tfrac{1}{8}, \ldots \) has finite total cost and UCS can fail to terminate. Under that assumption the number of expansions is bounded by \( O\!\left(b^{1 + \lfloor C^*/\epsilon \rfloor}\right) \) where \( C^* \) is the optimal cost, because no explored path is deeper than \( C^*/\epsilon \) steps.

One implementation detail matters for correctness and recurs in A*. The goal test must be applied when a node is popped, not when it is generated. A goal generated early via an expensive edge may sit on the frontier while a cheaper path to it is still being assembled, and testing at generation returns the expensive one. Dijkstra himself presented the algorithm in 1959. The AI literature rediscovered the framing with an implicit, exponentially large graph, which changes the engineering (no upfront vertex array, hashing states instead) but none of the mathematics.

Heuristic search and A*

Admissibility and consistency, defined precisely

A heuristic \( h(n) \) estimates the cost of the cheapest path from \( n \) to a goal. Write \( h^*(n) \) for the true value. Two properties matter. \( h \) is admissible if it never overestimates, meaning \( 0 \le h(n) \le h^*(n) \) for all \( n \), with \( h(\text{goal}) = 0 \). \( h \) is consistent (or monotone) if it satisfies a triangle inequality with respect to every edge. For every state \( n \), action \( a \), and successor \( n' \),

Consistency implies admissibility, and the derivation is a one-line induction along an optimal path. Let \( n = n_0, n_1, \ldots, n_k = \text{goal} \) be a cheapest path from \( n \). Applying the consistency inequality along each edge and telescoping,

so \( h(n) \le h^*(n) \). The converse fails. Admissible but inconsistent heuristics exist (assign \( h = h^* \) at one state and 0 at its neighbor along an expensive edge), though in practice almost every natural admissible heuristic is also consistent. Both 8-puzzle heuristics used below are consistent, since moving one tile changes the misplaced-tile count by at most 1 and changes any single tile's Manhattan distance by exactly 1, so in each case \( h \) drops by at most the step cost of 1 across any move.

A* and the optimality proof, written out

A* is best-first search on the evaluation function \( f(n) = g(n) + h(n) \), cost spent plus cost estimated to remain. Hart, Nilsson, and Raphael introduced it in 1968 and proved the two theorems that made it the default informed search algorithm. Both proofs are short enough to hold in the head, and both are worth having verbatim.

Theorem (optimality with an admissible heuristic). If \( h \) is admissible, A* tree search returns an optimal solution. Proof. Let \( C^* \) be the optimal cost. Suppose for contradiction that A* pops a suboptimal goal \( G_2 \), so \( g(G_2) > C^* \) and \( f(G_2) = g(G_2) + h(G_2) = g(G_2) \) since the heuristic is zero at goals. Consider any optimal path from \( s_0 \) to an optimal goal \( G \). At the moment \( G_2 \) is popped, some node \( n \) on that optimal path sits on the frontier (the path starts in the expanded region and leaves it somewhere, and \( G \) has not been popped or the search would have ended). Because \( n \) lies on an optimal path, \( g(n) = g^*(n) \), and by admissibility

so the priority queue would pop \( n \) before \( G_2 \). Contradiction. \( \square \)

For graph search, where each state is expanded at most once, admissibility alone is not enough. The search might lock in a suboptimal \( g \) value for a state whose cheaper path arrives later. Consistency repairs this through two lemmas. Lemma 1, \( f \) is nondecreasing along any path. If \( n' \) succeeds \( n \) via an edge of cost \( c \), then \( f(n') = g(n) + c + h(n') \ge g(n) + h(n) = f(n) \), where the inequality is exactly the consistency condition \( h(n) \le c + h(n') \) rearranged. Lemma 2, when A* with a consistent heuristic pops a node, it holds that node's optimal path cost. The argument mirrors the UCS proof. Suppose \( n \) is popped with \( g(n) > g^*(n) \). An optimal path to \( n \) crosses the frontier at some node \( m \) with \( g(m) = g^*(m) \). By Lemma 1 applied along the optimal path from \( m \) to \( n \), \( f(m) \le g^*(n) + h(n) < g(n) + h(n) = f(n) \), so \( m \) would be popped first, a contradiction. Together the lemmas give the stronger classical statement. A* with a consistent heuristic expands nodes in nondecreasing order of \( f \), never re-expands a state, and the first goal popped is optimal.

One more classical result explains why A* is not just correct but canonical, optimal efficiency. Any algorithm that is guaranteed optimal with the same information must expand every node with \( f(n) < C^* \) (every "surely expanded" node), because if it skipped one, an adversary could hide a cheaper solution through it and the algorithm would miss it. A* expands exactly this set, plus some subset of the \( f(n) = C^* \) tie set. No algorithm in the same class can expand fewer nodes on every problem. The proof is in Pearl's Heuristics (1984), together with the qualifications (the claim is about consistent heuristics and expansion counts, not wall-clock time).

Heuristic design and dominance

If two admissible heuristics satisfy \( h_2(n) \ge h_1(n) \) for all \( n \), then \( h_2 \) dominates \( h_1 \), and A* with \( h_2 \) expands a subset of the nodes A* with \( h_1 \) surely expands. The reason is immediate from the surely-expanded characterization. A node with \( g(n) + h_2(n) < C^* \) also has \( g(n) + h_1(n) < C^* \), so the \( h_2 \) set is contained in the \( h_1 \) set. Bigger admissible heuristics are never worse (up to tie-handling) and usually much better, so heuristic design is the art of pushing \( h \) up toward \( h^* \) without crossing it. The standard generator of admissible heuristics is problem relaxation. Remove constraints from the problem until it becomes easy, and use the relaxed problem's exact solution cost. Since every real solution is also a solution of the relaxed problem, the relaxed optimum cannot exceed the real one, and admissibility is automatic. In the 8-puzzle, allowing any tile to teleport to its destination makes the relaxed cost the misplaced-tile count \( h_1 \), and allowing tiles to slide through each other makes the relaxed cost the sum of Manhattan distances \( h_2 \). Manhattan dominates misplaced tiles because each misplaced tile contributes 1 to \( h_1 \) and at least 1 to \( h_2 \). Pattern databases push further. Solve a sub-puzzle (say, tiles 1 through 4) exactly for every configuration, store the table, and use lookups as the heuristic. Taking the maximum of several admissible heuristics is again admissible, since the max of lower bounds is a lower bound.

The 8-puzzle, measured

Everything above becomes concrete on one instance. The state below was produced by a seeded 60-step random walk from the goal (blank shown as a dot). Its optimal solution length, confirmed by four independent optimal searches, is 26 moves.

      start                goal
      4 8 2                1 2 3
      5 . 1                4 5 6          h_misplaced(start) = 8
      3 6 7                7 8 .          h_manhattan(start) = 16

The Manhattan value of 16 is the sum over tiles of row distance plus column distance to each tile's home. Tile 4 sits at the top-left but belongs at middle-left (distance 1), tile 8 sits top-middle but belongs bottom-middle (2), tile 2 is top-right and belongs top-middle (1), tile 5 is middle-left and belongs center (1), tile 1 sits middle-right and belongs top-left (3), tile 3 sits bottom-left and belongs top-right (4), tile 6 bottom-middle belongs middle-right (2), and tile 7 bottom-right belongs bottom-left (2), giving \( 1+2+1+1+3+4+2+2 = 16 \). Both heuristics are far below \( h^* = 26 \), and the gap is what the search pays for. Running the implementations from the code section on this instance gives the following counts, where "expanded" means popped from the frontier.

The effective branching factor \( b^* \) is the branching factor a uniform tree of depth 26 would need to contain the expanded nodes, obtained by solving \( \sum_{i=0}^{d} (b^*)^i = N + 1 \) numerically. The table is the entire subject in miniature. Uninformed search pays the full exponential, 169,364 expansions, only slightly fewer for BFS because it stops at generation. The weak heuristic cuts the work by a factor of 3.8, and the dominating heuristic cuts it by a further factor of 9.7, exactly the subset relationship the dominance argument promises (every problem, not just this one). And the improvement compounds with depth because it acts on the base of the exponential, not the constant. Dropping \( b^* \) from 1.53 to 1.31 at depth 26 is worth a factor of \( (1.53/1.31)^{26} \approx 56 \), close to the measured \( 169{,}364 / 4{,}598 = 36.8 \).

IDA* and weighted A*

A*'s frontier for hard instances outgrows memory long before time runs out, which is the problem Korf's iterative-deepening A* (1985) solves. IDA* runs a depth-first search that prunes any node whose \( f = g + h \) exceeds a bound. The initial bound is \( h(s_0) \), and each iteration raises the bound to the smallest \( f \) value that exceeded it. Memory is \( O(d) \), the current path. On the instance above IDA* used 6 iterations (bounds 16, 18, 20, 22, 24, 26, since \( f \) rises in steps of 2 in the 8-puzzle because each move changes \( g + h \) by 0 or 2 under a parity argument) and visited 10,269 nodes in total, about 2.2 times A*'s expansions, the price of re-walking shallow levels each iteration without a reached table. On the 15-puzzle, where A*'s frontier exceeds memory, IDA* with Manhattan distance was the first algorithm to solve random instances optimally, which is why it remains the reference algorithm for memory-constrained optimal search.

Weighted A* trades optimality for speed in a controlled way. It searches on \( f_w(n) = g(n) + w \, h(n) \) with \( w > 1 \), inflating the heuristic to make the search greedier. The guarantee is that the returned solution costs at most \( w \, C^* \). The proof mirrors the A* proof. When the goal \( G \) is popped, some node \( n \) on an optimal path is on the frontier with \( g(n) = g^*(n) \), and

using \( w \ge 1 \) in the middle step and admissibility at the end. Since \( f_w(G) = g(G) \), the returned cost \( g(G) \le w C^* \). The measured numbers show how favorable the trade is in practice. \( w = 2 \) reduced expansions from 4,598 to 542 (a factor of 8.5) while returning a 28-move solution against the guarantee's ceiling of 52, so the actual suboptimality is 7.7 percent, far below the worst case of 100 percent. This pattern, worst-case bound loose and practical loss small, is typical and is why bounded-suboptimal search is the default in robotics motion planning, where the anytime variants (ARA*, gradually lowering \( w \) as time permits) descend directly from this inequality.

Adversarial search

Minimax

A two-player zero-sum game with perfect information is a search problem where the transition alternates between a maximizing player and a minimizing opponent. The minimax value of a state is defined recursively, the utility at terminal states, the maximum over successors at MAX nodes, the minimum at MIN nodes,

Minimax computes the value an optimal player achieves against an optimal opponent, and by a straightforward induction it is a security level. Playing the minimax strategy guarantees at least \( V(s) \) against any opponent, since a suboptimal opponent can only hand MAX values that are at least as large as the minimum. Exhaustive minimax evaluates \( O(b^d) \) leaves for branching factor \( b \) and depth \( d \), which for chess (\( b \approx 35 \)) is hopeless beyond a few plies. Real systems cut off the recursion at a depth limit and substitute a heuristic evaluation function for \( U \). Everything proved about the search then holds relative to the evaluation, not the true game value, which is why evaluation quality dominates play strength.

Alpha-beta pruning, with the arithmetic

Alpha-beta computes the exact minimax value while skipping subtrees that provably cannot influence it. The algorithm threads two bounds through the recursion, \( \alpha \), the best value MAX can already guarantee on the current path, and \( \beta \), the best value MIN can already guarantee. A MIN node can stop examining children the moment its running minimum \( v \) drops to \( v \le \alpha \). MAX already has a path worth \( \alpha \) elsewhere, so MAX will never enter this node, and its exact value below \( \alpha \) is irrelevant. Symmetrically a MAX node stops when \( v \ge \beta \). The soundness argument is exactly that sentence made inductive. The pruned subtrees can only push the node's value further past the bound that already excludes it from the principal variation, so the root value is unchanged.

A worked trace on a depth-2 tree follows, MAX to move at the root, three MIN nodes with three leaves each.

                         MAX (root)
              ┌───────────────┼────────────────┐
             MIN A           MIN B            MIN C
           ┌──┼──┐         ┌──┼──┐          ┌──┼──┐
           8  5  6         4  9  3          7  5  2
                              ▲  ▲                ▲
                            pruned              pruned

At node A, the leaves 8, 5, 6 give value 5, and the root's \( \alpha \) rises to 5. At node B, the first leaf is 4, so B's value is at most 4, and \( 4 \le \alpha = 5 \) means MAX will never choose B regardless of the remaining leaves, so leaves 9 and 3 are pruned. At node C, the first leaf 7 sets C's running minimum to 7 (no cutoff, since \( 7 > 5 \)). The second leaf 5 drops the minimum to 5, and \( 5 \le \alpha = 5 \) triggers the cutoff, pruning the 2. The root value is \( \max(5, \le 4, \le 5) = 5 \), and the search evaluated 6 of 9 leaves. The implementation in the code section, run on exactly this tree, confirms value 5 with 6 leaf evaluations. Note the equality cutoff at C. Pruning on \( v \le \alpha \) rather than \( v < \alpha \) is safe for the root value, though it can hide equally good alternative moves.

How much pruning is possible was settled by Knuth and Moore in 1975. With perfect move ordering (best child first everywhere), alpha-beta on a uniform tree of branching \( b \) and depth \( d \) evaluates exactly

leaves. The counting argument runs as follows. To certify the root value, the proof tree must exhibit, along the principal variation, all \( b \) alternatives at levels where the player to move must be shown to have nothing better, but only one refuting reply at the opponent's levels. The two requirements alternate, so full branching occurs at every other level, giving \( b^{d/2} \) leaves from each player's perspective, minus 1 for the shared principal leaf. The consequence is the famous headline, perfectly ordered alpha-beta searches twice as deep as minimax for the same leaf budget, since \( b^{d/2} \) leaves at depth \( d \) equals the cost of minimax at depth \( d/2 \). With random move ordering the exponent degrades to roughly \( 3d/4 \) (Pearl 1982), which is why every serious game program spends heavily on move ordering, transposition-table best moves first, then captures, then killer moves.

Measured on random trees with the implementation below (values drawn uniformly, fixed seed), for \( b = 3, d = 4 \), minimax evaluates all \( 3^4 = 81 \) leaves, alpha-beta with the arbitrary generated order evaluates 25, and after sorting children best-first it evaluates exactly \( 3^2 + 3^2 - 1 = 17 \), matching the formula. For \( b = 4, d = 6 \), minimax evaluates \( 4^6 = 4{,}096 \), unordered alpha-beta 1,173, perfectly ordered exactly \( 4^3 + 4^3 - 1 = 127 \), a 32-fold saving over minimax. Both runs returned the same root value in all three configurations, as soundness requires.

Expectimax, adversaries replaced by dice

When the opponent is not adversarial but stochastic (a die roll, a randomly moving hazard, a user model with known error rates), MIN nodes become chance nodes that average instead of minimize,

Two consequences separate expectimax from minimax. First, pruning in the alpha-beta style is mostly unavailable. An average can be moved by any single child, so no child can be skipped without bounds on the utility range (with known bounds \( [L, U] \), partial sums do yield prunable intervals, which is the *-minimax family). Second, minimax values are invariant under any strictly increasing transformation of the leaf utilities, because max and min care only about order. Expectimax is not, because averages care about magnitude. Utilities in stochastic domains must therefore be calibrated quantities, not arbitrary scores. Problem 2 makes both points concrete with numbers.

From alpha-beta to MCTS

Alpha-beta with a handcrafted evaluation carried game playing from the 1950s through Deep Blue's 1997 match (Campbell, Hoane, and Hsu describe searching roughly 100 to 200 million positions per second with hardware move generation). Go broke the recipe, with a branching factor near 250 and no cheap accurate evaluation. Monte Carlo tree search replaced the depth-limited exact backup with sampled playouts and a bandit rule at each node. UCT (Kocsis and Szepesvári, 2006) selects children maximizing \( \bar{Q}(s,a) + c \sqrt{\ln N(s) / N(s,a)} \), inheriting its logarithmic regret analysis from UCB1. AlphaGo and AlphaZero closed the loop by learning the evaluation and the move prior with neural networks trained from self-play, but the outer loop is still tree search, and the guarantee structure is still the classical one. Given enough simulations, MCTS values converge to minimax values. The lineage from the 1975 pruning analysis to the 2017 self-play systems is direct, and the deep-RL side of that story is covered in the deep reinforcement learning notes.

Markov decision processes as a modeling tool

From deterministic search to stochastic dynamics

Expectimax over an infinite horizon with discounting is a Markov decision process. The model is a tuple \( (\mathcal{S}, A, P, r, \gamma) \), states, actions, a transition kernel \( P(s' \mid s, a) \), a reward function \( r(s, a, s') \), and a discount \( \gamma \in [0, 1) \). A policy \( \pi \) maps states to actions, and its value is the expected discounted return \( V^\pi(s) = \E \left[ \sum_{t=0}^{\infty} \gamma^t r_t \mid s_0 = s, \pi \right] \). Splitting the sum after its first term and using the Markov property gives the Bellman equation for a fixed policy, and taking the best first action gives the Bellman optimality equation,

This page uses the MDP as a modeling and planning tool and keeps the analysis at the level needed to trust the algorithms. Two facts are imported. The Bellman optimality operator is a \( \gamma \)-contraction in the sup norm, so value iteration converges to the unique fixed point \( V^* \) from any initialization at rate \( \gamma^k \). And policy iteration terminates in finitely many steps because each improvement step produces a strictly better policy until it reproduces the current one, and there are finitely many deterministic policies. Both proofs, together with the error bound \( \| V_k - V^* \|_\infty \le \tfrac{2\gamma \epsilon}{1 - \gamma} \) for the greedy policy at stopping tolerance \( \epsilon \) and the full theory through TD learning and policy gradients, are written out in the reinforcement learning foundations notes. Bellman (1957) and Puterman (1994) are the primary sources.

Value iteration on a gridworld, with real iterates

The test MDP is a 4×4 gridworld. Rows are numbered 0 (top) to 3, columns 0 to 3. Cell (1,1) is a wall. Entering (0,3) ends the episode with reward +1, and entering (1,3) ends it with reward −1. Every other step costs −0.04 (a living penalty that makes dawdling expensive), and \( \gamma = 0.95 \). Actions are the four compass moves, but the floor is slippery. The intended direction happens with probability 0.8, and the agent slips perpendicular (each side) with probability 0.1. Moving into a wall or off the grid leaves the state unchanged.

        col:   0     1     2     3
      row 0  [ . ] [ . ] [ . ] [ +1]
      row 1  [ . ] [ # ] [ . ] [ -1]
      row 2  [ . ] [ . ] [ . ] [ . ]
      row 3  [ . ] [ . ] [ . ] [ . ]

Value iteration initializes \( V_0 = 0 \) (terminals fixed at their exit rewards) and repeatedly applies the optimality backup. The first sweep at state (0,2), the cell left of the +1 exit, is worth doing by hand. Take action Right. With probability 0.8 the agent enters the terminal, collecting \( -0.04 + 0.95 \cdot 1.0 = 0.91 \). With probability 0.1 it slips up, hits the wall boundary, stays at (0,2), collecting \( -0.04 + 0.95 \cdot 0 = -0.04 \). With probability 0.1 it slips down into (1,2), also \( -0.04 \). So \( Q_1((0,2), R) = 0.8 (0.91) + 0.1 (-0.04) + 0.1 (-0.04) = 0.728 - 0.008 = 0.72 \), and no other action does better, so \( V_1(0,2) = 0.72 \). The code's first sweep prints exactly 0.7200. The second sweep uses \( V_1 \) in the backup. For (0,2) the slip-down successor (1,2) still holds \( -0.04 \) and the stay-in-place successor now holds 0.72, giving \( 0.8(0.91) + 0.1(-0.04 + 0.95 \cdot 0.72) + 0.1(-0.04 + 0.95 \cdot (-0.04)) = 0.728 + 0.0644 - 0.0078 = 0.7846 \), again matching the run. The full trajectory of six representative states comes straight from the program's output.

The propagation is visible in the table. Value flows outward from the +1 exit one sweep per step of graph distance (states four moves away are still at the accumulated living penalty after sweep 2, positive by sweep 10), and convergence to \( 10^{-10} \) takes 51 sweeps, consistent with the contraction rate \( \gamma^k = 0.95^{51} \approx 0.073 \) multiplied down from an initial error of order 1 and the tighter effective rate that short paths to terminals induce. The greedy policy read off the converged values is shown below.

      row 0:   R    R    R   [+1]
      row 1:   U    #    U   [-1]
      row 2:   U    L    U    D
      row 3:   U    U    U    L

Two entries reward inspection. At (2,3), directly below the −1 exit, the policy moves down, away from the goal side, because moving up enters −1 with probability 0.8 and even moving left risks a 0.1 slip upward into it. Retreating and approaching along column 2 is worth more in expectation. At (2,1), below the wall, the policy goes left to join the safe western corridor rather than squeezing past the −1 exit on the east side. Both are the kind of slip-aware detour that separates an MDP solution from a shortest path. A deterministic planner on the same map would hug the wall. Policy iteration on the same MDP, started from the all-Up policy with exact evaluation at each round, converged in 5 improvement rounds to the identical policy, and its value function matches value iteration's to six decimals, \( V(3,0) = 0.378584 \) from both. Five rounds versus 51 sweeps is the standard trade. Policy iteration takes few, expensive iterations (each one solves a linear system), value iteration many cheap ones.

Constraint satisfaction

The formalism, and why factored states change the game

A constraint satisfaction problem (CSP) is a triple \( (X, D, C) \), variables \( X_1, \ldots, X_n \), a finite domain \( D_i \) for each, and constraints, each a relation over a subset of variables specifying which joint assignments are allowed. A solution assigns every variable a value from its domain such that all constraints are satisfied. Deciding satisfiability of a general CSP is NP-complete (graph 3-coloring is already a CSP), so the interesting content is not a polynomial algorithm but a set of techniques that make the exponential search dramatically smaller in practice, plus identified tractable islands where polynomial algorithms do exist.

The structural difference from state-space search is that CSP states are factored. An assignment is a vector of variable values, not an opaque atom, and constraints touch only a few variables each. Two consequences follow. The first is commutativity, the order in which variables get assigned does not matter to the solution set, so search need only consider one variable per depth, shrinking the tree from \( n! \, d^n \) leaves (choosing which variable and which value at every level) to \( d^n \). The second is local reasoning, a constraint on \( (X_i, X_j) \) can eliminate values from \( D_i \) by looking only at \( D_j \), before and during search. Everything below is a combination of those two ideas.

Backtracking and forward checking, worked

Backtracking search is depth-first search over partial assignments. Pick an unassigned variable, try each domain value that is consistent with the assignments so far, recurse, and unwind on failure. Forward checking strengthens it. After assigning \( X_i = v \), delete from the domain of every unassigned neighbor the values inconsistent with \( v \), and if any domain empties, fail immediately instead of discovering the dead end several levels deeper. Here is a concrete run on a 5-region map coloring with colors \( \{r, g, b\} \) and adjacency A–B, A–C, B–C, B–D, C–D, D–E.

        A ─── B                assign A=r:  D(B)={g,b}  D(C)={g,b}
        │ ╲   │                assign B=g:  D(C)={b}    D(D)={r,b}
        │   ╲ │                assign C=b:  D(D)={r}
        C ─── D ─── E          assign D=r:  D(E)={g,b}
                               assign E=g:  solution (r,g,b,r,g)

Five assignments, zero backtracks. Each forward check funneled the next domain to almost a single choice. Plain backtracking on an unluckier ordering can assign A=r, B=g, then E=r, then hit the C/D conflict and thrash; the standard measure of this effect (Haralick and Elliott, 1980) is that forward checking prunes at the earliest point a single constraint can detect failure, while backtracking without it detects failure only when both endpoints of a constraint are assigned.

Variable and value ordering compound the savings. MRV (minimum remaining values) picks the unassigned variable with the smallest current domain, the most constrained variable, the one most likely to fail, and failing early is cheap. In the trace above, after A=r and B=g, MRV selects C because its domain is the singleton \( \{b\} \), exactly the forced move a human would make. A common tie-breaker is the degree heuristic, preferring the variable constraining the most other unassigned variables. LCV (least constraining value) orders values within the chosen variable by how few options they eliminate from neighbors, keeping flexibility for the rest of the search. The asymmetry is deliberate. Variables should be chosen to fail fast (all of them must eventually be assigned anyway), but values should be chosen to succeed, since only one value needs to work.

Arc consistency and AC-3, step by step

An arc \( (X_i, X_j) \) is consistent if every value in \( D_i \) has at least one supporting value in \( D_j \) compatible with the constraint between them. AC-3 (Mackworth, 1977) makes every arc consistent by fixed-point iteration. Hold a work queue of arcs. Pop \( (X_i, X_j) \) and delete from \( D_i \) every value with no support in \( D_j \). Whenever \( D_i \) shrinks, re-enqueue all arcs \( (X_k, X_i) \) pointing into \( X_i \), because their support may have just disappeared. The run below is the actual trace printed by the implementation in the code section, on the CSP with variables \( X, Y, Z \), each domain \( \{1, 2, 3\} \), and constraints \( X < Y \) and \( Y < Z \).

   initial queue: (X,Y) (Y,X) (Y,Z) (Z,Y)

   1  revise(X,Y): X=3 has no y>3 in D(Y)     remove {3}    D(X)={1,2}
   2  revise(Y,X): Y=1 has no x<1 in D(X)     remove {1}    D(Y)={2,3}   enqueue (Z,Y)
   3  revise(Y,Z): Y=3 has no z>3 in D(Z)     remove {3}    D(Y)={2}     enqueue (X,Y)
   4  revise(Z,Y): Z=1,2 have no y<them       remove {1,2}  D(Z)={3}
   5  revise(Z,Y): no change
   6  revise(X,Y): X=2 has no y>2 in D(Y)={2} remove {2}    D(X)={1}

   fixed point after 6 revise calls: D(X)={1}, D(Y)={2}, D(Z)={3}

The final domains are singletons, so arc consistency alone solved this instance. That is a property of this instance (a chain, hence a tree, see below), not of AC-3 in general. Arc consistency can leave large domains that still contain no joint solution. Three variables pairwise constrained to be unequal with domains \( \{1,2\} \) are perfectly arc consistent (every value has a support in each neighbor separately) yet unsatisfiable. Consistency is a local property, while satisfiability is global.

On complexity, with \( e \) arcs and domain size \( d \), an arc \( (X_i, X_j) \) re-enters the queue only when \( D_j \) loses a value, at most \( d \) times, and each revise call checks at most \( d^2 \) value pairs, so AC-3 runs in \( O(e\, d^3) \). AC-4 achieves the optimal \( O(e \, d^2) \) by maintaining explicit support counts, at the price of a heavier data structure that is often slower in practice. This trade (recompute cheaply versus index exhaustively) recurs across the field. Running AC-3 inside backtracking search after every assignment is the MAC algorithm (maintaining arc consistency), strictly stronger than forward checking, which is precisely AC-3 restricted to the arcs pointing at the just-assigned variable's neighbors.

The tree-structured CSP theorem

Theorem (Freuder, 1982). A binary CSP whose constraint graph is a tree can be solved, or proved unsatisfiable, in \( O(n\, d^2) \) time. Proof by construction. Root the tree anywhere and order the variables \( X_1, \ldots, X_n \) so that every node appears after its parent (a topological order of the rooted tree). Sweep backward from \( X_n \) to \( X_2 \), making each arc \( (\text{parent}(X_i), X_i) \) consistent. Each of the \( n - 1 \) arcs is processed once at cost \( O(d^2) \), and crucially, later revisions cannot break earlier ones, because making \( (\text{parent}, X_i) \) consistent only shrinks the parent's domain, and the arcs processed after it in the backward sweep are strictly closer to the root, involving only ancestors, never \( X_i \) again. This is where treeness is used. No arc points back into an already-processed subtree, because there are no cycles. If any domain empties, report unsatisfiable. Otherwise sweep forward, assigning \( X_1 \) any remaining value and each \( X_i \) any value consistent with its parent's assignment. Such a value exists by the arc consistency just established, so the assignment never backtracks. \( \square \)

The theorem is the seed of a large theory. Cutset conditioning solves near-tree problems by enumerating assignments to a small set of vertices whose removal leaves a forest, paying \( O(d^c) \) for a cutset of size \( c \) and \( O((n-c) d^2) \) for the rest. Tree decomposition generalizes further. Any CSP is solvable in time exponential only in the width of its best tree decomposition, and the same notion of induced width governs exact inference in graphical models, a correspondence developed at length in Dechter's Constraint Processing (2003) and mirrored on the graphical models page, where the identical mathematics appears as variable elimination and junction trees.

Local search and simulated annealing

Hill climbing and its failure modes

When the path to a solution is irrelevant and only the final configuration matters (CSP solutions, layouts, schedules), search can operate on complete assignments. Start anywhere, repeatedly move to a neighboring assignment that improves an objective, stop at a local optimum. Memory is \( O(1) \) and progress per step is fast. The failure modes are the geometry of the landscape, local maxima, plateaus (flat regions where greedy guidance vanishes), and ridges (ascent directions not aligned with any single move). Random restarts fix local maxima in expectation. With success probability \( p \) per restart, the expected number of restarts is \( 1/p \). Sideways moves help with plateaus but need a cap to avoid infinite wandering. For CSPs specifically, the min-conflicts heuristic (pick a conflicted variable, assign it the value minimizing the number of violated constraints) solves random large n-queens instances in a nearly constant number of steps even for a million queens, a striking empirical fact explained by the density of solutions in that particular landscape rather than by any general guarantee.

Simulated annealing and the Boltzmann acceptance rule

Simulated annealing (Kirkpatrick, Gelatt, and Vecchi, 1983, imported from the Metropolis algorithm of statistical mechanics) escapes local optima by accepting downhill moves with a probability that decays with how bad they are and with time. At temperature \( T \), a proposed move with objective change \( \Delta E \) is accepted with probability 1 if it improves, and with probability \( e^{\Delta E / T} \) if it worsens (for a maximization problem, \( \Delta E < 0 \) for a worsening move). The specific exponential form is not arbitrary. With symmetric proposals, this acceptance rule satisfies detailed balance with respect to the Boltzmann distribution \( \pi_T(x) \propto e^{E(x)/T} \), because

both sides equaling \( \min(\pi_T(x), \pi_T(x')) \) after multiplying through. The chain therefore samples \( \pi_T \) at equilibrium, and as \( T \to 0 \), \( \pi_T \) concentrates on global maxima. The classical asymptotic guarantee, cooling no faster than \( T_k = c / \log(k+1) \) reaches a global optimum with probability 1, is far too slow to use. Practical schedules cool geometrically and settle for good local optima. The detailed-balance argument here is the same one behind Metropolis-Hastings MCMC, derived fully on the graphical models page. Annealing is MCMC with the target distribution sharpened over time. The lineage runs forward too. Annealed schedules and temperature-controlled acceptance reappear in modern samplers and in the exploration schedules of deep RL.

Propositional logic and SAT

Entailment, resolution, and a worked refutation

A knowledge base \( KB \) entails a sentence \( \varphi \), written \( KB \models \varphi \), if every truth assignment satisfying \( KB \) also satisfies \( \varphi \). The computational route to entailment is refutation. \( KB \models \varphi \) if and only if \( KB \wedge \neg\varphi \) is unsatisfiable, which reduces logical questions to satisfiability checking on conjunctive normal form (CNF), a conjunction of clauses, each clause a disjunction of literals. The single inference rule needed is resolution. From clauses \( (A \vee x) \) and \( (B \vee \neg x) \), conclude the resolvent \( (A \vee B) \). Soundness is a two-case argument. Any model of both premises assigns \( x \) either true, in which case \( B \vee \neg x \) forces \( B \) to hold, or false, in which case \( A \vee x \) forces \( A \), and either way \( A \vee B \) holds. Resolution is also refutation-complete (Robinson, 1965). If a clause set is unsatisfiable, some sequence of resolutions derives the empty clause. This is completeness for refutation, not for generation. Resolution cannot derive every entailed sentence directly, but it can always confirm one by refuting its negation.

DPLL, backtracking plus unit propagation

The Davis-Putnam procedure (1960) eliminated variables by resolving all clause pairs on them, which explodes memory. Davis, Logemann, and Loveland (1962) replaced elimination with splitting, and the resulting DPLL skeleton is still the core of every modern solver. DPLL is backtracking search over truth assignments with two deduction rules applied at every node. The first is unit propagation. If a clause has all but one literal false, the last literal must be true, so assign it and repeat, since each assignment can create new unit clauses. The second is pure literal elimination, where a variable appearing with only one polarity can be set to satisfy all its clauses. A short trace on the clause set

branching on \( a \) true first, unit propagation fires in a cascade. \( (\neg a \vee b) \) forces \( b \), then \( (\neg b \vee c) \) forces \( c \), then \( (\neg c \vee \neg a) \) is violated with every literal false, a conflict, so backtrack. Branch \( a \) false, and \( (a \vee b \vee c) \) shrinks to \( (b \vee c) \), no unit yet. Branch \( b \) true, and \( (\neg b \vee c) \) forces \( c \), and all four clauses check out, satisfiable with \( (a, b, c) = (F, T, T) \). Two decisions, one conflict, and propagation did most of the assigning, which is the empirical signature of DPLL on real instances. Decisions are rare, propagations are the bulk of the work, and the engineering of propagation (watched literals, below) determines solver speed.

CDCL, learning from conflicts

Modern solvers extend DPLL with conflict-driven clause learning, developed in GRASP (Marques-Silva and Sakallah, 1999) and made fast in Chaff (Moskewicz, Madigan, Zhao, Zhang, and Malik, 2001). The pieces fit together as follows. Every propagated assignment records the clause that forced it, forming an implication graph. On conflict, the solver walks the graph backward from the violated clause to find a cut separating the decisions from the conflict, typically at the first unique implication point (1UIP), the assignment nearest the conflict through which all paths from the current decision pass. Negating the cut yields a learned clause that is entailed by the original formula (it is derivable by a sequence of resolutions along the graph edges, so soundness is inherited from resolution) and that the current assignment violates, so it prevents this conflict from ever recurring. The solver then backjumps, not to the previous decision level but to the second-highest level in the learned clause, where the clause is unit and immediately propagates, so search restarts in a provably new region. Around this core, Chaff added the two-watched-literal scheme (each clause is monitored through just two literals, so propagating an assignment touches only the clauses where a watched literal died, making backtracking free) and the VSIDS decision heuristic (per-literal activity counters bumped at conflicts and decayed over time, focusing decisions on the variables involved in recent conflicts). Restarts with learned clauses retained round out the standard recipe. The practical effect is substantial. Industrial instances with millions of variables solve routinely, and CDCL solvers are the engine inside SMT solvers such as Z3, which layer theory reasoning (arithmetic, arrays, bitvectors) on top of the propositional core. As a theoretical footnote, CDCL with restarts polynomially simulates general resolution, so clause learning is not a heuristic hack but a proof system upgrade over tree-like DPLL.

Bayesian networks as a modeling tool

One worked enumeration query

A Bayesian network factorizes a joint distribution as \( \prod_i P(X_i \mid \text{Parents}(X_i)) \) over a DAG. The full theory (d-separation, variable elimination, junction trees, sampling) lives on the graphical models page. Here the network is used the way the classical toolkit uses it, as a compact model that answers queries by summing out hidden variables. The running model is a small diagnostic network for a service outage.

      Overload (O)      DiskFault (D)         P(O)=0.30   P(D)=0.10
             └─────┬───────┘
                 Crash (C)                    P(C|O,D)=0.99  P(C|O,¬D)=0.70
             ┌─────┴───────┐                  P(C|¬O,D)=0.80 P(C|¬O,¬D)=0.05
        PageAlert (P)  EmailAlert (E)         P(P|C)=0.90  P(P|¬C)=0.10
                                              P(E|C)=0.70  P(E|¬C)=0.05

Ten independent numbers replace the \( 2^5 - 1 = 31 \) a raw joint table needs, and the saving scales exponentially with network size, which is the entire point of the representation. Inference by enumeration answers any query by summing the factored joint over the hidden variables. Problem 5 works one such query end to end, and the code section verifies the arithmetic by brute-force summation over all 32 atomic events.

Particle filtering

The recursive Bayes filter, and where the weights come from

Tracking a hidden state over time combines two models, a motion (transition) model \( P(x_t \mid x_{t-1}) \) and a sensor model \( P(z_t \mid x_t) \). The belief \( b_t(x) = \P(x_t = x \mid z_{1:t}) \) obeys a two-step recursion derived from the law of total probability and Bayes' rule,

When the state space is huge or continuous, the belief is approximated by \( N \) weighted samples (particles). The particle filter implements the recursion by importance sampling. Propagate each particle through the motion model (this samples from the prediction \( \bar{b}_t \), so the proposal equals the prior), then weight each particle by the sensor likelihood \( w^{(i)} = P(z_t \mid x^{(i)}) \), which is precisely the importance ratio between target \( b_t \propto P(z_t \mid x) \bar b_t(x) \) and proposal \( \bar b_t \). Resampling \( N \) particles proportional to weight then equalizes the weights and concentrates particles where the posterior has mass, preventing the weight distribution from degenerating over time. The bootstrap form of this algorithm is due to Gordon, Salmond, and Smith (1993), with the general sequential Monte Carlo framework in Doucet, de Freitas, and Gordon (2001). The standard degeneracy diagnostic is the effective sample size \( N_{\text{eff}} = 1 / \sum_i (\tilde{w}^{(i)})^2 \) over normalized weights, which equals \( N \) when weights are uniform and 1 when one particle carries everything. Resampling when \( N_{\text{eff}} \) falls below \( N/2 \) is common practice.

At scale the same arithmetic sharpens a posterior no single reading could. Run the implementation below with 1,000 particles on the corridor, uniformly initialized. After one door reading the mass concentrates on the three doors (0.288, 0.302, 0.297 at cells 1, 4, 7, where the exact filter gives 0.291 each). After moving right (80 percent one cell, 10 percent stay, 10 percent two cells) and sensing door again, the three-way symmetry persists because the door spacing is symmetric. A third step sensing no door shifts mass to the cells just past each door (0.212, 0.218, 0.225 at cells 2, 5, 8 against the exact filter's 0.220 each, and every particle-filter cell estimate lands within 0.015 of the exact posterior). Breaking the symmetry requires either irregular door spacing or more steps. The worked example is small enough to see every mechanism and the code is exact enough to check against the closed-form filter, which is the discipline this page applies throughout.

Where the classical toolkit sits in a modern agent stack

The classical algorithms survive in two forms, literally, inside production systems that need guarantees, and structurally, as the skeleton of systems built around learned components. Among the literal survivals, constraint programming and SAT run scheduling, timetabling, chip verification, and policy checking (OR-Tools CP-SAT, whose engine is a clause-learning SAT solver extended with integer reasoning, Z3 and CVC5 in program verification, and CDCL solvers in equivalence checking for hardware). A*, D* Lite, and bounded-suboptimal variants run navigation in robots and games. Particle filters run localization in consumer robots. Every one of these deployments is chosen precisely for the property the proofs in this page establish. The answer is right, or its suboptimality is bounded, and failure is detectable.

The structural survivals are more interesting. An LLM-based agent choosing a sequence of tool calls is executing a search problem. States are conversation-plus-environment configurations, actions are tool invocations, and the policy proposing actions is a learned successor generator. Tree-of-thoughts style deliberation is best-first search where the language model plays both successor function and heuristic evaluator (Yao et al., 2023). Sampling several rollouts and keeping the best is a stochastic beam. A reflection step that rejects a partial plan is a pruning rule, sound only to the degree the evaluator is calibrated, which is exactly the admissibility question in new clothing. AlphaZero made the pattern explicit for games. MCTS provides the guarantees and the improvement operator, networks provide the priors and evaluations, and the combination is stronger than either. The same division of labor is visible in modern neuro-symbolic systems. AlphaGeometry (Trinh et al., 2024) couples a language model that proposes constructions with a symbolic deduction engine that verifies them, and LLM-modulo frameworks pair generators with exact verifiers, with the symbolic side contributing precisely what this page derives, soundness, completeness over the enumerated space, and certificates. The practical skill is recognizing which box of a hybrid system needs a guarantee, and knowing which classical tool provides it off the shelf.

Implementation, verified

Four self-contained Python programs produced every number quoted above. They are written for clarity over speed (plain dicts and heaps, no NumPy), because at this scale clarity wins. The largest run, uniform-cost search over 169,364 expansions, finishes in a couple of seconds. Each block is followed by the exact output of the run.

A* on the 8-puzzle with expansion counting

The search maintains g_best, the cheapest known path cost per state, and counts a node as expanded when popped with an up-to-date cost (stale queue entries are skipped, the standard lazy-deletion idiom for binary heaps). Passing h=0 gives uniform-cost search, and passing a weight gives weighted A*. The same successor function drives BFS and IDA*, so all optimal variants agreeing on cost 26 is a real cross-check, not four copies of one bug.

import heapq
from itertools import count

GOAL = (1, 2, 3, 4, 5, 6, 7, 8, 0)
NEIGH = {i: [j for j in range(9)                     # legal blank moves
             if abs(i//3 - j//3) + abs(i%3 - j%3) == 1] for i in range(9)}

def successors(state):                               # state: tuple of 9 ints
    z = state.index(0)
    for j in NEIGH[z]:
        s = list(state)
        s[z], s[j] = s[j], s[z]
        yield tuple(s)

def h_manhattan(state):
    d = 0
    for i, t in enumerate(state):
        if t:                                        # skip the blank
            gi = t - 1                               # tile t's home index
            d += abs(i//3 - gi//3) + abs(i%3 - gi%3)
    return d

def astar(start, h, w=1.0):
    tie = count()                                    # FIFO tie-breaking
    openq = [(w * h(start), next(tie), start, 0)]
    g_best = {start: 0}
    expanded = 0
    while openq:
        f, _, s, g = heapq.heappop(openq)
        if g > g_best.get(s, float("inf")):          # stale entry, skip
            continue
        expanded += 1
        if s == GOAL:
            return g, expanded
        for s2 in successors(s):
            g2 = g + 1
            if g2 < g_best.get(s2, float("inf")):
                g_best[s2] = g2
                heapq.heappush(openq, (g2 + w * h(s2), next(tie), s2, g2))

START = (4, 8, 2, 5, 0, 1, 3, 6, 7)                  # 60-step seeded scramble
for name, h, w in [("UCS", lambda s: 0, 1.0),
                   ("A* manhattan", h_manhattan, 1.0),
                   ("wA* w=2", h_manhattan, 2.0)]:
    cost, exp = astar(START, h, w)
    print(f"{name}: cost {cost}, expanded {exp}")

   UCS: cost 26, expanded 169364
   A* manhattan: cost 26, expanded 4598
   wA* w=2: cost 28, expanded 542

AC-3

The constraint dictionary maps each directed arc to a predicate, so an undirected constraint contributes two entries. The re-enqueue rule adds only arcs into the revised variable, excluding the arc just used, which is the detail that keeps the complexity at \( O(e d^3) \) rather than re-scanning everything.

from collections import deque

def ac3(domains, constraints):
    """domains: var -> list of values.
    constraints: (Xi, Xj) -> predicate ok(xi_val, xj_val), both directions."""
    queue = deque(constraints)                       # every arc once
    while queue:
        xi, xj = queue.popleft()
        removed = [x for x in domains[xi]
                   if not any(constraints[(xi, xj)](x, y) for y in domains[xj])]
        if removed:
            domains[xi] = [x for x in domains[xi] if x not in removed]
            print(f"revise({xi},{xj}): removed {removed}, D[{xi}]={domains[xi]}")
            if not domains[xi]:
                return False                         # domain wipeout
            queue.extend((a, b) for (a, b) in constraints
                         if b == xi and a != xj)     # arcs into Xi
    return True

doms = {"X": [1, 2, 3], "Y": [1, 2, 3], "Z": [1, 2, 3]}
cons = {("X", "Y"): lambda x, y: x < y, ("Y", "X"): lambda y, x: y > x,
        ("Y", "Z"): lambda y, z: y < z, ("Z", "Y"): lambda z, y: z > y}
print("consistent:", ac3(doms, cons), "final:", doms)

   revise(X,Y): removed [3], D[X]=[1, 2]
   revise(Y,X): removed [1], D[Y]=[2, 3]
   revise(Y,Z): removed [3], D[Y]=[2]
   revise(Z,Y): removed [1, 2], D[Z]=[3]
   revise(X,Y): removed [2], D[X]=[1]
   consistent: True final: {'X': [1], 'Y': [2], 'Z': [3]}

Value iteration and policy iteration on the gridworld

The MDP is exactly the 4×4 world specified earlier: wall at (1,1), +1 exit at (0,3), −1 exit at (1,3), living reward −0.04, slip 0.8/0.1/0.1, \( \gamma = 0.95 \). Terminal values are pinned to their exit rewards so terminals never bootstrap. Policy iteration reuses q_value for both evaluation (iterated to \( 10^{-12} \), a stand-in for the exact linear solve) and improvement.

ROWS = COLS = 4
WALL, TERM = {(1, 1)}, {(0, 3): 1.0, (1, 3): -1.0}
LIVING, GAMMA = -0.04, 0.95
ACT = {"U": (-1, 0), "D": (1, 0), "L": (0, -1), "R": (0, 1)}
PERP = {"U": "LR", "D": "LR", "L": "UD", "R": "UD"}
STATES = [(r, c) for r in range(ROWS) for c in range(COLS) if (r, c) not in WALL]

def move(s, a):
    r, c = s[0] + ACT[a][0], s[1] + ACT[a][1]
    return (r, c) if 0 <= r < ROWS and 0 <= c < COLS \
                     and (r, c) not in WALL else s

def q_value(V, s, a):                                # one-step lookahead
    pairs = [(a, 0.8)] + [(p, 0.1) for p in PERP[a]]
    return sum(pr * (LIVING + GAMMA * V[move(s, aa)]) for aa, pr in pairs)

def value_iteration(eps=1e-10):
    V = {s: TERM.get(s, 0.0) for s in STATES}
    sweeps = 0
    while True:
        sweeps += 1
        V2 = {s: TERM[s] if s in TERM
              else max(q_value(V, s, a) for a in ACT) for s in STATES}
        delta = max(abs(V2[s] - V[s]) for s in STATES)
        V = V2
        if delta < eps:
            return V, sweeps

V, k = value_iteration()
pi = {s: max(ACT, key=lambda a: q_value(V, s, a))
      for s in STATES if s not in TERM}
print(f"converged in {k} sweeps; V(3,0)={V[(3,0)]:.6f}")
print("policy row 2:", [pi[(2, c)] for c in range(4)])

   converged in 51 sweeps; V(3,0)=0.378584
   policy row 2: ['U', 'L', 'U', 'D']

A particle filter against the exact filter

The corridor world is small enough that the exact discrete Bayes filter (ten-entry belief vector) runs alongside the particle filter, so the Monte Carlo error is measurable rather than assumed. Systematic resampling (one uniform draw, \( N \) evenly spaced pointers) is used because it has lower variance than independent multinomial draws and costs \( O(N) \).

import random

DOORS = {1, 4, 7}
def lik(z_door, pos):                                # sensor model P(z|x)
    at = pos in DOORS
    return (0.8 if at else 0.05) if z_door else (0.2 if at else 0.95)

rng = random.Random(42)
N = 1000
particles = [rng.randrange(10) for _ in range(N)]    # uniform prior

def step(particles, z, moved):
    if moved:                                        # motion: +1 (.8) 0 (.1) +2 (.1)
        def jump(p):
            u = rng.random()
            return (p + (1 if u < 0.8 else 0 if u < 0.9 else 2)) % 10
        particles = [jump(p) for p in particles]
    w = [lik(z, p) for p in particles]               # importance weights
    tot = sum(w)
    stride = tot / N                                 # systematic resampling
    u = rng.random() * stride
    out, cum, i = [], w[0], 0
    for k in range(N):
        while cum < u + k * stride:
            i += 1
            cum += w[i]
        out.append(particles[i])
    return out

def histo(ps):
    return [round(sum(p == c for p in ps) / len(ps), 3) for c in range(10)]

particles = step(particles, True, moved=False)
print("after door:      ", histo(particles))
particles = step(particles, True, moved=True)
print("after move+door: ", histo(particles))
particles = step(particles, False, moved=True)
print("after move+nodoor:", histo(particles))

   after door:       [0.014, 0.288, 0.02, 0.014, 0.302, 0.017, 0.015, 0.297, 0.01, 0.023]
   after move+door:  [0.011, 0.246, 0.076, 0.013, 0.246, 0.072, 0.013, 0.235, 0.075, 0.013]
   after move+nodoor:[0.025, 0.009, 0.212, 0.11, 0.009, 0.218, 0.097, 0.008, 0.225, 0.087]

   exact filter:     [0.018, 0.291, 0.018, 0.018, 0.291, 0.018, 0.018, 0.291, 0.018, 0.018]
                     [0.006, 0.239, 0.078, 0.015, 0.239, 0.078, 0.015, 0.239, 0.078, 0.015]
                     [0.022, 0.007, 0.220, 0.096, 0.010, 0.221, 0.096, 0.010, 0.221, 0.096]

Worked problems

Six problems appear inline above (A* guarantees, expectimax risk, the cyclic CSP, resolution refutation, Bayes net enumeration, the particle update). Two more round out the set, one counting exercise and one counterexample construction.

How it is done in practice

Production search rarely runs the textbook loop unmodified, but the modifications are all recognizable from the theory. Game engines (Stockfish is the reference open implementation) run iterative-deepening alpha-beta with transposition tables, aspiration windows (search with a narrow \( (\alpha, \beta) \) window guessed from the previous iteration and re-search on failure), late-move reductions, and a static evaluation that since 2020 is a small neural network (NNUE) evaluated incrementally in integer arithmetic. The pruning soundness argument is unchanged, only the leaf values are learned. Robotics motion planners layer A* variants over lattice state spaces with anytime weighted schedules, and the localization stack in front of them is a particle filter with adaptive sample sizes. Planning systems compile factored action representations into heuristics automatically. The delete-relaxation heuristics inside Fast Downward are problem relaxations in exactly the sense derived earlier, computed by the machine instead of the modeler.

The solver world is further along the same road. CP-SAT in OR-Tools reformulates constraint programs over a lazy-clause-generation core. Propagators for integer constraints explain their prunings as clauses, which the CDCL engine then learns from, merging the AC-3 lineage and the GRASP/Chaff lineage into one solver. SAT solvers run portfolios with hundreds of heuristic settings and share learned clauses across parallel workers. SMT solvers sit inside compilers, symbolic-execution engines, and cloud infrastructure (AWS's Zelkova checks IAM policy questions by compiling them to SMT). The common engineering pattern across all of these is an exact core with proofs, wrapped in restarts, portfolios, learned orderings, and incremental data structures, with certificates (DRAT proofs for SAT, plans checked by validators) emitted so that downstream systems need not trust the solver's implementation, only its certificate checker.

The current research frontier

The active edge of classical search is mostly hybridization with learning. On the search side the theme is learned heuristics with retained guarantees. Training neural heuristics and then bounding them (or using them only for ordering, where mistakes cost time, not correctness) is a steady line of work across robotics and planning groups, and AlphaZero-style policy-guided tree search continues to expand beyond games into combinatorial optimization and theorem proving. DeepMind's AlphaGeometry and AlphaProof pair generative proposers with symbolic verifiers. The OpenAI and Anthropic reasoning-model lines internalize search as chain-of-thought sampling with learned self-evaluation, and the test-time-compute literature (best-of-n, tree-of-thoughts, process reward models guiding beam search) is an explicit rediscovery of heuristic search over reasoning states, with groups at Princeton, DeepMind, Meta AI, and Tsinghua among many others publishing variants. On the solver side, SAT research iterates through the annual competition cycle (CaDiCaL and Kissat, from Armin Biere's group at Freiburg, define the current single-core state of the art), with machine-learned branch ordering and restart policies appearing inside otherwise-exact solvers. Verified certificates keep pace. DRAT proof checking is now standard, and the 2016 Boolean-Pythagorean-triples result (Heule, Kullmann, and Marek) produced a 200-terabyte proof, checked mechanically. In MDP land, the planning-and-learning boundary is the frontier itself. The deep RL notes track it, and the classical side contributes the baselines that still win when models are exact and state spaces are enumerable.

Open source to read

• aimacode/aima-python, reference implementations of nearly every algorithm on this page in readable Python. Start with search.py and csp.py.
• python-constraint/python-constraint, a small pure-Python CSP library. constraint/solvers.py shows backtracking, MRV, and forward checking in a few hundred lines.
• google/or-tools, industrial constraint programming and routing. Read ortools/sat/cp_model.proto for the modeling surface and the ortools/sat/ directory for the lazy-clause-generation engine.
• Z3Prover/z3, the most widely deployed SMT solver. src/sat/sat_solver.cpp is a production CDCL core with watched literals and VSIDS-family heuristics visible.
• arminbiere/cadical, the cleanest modern competition SAT solver. src/propagate.cpp is the two-watched-literal scheme, heavily commented.
• niklasso/minisat, the classic minimal CDCL solver, about 2,000 lines. core/Solver.cc is still the best single file for learning clause learning.
• pysathq/pysat, Python bindings over a dozen SAT solvers plus cardinality encodings, useful for experimenting with encodings without touching C++.
• aibasel/downward, Fast Downward, the reference classical planner. The heuristic implementations under src/search/heuristics/ make relaxation-based heuristic design concrete.
• suragnair/alpha-zero-general, a compact AlphaZero reimplementation. MCTS.py shows the UCT selection rule and value backup in under 200 lines.

Common misconceptions

"A* is a fast algorithm." A* is optimally efficient, meaning no equally informed optimal algorithm expands fewer nodes. It is still exponential when the heuristic error grows with depth, and the measured table shows even a good heuristic expanding thousands of nodes on a toy puzzle. Feasibility comes from the heuristic, not the algorithm. A* merely guarantees nothing is wasted relative to what the heuristic knows.

"Alpha-beta returns an approximation of the minimax value." Alpha-beta returns exactly the minimax value of the tree it searches. The pruned subtrees are provably irrelevant to the root value. Approximation enters only through depth cutoffs and evaluation functions, which affect plain minimax identically.

"Making a CSP arc consistent solves it." Arc consistency is a local property. Three variables pairwise constrained unequal over domains of size two are fully arc consistent and unsatisfiable. AC-3 shrinks domains and detects some failures early. Search remains necessary in general, and the tree-CSP theorem marks the structural boundary where propagation alone suffices.

"SAT is NP-complete, so SAT solvers are impractical." NP-completeness is a worst-case statement. CDCL solvers routinely dispatch industrial instances with millions of variables because real formulas carry structure (community structure, small backdoors) that clause learning exploits. The hard instances near the random 3-SAT threshold are real but not what industry generates. The practical question is never "is it NP-hard" but "does my instance family have exploitable structure".

"Expectimax can be pruned like minimax." An average, unlike a minimum, can be moved by any child, so no child of a chance node can be skipped on ordering information alone. Pruning chance nodes requires a priori bounds on leaf utilities, and even then yields interval-based cutoffs weaker than alpha-beta's.

"Value iteration must converge before the policy is usable." The greedy policy typically becomes optimal long before the values settle. In the measured gridworld run the greedy policy is exactly optimal from sweep 12 of 51, while the values are still wrong in the second decimal place, and the \( 2\gamma\epsilon/(1-\gamma) \) bound quantifies exactly how loose the values can be while the policy stays near-optimal. Stopping early and acting greedily is usually correct engineering.

"More particles fix any particle filter." Particle count fights variance, not model mismatch. With a proposal far from the posterior (a very peaked sensor likelihood after a diffuse motion step), the weights degenerate no matter how many particles are used, and the fixes are structural, better proposals, low-variance resampling, or switching to a filter that exploits the model's analytic structure.

Self-check

References

1. Russell, S. and Norvig, P. Artificial Intelligence: A Modern Approach, 4th edition. Pearson, 2020.
2. Pearl, J. Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley, 1984.
3. Dechter, R. Constraint Processing. Morgan Kaufmann, 2003.
4. Bellman, R. Dynamic Programming. Princeton University Press, 1957.
5. Puterman, M. Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley, 1994.
6. Pearl, J. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann, 1988.
7. Thrun, S., Burgard, W., and Fox, D. Probabilistic Robotics. MIT Press, 2005.
8. Hart, P., Nilsson, N., and Raphael, B. "A Formal Basis for the Heuristic Determination of Minimum Cost Paths." IEEE Transactions on Systems Science and Cybernetics 4(2), 1968. doi:10.1109/TSSC.1968.300136
9. Korf, R. "Depth-First Iterative-Deepening: An Optimal Admissible Tree Search." Artificial Intelligence 27(1), 1985. doi:10.1016/0004-3702(85)90084-0
10. Knuth, D. and Moore, R. "An Analysis of Alpha-Beta Pruning." Artificial Intelligence 6(4), 1975. doi:10.1016/0004-3702(75)90019-3
11. Pearl, J. "The Solution for the Branching Factor of the Alpha-Beta Pruning Algorithm and Its Optimality." Communications of the ACM 25(8), 1982. doi:10.1145/358589.358616
12. Mackworth, A. "Consistency in Networks of Relations." Artificial Intelligence 8(1), 1977. doi:10.1016/0004-3702(77)90007-8
13. Freuder, E. "A Sufficient Condition for Backtrack-Free Search." Journal of the ACM 29(1), 1982. doi:10.1145/322290.322292
14. Haralick, R. and Elliott, G. "Increasing Tree Search Efficiency for Constraint Satisfaction Problems." Artificial Intelligence 14(3), 1980. doi:10.1016/0004-3702(80)90051-X
15. Kirkpatrick, S., Gelatt, C., and Vecchi, M. "Optimization by Simulated Annealing." Science 220(4598), 1983. doi:10.1126/science.220.4598.671
16. Davis, M. and Putnam, H. "A Computing Procedure for Quantification Theory." Journal of the ACM 7(3), 1960. doi:10.1145/321033.321034
17. Davis, M., Logemann, G., and Loveland, D. "A Machine Program for Theorem-Proving." Communications of the ACM 5(7), 1962. doi:10.1145/368273.368557
18. Robinson, J. A. "A Machine-Oriented Logic Based on the Resolution Principle." Journal of the ACM 12(1), 1965. doi:10.1145/321250.321253
19. Marques-Silva, J. and Sakallah, K. "GRASP: A Search Algorithm for Propositional Satisfiability." IEEE Transactions on Computers 48(5), 1999. doi:10.1109/12.769433
20. Moskewicz, M., Madigan, C., Zhao, Y., Zhang, L., and Malik, S. "Chaff: Engineering an Efficient SAT Solver." Proceedings of the 38th Design Automation Conference, 2001. doi:10.1145/378239.379017
21. Eén, N. and Sörensson, N. "An Extensible SAT-solver." Theory and Applications of Satisfiability Testing (SAT), 2003. doi:10.1007/978-3-540-24605-3_37
22. de Moura, L. and Bjørner, N. "Z3: An Efficient SMT Solver." Tools and Algorithms for the Construction and Analysis of Systems (TACAS), 2008. doi:10.1007/978-3-540-78800-3_24
23. Gordon, N., Salmond, D., and Smith, A. "Novel Approach to Nonlinear/Non-Gaussian Bayesian State Estimation." IEE Proceedings F: Radar and Signal Processing 140(2), 1993. doi:10.1049/ip-f-2.1993.0015
24. Doucet, A., de Freitas, N., and Gordon, N. (editors). Sequential Monte Carlo Methods in Practice. Springer, 2001.
25. Kocsis, L. and Szepesvári, C. "Bandit Based Monte-Carlo Planning." European Conference on Machine Learning (ECML), 2006. doi:10.1007/11871842_29
26. Campbell, M., Hoane, A. J., and Hsu, F. "Deep Blue." Artificial Intelligence 134(1-2), 2002. doi:10.1016/S0004-3702(01)00129-1
27. Silver, D. et al. "A General Reinforcement Learning Algorithm that Masters Chess, Shogi, and Go through Self-Play." Science 362(6419), 2018. doi:10.1126/science.aar6404
28. Yao, S., Yu, D., Zhao, J., Shafran, I., Griffiths, T., Cao, Y., and Narasimhan, K. "Tree of Thoughts: Deliberate Problem Solving with Large Language Models." NeurIPS, 2023. arXiv:2305.10601
29. Trinh, T., Wu, Y., Le, Q., He, H., and Luong, T. "Solving Olympiad Geometry without Human Demonstrations." Nature 625, 2024. doi:10.1038/s41586-023-06747-5
30. Heule, M., Kullmann, O., and Marek, V. "Solving and Verifying the Boolean Pythagorean Triples Problem via Cube-and-Conquer." Theory and Applications of Satisfiability Testing (SAT), 2016. doi:10.1007/978-3-319-40970-2_15