We own a perfect
simulator.
So we search it.
A from-scratch agent that beats Super Mario Bros. on the NES — not by learning to play, but by searching a deterministic emulator for winning action sequences, then distilling what it finds into a tiny net. This is the whole story: the wins, the honest dead-ends, and how every piece maps to a frontier-lab interview.
★ I built this for fun — and to study for research-engineer interviews.Don't learn physics you can query.
Super Mario Bros. is fully deterministic. Given a state and a button press, the next state is fixed:
Because we own that function — and can snapshot & restore it for ~73 microseconds — we never need a neural network to predict the world. We can search the real emulator for a sequence of buttons that reaches the flag, then distill that expert trajectory into a fast reactive net. The net inevitably wanders into states the search never showed it — covariate shift — so we correct it by re-running search from its own failures and retraining. That loop is DAgger.
A snapshot button changes everything.
The whole approach rests on three properties of the NES emulator, each verified by a committed test.
Bit-identical replays
Two runs from the same seed reach byte-for-byte identical RAM. Golden hashes are committed so a ROM/emulator
regression turns a test red. tests/test_determinism.py — green.
Save / restore in 73µs
Every search node is a cloned emulator state. At ~1375 fps/core and 73µs round-trips, a beam can branch
thousands of futures per second. Snapshots can't be serialized across processes (Python pickle),
so the parallelization strategy is: run independent searches on separate cores, not parallel workers inside one search.
The setting picks the tool
A deterministic, resettable sim + a perfect oracle is the textbook home of search and reverse-curriculum RL — not blind model-free learning. Half the project was rediscovering this from first principles.
Deep dive — the gym wrapper's hidden fast-forward (a bug that cost four debugging rounds)
gym-super-mario-bros runs _skip_change_area / _skip_occupied_states
inside env.step(). So when Mario enters a pipe, the transition is fast-forwarded
before your code reads RAM. The transient signals ($06DE, $000E) are already
cleaned up — the detector is blind. Searches were entering pipes correctly and we were throwing the
successes away as "deaths." The fix: detect entries by the post-step x-position discontinuity
(live RAM vs. info.x_pos jumps >100px), or step the raw native frame
(sim.u._env.frame_advance) instead of the wrapped step. Lesson for an interview: verify your
instrumentation before you trust a negative result.
State representation & the death-aware reward.
Two design decisions here are load-bearing. Toggle the representations:
Ego-centric tile grid
A 13×16 grid of tiles around Mario — 5 channels: {empty, solid, mario, enemy, hazard} — plus 8 scalars. Always relative to Mario (never absolute x) so it generalizes across levels. Sees further ahead (11 tiles) than behind (4) — upcoming hazards matter more than passed ones.
gap_ahead+x_subtilerestore sub-tile timing the 16px grid quantizes away — the unlock for the first pit.- Used by the value net; simple, but a flat MLP on it caps at low completion rates when generalizing across levels.
grid[13×16] · channels = {EMPTY,
SOLID, ENEMY, MARIO, HAZARD}
scalars = [vx, vy, powerup,
on_ground, jumping, x_subtile,
in_water, gap_ahead]
OBS_DIM = 13·16·5 + 8 = 1048
Object-centric entity tokens
14 tokens × 17 features: 1 player + 5 enemy slots + 8 terrain columns. Each token carries relative position, velocity, type, ground-distance, pit-flag. Fed to a tiny transformer (mean-pooled).
- Compositional → a "enemy at (dx,dy)" concept transfers across levels far better than raw tiles.
- Fixes V4's empty-HAZARD bug: enemies are the hazards, encoded by type.
- 13× smaller than the flat MLP, higher val-acc (0.65 > 0.57) — yet representation was not the wall.
tokens = [player, enemy×5, terrain_col×8] feat = [is_P,is_E,is_T, dx,dy, vx,vy, etype, ground, on_gnd, jump, active, pit, pow, face, gap, xsub] OBS_DIM = 14·17 = 238 → Transformer
Death must be a hard negative
Score = +W·Δx + flag − death − stuck, where W is a scalar weight on rightward progress and Δx is the change in Φ. If death isn't dominant, Mario
jumps into pits because respawning one screen back still "scores OK." And you must ignore counter RAM
(score, coins, timer) — they give fake monotone progress and the agent humps a wall forever (the 1-2 coin-ledge trap).
The single most impactful fix
Mario's x_pos is area-local — it resets to ~40 when you enter a pipe. So a correct pipe entry
reads as a −1000px collapse, and search refuses it. Fix: a global progress coordinate.
Three search algorithms, one oracle.
Watch a beam keep only its top-k most-promising futures at each step, pruning the rest:
Each frame, every surviving node tries all 7 actions, scores the result with Φ, dedups near-identical states (16px buckets), and keeps the best k. Green = kept, faded = pruned. Reach the flag → return immediately.
Greedy frontier
Top-k by death-aware Φ score, with a stuck-cap (prune nodes that stop moving right). Solves linear levels
in seconds. Optional value_guide and policy_prior hooks — this is where the neural net
plugs in to accelerate search (see the thesis).
Go-Explore for mazes
Inspired by Go-Explore: instead of always pushing forward, archive every distinct cell visited and
periodically return to the least-explored ones. Here, cells are (area, x-tile, y-tile) — novelty
bonus keeps the search from looping forever. Cracked 4-2's warp-zone maze where plain beam's frontier emptied.
Per-room curriculum
Success = reaching a new area, not raw x. Keys cells on the $0750 pointer + an x-velocity
bucket so identical tiles at different speeds stay distinct. Solves multi-area pipe levels room by room.
The honest version — including where it broke.
Most write-ups hide the dead-ends. The dead-ends are the most interesting part — and the best interview material. Click through the milestones:
The levels that fought back.
Every hard castle and water level was a forensic investigation in RAM and 6502 disassembly. These are the "tell me about the hardest bug you've debugged" stories.
The net doesn't replace the search. It serves it.
After V4 and V5 failed to make a standalone learned controller, V6 inverted the goal. The literature is unanimous for this setting: search is the solver; learning's job is to guide it — the lesson of the Mario AI Championship (A* won), OpenAI's Sonic benchmark (replay heuristic beat from-scratch PPO), and AlphaZero.
Policy-guided beam — measured on 1-1
Use a weak net (0.19 completion rate as a standalone controller) only to rank actions; expand the prior's top-k at each node.
| configuration | nodes | time | result |
|---|---|---|---|
| plain beam, width 6 | 7,005 | 66.5s | ✓ solved |
| guided, width 6, top-3 | 2,770 | 30.8s | ✓ solved |
| plain beam, width 3 | 3,657 | 23.1s | ✓ solved |
| guided, width 3, top-2 | 642 | 5.1s | ✗ over-pruned |
Why not just train a controller?
Because it has a ceiling — and we proved it. With a deep-lookahead teacher, hazard-focal loss, and from-scratch balanced DAgger, standalone imitation on 1-1 caps at ~0.45–0.5 completion rate, and DAgger degrades it (0.48 → 0.22 on 1-1). The death-cliff covariate shift can't be cloned away from thin data.
- Representation isn't the bottleneck (entity-transformer hit the same wall).
- Temporal context (4-frame stacks): tested → no performance improvement.
- Tiny LLM/nanoGPT for control: researched → not worth it (LLM pretraining knowledge doesn't transfer to raw button timing; inference latency is also incompatible with real-time control).
- The productive lever is the prior. net serves search
Every concept here is an interview answer.
Frontier labs (June 2026) reportedly take <1% of applicants and weight visible work + honest reasoning over LeetCode. This project is a portfolio piece and a study deck. First, what each lab is actually screening for:
- "Be a coding machine" — pragmatic scalability, fast implementation.
- Move across product/eng boundaries, keep evaluation honest.
- 4–6h final loop, paper-discussion round sent in advance.
- 90-min CodeSignal screen demanding ~100% correctness.
- Safety / alignment reasoning is not box-checking — treating it as such fails the loop.
- Rigorous reference checks; ~half of technical staff have PhDs, plenty don't.
- "A PhD defense mixed with a rigorous engineering exam."
- Rapid-fire fundamentals (SVD, backprop, probability) — even seniors forget the formal defs.
- Research-scientist track expects a publication record.
Flashcards — tap to reveal the answer
The 9 interview categories → what in this project demonstrates them
STAR behavioral stories mined from this repo
Interview-prep framing synthesized from June-2026 write-ups by Sundeep Teki (RE guide), the 2026 hiring guide, and lab-by-lab signal differences.
Receipts.
Everything is reproducible: cached solutions replay to beat=True, contact sheets show the flag,
and the any% run stitches them into one continuous playthrough.
any% playthrough — 8/8 levels, beat_game=True
