Exhibit 06Heuristic Search

8-Puzzle

Slide the tiles back to 1 2 3 / 4 5 6 / 7 8 _. Two ways to use Jev in search: let code run a beam search while Jev ranks boards (the pattern TypeSafe recommends), or ask Jev to count the moves left for A* (a stress test of a documented weakness). Both are compared with the textbook Manhattan distance.

Partly in scopeEstimating a distance is counting, a documented weakness; ranking boards with search in code is in scope. TypeSafe docs, Jev 1.13 jaggedness: “jev-1.13 does not count reliably.”
World
→
State
→
Decision
→
Action
→
New state
Optimal moves
Beam width

In scopeCode runs the search and keeps a visited set; Jev only answers a comparative Choice, “which of these boards is closest to being solved?”, for the unvisited successors of each board in the beam. A path scores the sum of log-probabilities; the best paths survive each step, with the beam widened (1, 2, 3, 5, 8, 13) and rankings reused whenever a pass fails, as in the benchmark. The baseline ranks the same options by Manhattan distance. Budget: 300 distinct Jev rankings. TypeSafe: keep control flow in code

1
2
3
4
5
6
7
8
Goal
blank last
Optimal solution
10 moves
Moves to goal now
10
Jev spend this session
0 calls · $0
This puzzle · beam search, Jev vs Manhattan ranking
run each ranker and width to fill in
Jev ranks · widening
not run
Manhattan · widening
not run
Jev ranks · width 3
not run
Manhattan ranks · width 3
not run
Jev ranks · greedy
not run
Manhattan ranks · greedy
not run
Jev ranks · widening
idle
Depth
—
Boards expanded
—
Rankings
—
Cost
—
Latest ranking

Run “Jev ranks”. Each call compares the unvisited successors of one board.

Jev decision

idle
Each Jev call ranks the successors of one board in the beam. The latest ranking appears here.
Lesson · Heuristics
Good estimates → less search
Two designs are on this page. In the ranking design, code owns the search (a beam of the most promising paths and a visited set) and Jev answers the one comparative question TypeSafe's guidance suggests: which of these few boards is closest to solved. Beam search is not guaranteed to find a solution, even with a good ranker, so the Manhattan-ranked beam on the same puzzle is the fair baseline. In the counting design, A* expands the board with the lowest f = g + h: moves made so far plus an estimate of moves left. If the estimate never overestimates, the first solution A* finds is a shortest one; the closer the estimate is to the truth, the fewer boards it has to look at. Misplaced tiles and Manhattan distance are the textbook estimates, and both provably never overestimate. Jev's estimate comes with no such guarantee, so A* guided by it may return a longer path. The scatter shows how far off it is, and in which direction; the chart shows what that costs in search. The + features level hands Jev the Manhattan distance itself, so there it is judged on whether it adds anything to a number it was given.