Move: arrows or WASD Autoplay: SPACE One AI move: F Search depth: 1 2 3 New game: R POSITIONS in the HUD is how many boards the last AI decision looked at.
2048 with correct merge semantics and an expectimax AI that will play it for you, at a search depth you choose, showing you what the search cost. THE INTERESTING BIT The merge rule. A tile produced by a merge cannot merge again in the same move: 4 4 4 4 slid left is 8 8, not 16. Almost every clone gets this wrong, and it is usually because they implement it with an "already merged this move" flag that some code path forgets to check. Here there is no flag — the compacted line is scanned once and a merge advances the read cursor by two, so a freshly created tile is never looked at again. Wrong by construction is impossible. tools/verify.py pins the five cases that separate a correct 2048 from a clone and cross-checks the whole thing against an independent reference on 2,000 random boards in all four directions: 0 mismatches. Expectimax, not minimax. The spawn is random, so the opponent has no strategy to minimise against. The player's plies take the maximum; the spawn's plies take a probability-weighted average over every empty cell and both spawn values (2 at p=0.9, 4 at p=0.1). The evaluation is a snake weight matrix — the strongest cheap 2048 heuristic is "keep the tiles in serpentine order with the maximum in a corner", and a weight matrix that decreases monotonically along that path says exactly that without needing a separate monotonicity term — plus a bonus per empty cell and a smoothness penalty. Two Scratch-specific decisions carry the implementation: Tiles are stored as exponents, not values. 0 empty, 1 for the tile "2", 11 for "2048". A merge is e → e+1, and the smoothness term, which wants |log₂a − log₂b|, becomes a subtraction. Scratch has no integer log, so with raw values that term would need a log block and a division per adjacent pair, 24 pairs per leaf evaluation, on the hottest path in the project. goboscript locals are not per-invocation, and expectimax is recursive. A local compiles to an ordinary sprite variable with a mangled name, shared by every frame of a recursive call — the goboscript docs say locals in a recursive procedure are undefined behaviour. So every piece of frame state that must survive a recursive call lives in a list indexed by search level (sbest, sdir, sacc, scell, …). Because the level strictly increases with depth, one slot per level behaves exactly like a proper local. local is still used, but only where the value is written and read with no recursive call in between. The board stack works the same way: bd holds twelve 16-cell boards end to end, level 1 is the live game and the search writes into levels 2 upward. [What the search costs, measured] Positions examined for one decision on a mid-game board with 10 empty cells, from tools/proto.py, which implements the same rules and the same search: | depth | full 2+4 spawn | 2-spawn only | hybrid — what ships | |---|---|---|---| | 1 | 44 | 24 | 44 | | 2 | 2,892 | 781 | 1,528 | | 3 | 195,902 | 27,456 | 52,664 | The hybrid column is the one the project runs: the 4-spawn branch is expanded only at the chance node nearest the root, and deeper chance nodes assume a 2. That keeps the near-term value exact while cutting depth 3 from 196k positions to 53k — paying nearly 4× for a tenth of the probability mass, deep in the tree, is not a trade worth making inside Scratch. Cross-checked against the compiled .sb3 in the headless harness. All original - code, art and sound. See Inside is open.
