Search agents and fork()

In 2009 the winning agent's edge was that its author had rebuilt the game's physics as a forward model. Here that is a method call:

const sim = tools.fork()      // a clone of the live world
sim.tick(BTN_RIGHT | BTN_RUN) // step it with a hypothetical input
sim.player.xPx                // read the future

A fork is a full, independent world. Stepping it does not touch the real one, and its results are exact — not an approximation of the physics, the physics, because it is the same code running the same integer arithmetic. Whatever you learn from a fork is true.

The catch is the budget: forked ticks cost the same as real ones, and you have 40 ms of CPU per tick. Search depth is the currency you are spending, and how you spend it is the entire strategic question.

Search over actions, not frames

The naive formulation is hopeless. Input is one byte, so 256 possible masks per frame, 60 frames per second: a one-second lookahead is 256⁶⁰ leaves. No heuristic saves that.

The move that works — Baumgarten's, in 2009 — is to search over held actions instead. One action is one button mask held for a fixed number of frames. The reference solver in @subpixel/agents uses thirteen of them, averaging about 9.5 frames each, which turns one second of game time into roughly six decisions instead of sixty.

The set is curated, not exhaustive:

Action	Mask	Frames	Why it exists
R, RR	right, right+run	4	travel; RR is what builds P-speed
RRJ8, RRJ16, RRJ24	right+run+jump	8 / 16 / 24	three genuinely different arcs — jump height is set by how long the bit stays held
RJ	right+jump	12	a walking jump clears a one-tile step without sailing over the ledge behind it
L, LR, LJ	left variants	4–12	backing up is not optional: a gap needing a running start is unreachable from a standing stop
J16	jump	16	vertical shafts, and hitting a block directly overhead
spin, waits	spin / none / down	varies	breaking turn blocks, bouncing off spiked enemies, waiting out a moving hazard

Because jump and spin are edge-triggered, an action that calls itself a jump has to guarantee a fresh press: macroFrame() clears the bit on frame 0 when the previous frame already held it, which costs nothing and turns frame 1 into a real press. See your first agent for what happens when you skip that.

Weighted A*, and what the reference solver measures

solve() in @subpixel/agents is a weighted A*: f = g + w·h, where g is frames elapsed and h is remaining distance divided by the best-case pixels-per-frame. Max P-speed oscillates 48, 47, 48, 47, 49 subpixels per frame, so dividing by 49/16 px keeps h from ever over-estimating on flat ground. The heuristic stays admissible; the weight is where optimality is deliberately traded for reach.

The weight was measured, not guessed. On the built-in test level at a 200,000-node cap:

Weight	Result
1.5	no solution — stalls at x 3546
2.0	no solution — stalls at x 3547
3	solved: 42.5k nodes, 3042 frames, ~6.7 s
4	solved: 53.5k nodes, 3105 frames, ~7.3 s

Hence DEFAULT_WEIGHT = 3, and a certification ladder of [3, 6, 12] — each rung greedier, and therefore reaching further, for levels the previous rung could not finish.

Two caps matter and they are not interchangeable. maxNodes is deterministic: the same level with the same cap gives the same answer on every machine. maxWallClockMs is advisory, for keeping an interactive caller from hanging — never let a decision that has to be reproducible depend on it.

Keying states, or: why your search revisits the same jump 400 times

Two worlds that differ by one subpixel are, for search purposes, the same world. Without deduplication the frontier fills with copies of one moment. The reference solver's key is worth stealing wholesale:

`${xPx >> 2}|${yPx >> 2}|${(vx16 >> 8) & 0xff}|${vy & 0xf8}|${powerup}|${inAir}|${riding}` +
`|${areaIndex}|${pMeter >> 4}` + hazardSignature(world)

Each term earns its place:

• Position quantized to 4 px and velocity coarsened — subpixel differences do not change what is reachable next.
• powerup, inAir, riding — a small player, a big player, and a player on a mount have different hitboxes and different options.
• areaIndex — the same coordinates inside a bonus room are not the same state as in the main area.
• pMeter >> 4 — P-speed is the difference between clearing a long gap and not, so it belongs in the key; the low bits do not.
• A hazard signature over nearby sprites, keyed to absolute cells rather than to offsets from the player, so that the same enemy in the same place hashes the same however you approached it.

Anything you leave out of the key, the search will happily prove to itself over and over. Anything you put in that does not change reachability multiplies your node count for nothing.

Prune states that cannot come back

The single largest reach improvement in the reference solver is three lines: treat "below the floor and still falling" as terminal, one tile above the engine's own death plane. The engine does not set dead until 32 px below the bottom row, and in that interval the player keeps drifting rightward through nothing, which reads as progress to a distance heuristic. Prune it:

function doomed(world: World): boolean {
  return world.player.yPx >= world.level.heightTiles * 16 - 16
}

Budget arithmetic

40 ms per tick is generous for JIT'd JavaScript and still finite. Some ways to spend it well:

• Plan rarely, execute for several frames. A search that produces a 40-frame plan and re-plans every 10 frames spends a quarter of the CPU of one that re-plans every frame, and in a deterministic world the plan does not rot unless something you did not model moves.
• Reuse the tree. After executing an action, the subtree under the action you took is still valid — its states were computed with the same physics you just experienced. Throwing it away every tick is the most common way to waste the budget.
• Drop worlds you have expanded. The reference solver nulls a node's world once its children exist; 200,000 live worlds do not fit in 512 MB, and a node only needs its parent link and the input bytes on the edge to reconstruct the log at the end.
• Watch the tail, not the mean. The hard kill is a single 200 ms tick, so a search that averages 12 ms but occasionally spikes will end your run at exactly the moment it mattered. Check your elapsed time inside the loop and return the best plan you have.

Exceeding the budget is not fatal to the run: the tick is recorded as a TIMEOUT and no further input is sent — the replay shows your agent standing still for the rest of the level, which is honest and a little bit funny.

Show your work

Everything emitted through tools.debug is recorded into the official replay and rendered by the replay viewer with per-channel toggles:

• debug.line/box/point/text(...) — world-space overlay primitives.
• debug.value(key, number | string) — time-series channels plotted under the canvas.
• debug.tree(nodes) — a search tree of { pos, parent, score }, rendered as the fan of branches ahead of the player.

The overlay is capped at 32 KB per tick and drops rather than failing when you exceed it. Use it: it is the fastest debugger you have, and the fan-out of a working search is the best-looking thing in this competition.