Beam search is not monotonic, and it corrupted my measurements
A wider beam search is not a strictly better beam search. On one Sunny Sort level, width 45 finds a winning line, width 90 fails, and width 200 finds one again — and because every difficulty measurement in the project was asking "is this still winnable?" with a single width, the answer was wrong often enough to bias the whole curve.
How it surfaced
A level showed up as unsolvable during probing and solvable during generation. Same level, same move budget, two different verdicts from the same solver.
The difference was the beam width each stage happened to use.
| Beam width | Result |
|---|---|
| 45 | solves |
| 90 | fails |
| 200 | solves |
Why a wider beam can be worse
Beam search keeps the best k states at each depth and discards the rest. Widening k keeps more states — but it also changes which states are on the frontier, because the frontier is ranked by a heuristic, not by truth.
A winning line often passes through a state the heuristic scores poorly. At width 45 that state survives because there is little competition at its depth. At width 90 more candidates arrive, all of them scoring better on the heuristic and none of them leading anywhere, and the state that mattered gets pushed off the frontier.
More search, worse answer. The property people assume — that adding width can only help — is a property of exhaustive search, not of a truncated one.
What it cost before I noticed
The failure mode is asymmetric, and that is what makes it dangerous. A beam search never reports a win it cannot demonstrate, so a positive is trustworthy. A negative means only "this width did not find a line", which reads identically to "no line exists".
So the measurements were producing false negatives only:
- levels declared impossible that were winnable;
- decision width measured at 76% against a real 86% in the same configuration.
That second number is the one that stings. Decision width is the metric the whole pressure decision turned on — the share of legal moves that keep the win alive. A ten-point understatement pushes every judgement about how much freedom a level allows in the same direction, and nothing about the output looks suspicious. It is a plausible number, stated confidently, and wrong.
The fix
DepthProbe.Winnable and BestLine now try several widths before concluding anything. A level is only declared unwinnable when every attempted width failed; the best line is the best any of them found.
Both the analyzer and the generator's fairness check use the multi-width versions. No level is declared impossible because of a quirk in the solver.
The cost is search time, paid offline during generation, by a machine, once. The alternative was shipping levels that a player cannot beat and cannot be told why.
The part worth generalising
This is recorded in the design log with its own entry, not because the fix is interesting, but because of what kind of bug it is.
It never crashed. It never threw. It produced a number of exactly the right shape, in the right range, that a reasonable person would read and act on. Every decision made downstream of that measurement inherited the error silently — and the only reason it was caught at all is that two stages of the same pipeline happened to use different widths and disagreed out loud.
If a tool answers a question by searching, the width of the search is part of the answer. Ask it more than one way before you believe it.