Chomp is a chocolate bar with a poisoned corner. A bite takes one square and everything down-and-right of it; whoever is forced to eat the poison loses. Three lines of strategy stealing prove the first player wins every bar bigger than a single square — and the proof computes nothing. It holds for bars no machine will ever solve, and it never names the move.
Seventy-two days in, this is the first page proved that way and the first whose state is a partition in a box. A position is a staircase: one height per column, weakly decreasing. That is C(n+m, m) positions — 184,756 for a 10×10, not 2¹⁰⁰ — and ranking them with a combinatorial number system makes every bite land at a strictly smaller index, so the entire table fills in one ascending for-loop. No recursion, no memo map, no hash.
function rankShape(B, h){ // a sum of per-column increasing terms
let s = 0;
for (let i = 0; i < B.M; i++) s += B.CUM[i][h[i]];
return s;
}
Bite it yourself: https://dev48.infy.uk/game/day72-chomp.html
The move the argument mentions is usually the wrong one
Strategy stealing reasons about the far corner square: if biting it loses, the winning reply could have been played first instead. That square is the only move the argument ever names. Played as a policy it is a losing move on 80 of the 99 bars up to 10×10. Every one of the 19 it wins has a side of exactly 2; set the two-row bars aside and it wins 3 times in 293.
| policy, every bar 2×2 to 8×8, five games each | wins |
|---|---|
| perfect play from the table | 245 / 245 — 100.0% |
| the proof's own move | 132 / 245 — 53.9% |
| the biggest legal bite | 123 / 245 — 50.2% |
| bite at random | 117 / 245 — 47.8% |
A theorem can be right about the outcome and worth six points against a coin about the move.
The win is a needle, which is why that gap is expensive: of the 184,755 shapes fitting in a 10×10 box only 2,612 are losses for the player to move, a winning bite is 312,237 of 9,053,045 legal bites — 3.45% — and even a won position offers 1.71 of them on average.
What the measurement contradicted
Uniqueness. 687 of the 692 bars the deep sweep visits have exactly one winning bite, which makes "the winning bite is unique" irresistible and false. 6×13, 8×10, 9×10, 10×14 and 12×13 each have exactly two, and after 34,020,393 solved positions not one bar has three.
The shape of the counterexample is the real finding. The smallest is 78 squares, not 80 — 6×13 is thinner than 8×10 — so a sweep ordered by area or by side length walks straight past it. The plan is one box per row count instead: two rows out to 400 columns, thirteen rows out to thirteen.
One closed form does survive — an L loses exactly when its two arms are equal, 0 exceptions — and it is worth almost nothing, catching 10 of the 2,612 losses and beating "just guess the mover wins" by 0.0054 of a percentage point.
10,963,023 assertions on load, and 52,446,660 more in a verifier that pulls the engine block out of the file and runs it under Node. Self-contained: one file, inline CSS, no external asset of any kind.
Part of a from-scratch series — one game a day, vanilla JS, dependency-free engine: https://dev48.infy.uk/gamefromzero.php
Top comments (0)