My puzzle game’s BFS solver reported an optimal solution of 13 moves for a
level the game itself could finish in 12. Both numbers came from the same rule
engine. The solver was not wrong about the rules — it was wrong about what
counts as « nothing happened ».
TL;DR — never decide that an action was a no-op by looking at the events it
emitted. Compare the state before and after. An action can change hidden state
while emitting only a « blocked » event, and an event-based prune will make that
action unreachable for the search.
What I expected
The solver explores actions with the usual guard against useless branches:
new_state, events = resolve(cur_state, action)
if not events:
continue
if all(e["type"] == "blocked" for e in events):
continue # "nothing happened", don't branch
That looked safe. A move into a wall emits [blocked] and changes nothing;
branching on it would just duplicate the parent state. Every test passed,
including a parity suite that checks this Python solver against its GDScript
twin on a corpus of levels — both agreed on solvability everywhere.
What actually happens
One mechanic broke the assumption. A jellyfish sting « stuns » the crab: the next
manual rotation is absorbed. In the engine that looks like this:
def try_manual_rotate(self, clockwise=True):
if self.stunned > 0:
self.stunned -= 1 # the sting wears off...
return False # ...but the gesture is spent, no rotation
if self.rotations_left <= 0:
return False
self.pincer = rotate_cw(self.pincer) if clockwise else rotate_ccw(self.pincer)
self.rotations_left -= 1
return True
A rotation attempted while stunned returns False, so the resolver emitted
[blocked] — and the state had changed: stunned went from 1 to 0. The prune
threw that branch away. The solver could therefore never spend a gesture to
purge the stun, and had to route around the jellyfish entirely: 13 moves
instead of 12. The parity suite never caught it because solvability was
identical; only the path length drifted, and only on levels where the optimal
path eats a sting.
The fix
Decide « no-op » by state, not by narration:
new_state, events = resolve(cur_state, action)
if not events:
continue
if (all(e["type"] == "blocked" for e in events)
and new_state.canonical_key() == cur_state.canonical_key()):
continue # a true no-op: same story AND same state
canonical_key() was already computed for BFS deduplication, so the extra cost
is one comparison. On my 552-level corpus the par table changed for exactly one
level (13 → 12), and re-checking all 552 confirmed no other drift.
We also gave the engine a distinct stun_spent event instead of blocked, so
the UI’s move counter and the undo log see the gesture too. That is the nicer
long-term shape — every state change gets an honest event — but the solver fix
is the one that matters: it holds even when the next silent mechanic forgets to
emit its own event type.
Why it works
An event stream is a rendering of the transition, written for the UI. The
search’s contract is with the state graph. Whenever the two disagree, the state
is the truth: pruning on events quietly bakes UI assumptions into the search,
and the failure mode is invisible — no crash, no unsolvable level, just optimal
paths that are slightly too long, which then poison anything derived from them
(star thresholds, difficulty scores, hint text).
Related: My optimal-solver tests all passed for a solver that was not
optimal, a different way the same solver
lied to me while every test stayed green.
What I did not test
Engines where hashing the full state per candidate is expensive — here the key
already existed for deduplication. And I only measured drift via the optimal
path length; if your engine has actions that change state and emit blocked
and never affect any optimal path, the bug can hide indefinitely.
Facts
context: BFS solver over a deterministic game rule engine (Python mirror of a Godot game)
problem: pruning actions whose events were all "blocked" skipped a rotation that silently consumed a stun counter, inflating optimal path lengths
solution: prune only when the event stream is all-blocked AND the canonical state key is unchanged; also emit a distinct event for the silent transition
verified_on: 2026-08-16
applies_to: [any search over a simulator that reports transitions as events, Python 3, Godot 4.7]
does_not_apply_to: [engines whose actions cannot mutate state without reporting it]