Gregory Friedman The Greg Wide Web on the name →

The Search Room

Search, at play

Three classical search problems from CE 213, the AI course I took on exchange at the University of Essex, rebuilt from scratch as things you can play with. The arc is the course's own: first a state space small enough to draw whole and flood with breadth-first search; then a space too big to draw, where a heuristic decides how much of it you visit; then an opponent, where search stops finding paths and starts finding moves. What each rebuild changes, and what the labs actually asked, is in the Search at Play case study.

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 corn, goose and fox crossing beside its complete state space: 16 states, six of them fatal (struck and dashed). Row the cargo across and your path traces live through the graph; Solve by BFS floods the safe states layer by layer and stops the moment it touches the goal, seven crossings out.
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 The same grid world solved twice: uniform cost on the left, A* with Manhattan distance on the right. Paint walls and swamp (step cost 5), drag the start and goal, and compare expanded counts; Replay animates both frontiers in lockstep. Set the heuristic to h = 0 and A* collapses into uniform cost, expansion for expansion.
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 exact minimax. Show the search opens the game tree from the current position: every option with its value, and the replies to whichever one you point at; hover an empty square for the value of moving there. The bot cannot be beaten, and the tree is the reason why.
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.

The first three had originals in Java and Python coursework: breadth-first search on this same four-bit river, uniform cost against A* on the 8-puzzle, and a minimax player with alpha-beta pruning. The fourth had no lab behind it; constraint satisfaction is the pillar the course never reached, and it is here because the other three kept pointing at it. These pages rebuild the ideas for the browser rather than republish the labs; the write-up at /projects/search-at-play/ keeps the honest numbers, including where the rebuilds take the easy road.

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.