Gregory Friedman The Greg Wide Web on the name →

Case Study · AI · Search

Search at Play

2025–2026 · demo

The idea

In spring 2025 I spent a semester on exchange at the University of Essex, and CE 213, the AI course, walked the classical search curriculum in three steps: model a puzzle as a state space and flood it with breadth-first search, then add costs and a heuristic and watch A* outrun uniform cost, then add an opponent and let minimax turn search into play. The coursework was Java and Python: a river-crossing solver, an 8-puzzle solver run both ways, and a tic-tac-toe player with alpha-beta pruning.

The lab handouts belong to Essex and the graded code belongs to a gradebook, so this project republishes neither. Instead I rebuilt the three ideas from scratch for the browser, as plates you can poke: the same state spaces, the same algorithms, but with the part that made them click for me (watching the search actually move) promoted from print statements to the figure itself. All three live together at /search/; they are also embedded below, where the write-up discusses them, and a fourth plate at the end adds the pillar the labs never reached.

Uninformed: the river as a graph

The corn, goose and fox puzzle is the smallest state space worth drawing: four bits (corn, goose, fox, man), sixteen states, of which six are fatal because something gets eaten. The lab’s insight was that once you write the is_viable_state predicate, the puzzle stops being a riddle and becomes a graph reachability question. The rebuild draws that graph in full, at build time, and lets you walk it from the board: every crossing you make traces an edge, every blunder lands you on a struck-out node, and the solve button runs breadth-first search as a visible flood, layer by layer, seven crossings to the far bank. BFS is optimal here because every crossing costs the same; the first time the wave touches the goal, no shorter path can exist.

Left bank
Right bank

Everyone starts on the left bank. Ferry all three across without a meal being made.

cgfm|· cgf|m cgm|f cg|fm cfm|g cf|gm cm|gf c|gfm gfm|c gf|cm gm|cf g|cfm fm|cg f|cgm m|cgf ·|cgfm start goal

c corn · g goose · f fox · m the man with the boat · left|right of the river · struck states: something gets eaten

The whole puzzle, drawn: 6 of the 16 states are fatal, and the 10 safe ones leave only two corridors from start to goal, each 7 crossings long, meeting where the goose rides back. With JavaScript enabled this plate adds the board itself: row the cargo across, watch your path trace through this graph, or let breadth-first search flood it layer by layer.

Plate I The playable crossing and its complete state space. Six of the sixteen states are fatal; the ten safe ones leave two seven-crossing corridors, and both begin by rowing the goose.

Informed: paying for a heuristic’s opinion

The third lab replaced the river with the 8-puzzle, where the state space (181,440 reachable boards) is far too big to draw, and had us solve the same scrambled board twice: once with uniform-cost search and once with A* using a Manhattan-distance heuristic. My argument for that heuristic’s admissibility is still the one I would give: every legal move slides exactly one tile one square, so the sum of the tiles’ Manhattan distances can never overcount the moves remaining, and a heuristic that never overestimates preserves A*‘s optimality guarantee. On my laptop the difference was not subtle: the same 30-move solution in 99–155 ms for uniform cost against 15–51 ms for A*, a several-fold speedup from one good idea about distance.

The rebuild trades the 8-puzzle for a paintable grid world, because a grid makes the shape of the two searches visible in a way tile boards cannot: uniform cost grows a circle, A* grows a lobe that leans at the goal. Both panels run the identical routine; the only difference is whether Manhattan distance is added to the priority. That is not a rhetorical flourish, it is the actual code, which is why the heuristic toggle is the plate’s best argument: set h = 0 and the two panels expand cell for cell in the same order, because uniform cost simply is A* with nothing to say about the future.

Uniform-cost search and A* on the default grid world: nodes expanded and path cost.
searchexpandedpath cost
uniform cost9214
A* · Manhattan3814

Both searches, run at build time on this plate's default map: the same cheapest path (cost 14), but uniform cost settles 92 cells to A*'s 38, because the Manhattan heuristic keeps the frontier leaning toward the goal. With JavaScript enabled the map is paintable and both expansions replay side by side.

Paint
Run

Uniform cost

A* · Manhattan

shaded green: expanded, darker = earlier · ochre outline: frontier · green line: the cheapest path · hatched: swamp, step cost 5 · solid: wall

Plate II One world, two searches. Walls block, swamp costs 5 a step, and the counts under each panel keep the score. With Manhattan distance on, A* settles a fraction of what uniform cost does and still returns the same cheapest path.

Adversarial: search against someone

The minimax assignment was tic-tac-toe in Java, with alpha-beta pruning as the headline optimization. The lab’s closing question asked how much pruning helps, and the answer I wrote then still stands: against minimax’s O(b^d) nodes, alpha-beta examines roughly O(b^(d/2)) with good move ordering, but tic-tac-toe is so small that the stopwatch barely notices. The browser rebuild leans into that smallness instead of fighting it: rather than pruning the tree, it memoizes every position it meets, 5,478 distinct boards in all, so the “AI” is really a completed table of the game being read back.

What the plate adds to the assignment is the view I wanted while debugging mine: press Show the search and the tree from the current position opens underneath the board, every legal move labelled with its exact value, the replies to any option one hover away. It also makes the game’s central disappointment inspectable. Tic-tac-toe is a draw under best play, so the bot cannot be beaten, and the tree shows you why move by move: whatever you choose, at least one reply holds the value at zero or better for the bot. Losing to it stops feeling like bad luck and starts looking like a proof.

Minimax value of each kind of opening move in tic-tac-toe.
openingvalue under best play
centerdraw
cornerdraw
edgedraw

Solved at build time: minimax reaches 5,478 distinct positions from the empty board and values the game at 0, a draw. Every opening holds that draw. With JavaScript enabled this plate lets you play the table anyway, and open the search to see the value of every move you were offered.

Your move: you are X, the bot holds the table.

Plate III Tic-tac-toe against the completed table. Open the search to see your options valued, hover a square for the value of playing it, and watch the draw you were always promised arrive.

Constrained: a search with no path in it

The three plates above are all path problems. Breadth-first search wants a sequence of crossings, A* wants a route across a grid, minimax wants a line of play; in each case the answer is the walk, and the state you finish on is almost incidental. Constraint satisfaction is the fourth classical pillar and it inverts that. A CSP is a set of variables, a domain of possible values for each, and constraints saying which combinations are legal; a solution is an assignment, full stop. There is no route to report, no distance to a goal, no heuristic whose admissibility you have to argue. Whatever order you fill the variables in is scaffolding you throw away at the end, which means the structure worth seeing is not in a path but in the constraints, and in what they have already ruled out.

Sudoku is the standard specimen. It is 81 variables, a domain of 1 to 9 for each, and an all-different constraint on each of the 27 rows, columns and boxes; decompose all-different into “these two cells hold different digits” and you have 810 binary constraints, 20 touching every cell. Plain backtracking treats that as blind search: pick a cell, try a value, test it against the assigned cells sharing a unit, recurse, undo when everything fails. Forward checking does the same but strikes each value it commits to out of its 20 peers’ candidate sets, so it can abandon a branch the moment some cell has nothing left instead of finding out fifteen levels down. AC-3 is the full queue-driven arc-consistency algorithm: revise each arc in turn, asking whether every value in one domain still has support in its neighbour’s, and re-queue every arc pointing at a domain that shrank. On a not-equal constraint the answer is boring in a useful way, since a revision can only prune when the neighbour is down to one value, so AC-3 on a Sudoku is exactly the cascade of forced cells a human solver calls naked singles, followed as far as it will go.

All three run on one stepper, with the same cell order and the same tie-breaking, so any difference in the counters is caused by the lookahead and by nothing else. On the 24-clue puzzle the plate calls Stiff, filling cells in reading order, plain backtracking makes 572,844 assignments and 63,618 backtracks to reach a grid that forward checking reaches in 15,356 and AC-3 in 208: a factor of 2,754 between the two ends, with the amount of lookahead as the only difference between them. The second control is the one that surprised me, though. Switch from reading order to minimum remaining values, which simply branches on whichever cell has the fewest candidates left, and plain backtracking, unimproved in every other respect, goes from 14,479,949 assignments on the Awkward puzzle to 290, with no backtracks at all. Forward checking under the same heuristic finishes that grid in 57 assignments, which is precisely the number of empty cells: it never guesses wrong once. Propagation is worth a great deal, and deciding what to branch on is worth more.

The pencil marks are why this is a figure rather than a solver. Every empty cell draws its live candidate set, so propagation appears as digits quietly vanishing instead of as a line in a log. On the 34-clue Gentle puzzle arc consistency finishes the job by itself: 121 candidates over 47 empty cells collapse to exactly 47, one apiece, before anything is guessed, and the search that follows is transcription. On Stiff the same preprocessing leaves 192 candidates and only five forced cells, which is exactly why a search is still required. Plain backtracking’s grid keeps its candidate sets too, drawn but never consulted, so you can watch it labour underneath a cell whose cross went up thousands of steps ago. That is what “no lookahead” looks like from the outside. All three puzzles were dug out of random completed grids, and the build refuses to ship one unless an exhaustive count confirms it has exactly one solution, because a Sudoku with two answers would make every number under it meaningless.

Puzzle
Technique
Next cell
Run
Speed

24 clues placed. Striking them from their peers leaves 217 candidates across 57 empty cells, which is about 10^31.8 ways to fill the grid if the constraints stopped mattering. Press Step.

Assignments
0
Backtracks
0
Constraint checks
0
Arc revisions
0
Steps
0
Candidates left
217
Ways left to fill
10^31.8

ochre outline: the cell in hand · dashed outline: the cell that vetoed it · green tint: candidate sets that shrank this step · ochre tint and ×: a cell with no candidates left · small digits: the candidates still standing

The three techniques, run to the end

Assignments, backtracks and constraint checks for each technique on the same puzzle.
technique assignments backtracks constraint checks outcome
Backtracking 572,844 63,618 4,275,870 solved
Forward checking 15,356 11,111 109,434 solved
AC-3 208 113 12,912 solved

Stiff · 24 clues, in reading order, computed when this page was built. Backtracking pays 2,754 times as many assignments as AC-3 for the same grid. Race them again for any other puzzle and ordering.

Stiff · 24 clues: generated the same way as the others, dug a good deal further. Propagation no longer settles it, so all three techniques have to search, and the gap between them opens. Checked at build time, by an exhaustive count that stops at two, to have exactly one solution.

Plate IV Sudoku as a constraint satisfaction problem: 81 variables, nine values each, 810 binary not-equal constraints. Empty cells show the candidates they still have, and the counters keep score. Run one puzzle with each technique in turn, then change what the search branches on: minimum remaining values costs nothing and buys more than either kind of lookahead.

Where the rebuilds simplify, and what would complete them

The rebuilds simplify in four places, each a deliberate trade. The grid world’s open list is a scanned array rather than a binary heap, fine at a hundred cells and the first thing to replace one zoom level later; the replay animates a recorded expansion order rather than the live search, which preserves the order but hides the queue’s churn. The tic-tac-toe plate memoizes instead of pruning, which trades away the one technique the assignment emphasized; another plate racing alpha-beta’s node count against full minimax would complete the story, and is the natural next addition. The Sudoku plate takes the cheapest possible reading of all-different, chopping it into 810 binary not-equal constraints, which is why its AC-3 only ever finds naked singles; a real all-different propagator reasons about the whole unit at once and prunes a good deal harder, and offering one is what would bring the plate up to what modern constraint solvers do. And the river plate solves a graph of ten safe states, which is to say: it proves the method on a problem that never needed it. That is the point of lab problems, and the reason they make good plates, but the projects one shelf over (the durak searcher, which has to sample its opponent’s hidden hand) are where the same ideas stop being comfortable.

Keys on this page

A figure's keys are its own: they answer once the figure has focus, so tab to it or click it first. Esc closes this sheet.