Seventy engines in this series, and every one had a position to evaluate. Kayles takes that away. A ball knocks down one pin or two side by side, and a pin taken from the middle does not shorten the row — it splits it. Thirteen becomes six and six. By ply five you are running four or five independent games in parallel, and the number of continuations is the product over the parts, so nothing that searches survives contact.
What replaces the search is Sprague–Grundy: give every row one number, XOR the numbers, and zero means you lose.
function grundyRow(allowed, N){
const G = new Int32Array(N + 1); // G[0] = 0: no pins, no move, a loss
for (let n = 1; n <= N; n++){
const s = new Set();
for (const c of allowed)
for (let i = 0; i + c <= n; i++)
s.add(G[i] ^ G[n - c - i]); // the middle SPLITS: two games, already XORed
G[n] = mex(s);
}
return G;
}
Nine lines, linear in the longest row, and the entire player is xorOf(rows, G) !== 0. Play it, with every winning reply painted: https://dev48.infy.uk/game/day70-kayles.html
The decomposition is the assumption, so it is attacked rather than cited
A second solver treats a board of sixteen cells as a bitmask, enumerates all 65,536 of them, and scores each by mex over its own successors — no runs, no splitting, no XOR anywhere in it. Every mask equals the XOR of its runs: 65,536 of 65,536, per rule set. The verifier then goes further and plays the definition rather than checking it — row n beside a Nim heap of G(n) must be a LOSS, and beside any other heap a WIN, over 672 combined games decided by pure win/loss recursion.
The period is certified, not observed. Guy–Smith turns "check forever" into "check n ≤ 156", and a control rejects a claimed start of 70. Sixteen earlier terms break the period, the last at n = 70, which is exactly why it is invisible in the values people print.
Two metrics, running in opposite directions
Change one word — last pin loses — and Sprague–Grundy no longer applies. The normal-play values stay nearly right, so the sensible engineering call is to ship them and note the edge cases.
| rule set | positions the values still call correctly | games the bot reading them wins |
|---|---|---|
| Kayles 0.77 | 96.91% | 8 / 719 |
| Dawson's Kayles 0.07 | 60.44% | 214 / 626 |
| Triples 0.777 | 99.18% | 8 / 754 |
| odds only 0.707 | 0.00% | 525 / 525 |
The control says an exact misère tablebase wins 719 of those same 719 starts. Being right about 96.91% of the state space buys 1.1% of the games, because the 3.09% is not scattered — it is the endgame, and every game arrives there. Being wrong about every single position costs nothing, because on odds-only the parity of the rack flips whatever you believe: from an even total every legal move wins, the engine cannot find one that zeroes the XOR, falls through to its first legal move, and that move is correct.
Verdict accuracy over a uniform sample of positions is not a weak proxy for playing strength. It is not a proxy at all.
What the measurement contradicted
The mirror trick — take the middle, then copy every reply on the other side — carries no arithmetic at all and wins 200 of 200 single rows. On two rows it finds a winning move 20.6% of the time. A rack of pins is one row, so anyone who has only played from a full rack has never seen the theory earn anything; the second row is the whole bill.
"Always take the biggest bite off the end" wins 5.4% against random's 5.6%. It is the same player.
And one assertion failed 300 times and was mine, not the engine's: I asserted that the perfect player loses whenever the XOR says the start is lost. A lost position is only lost against correct play, and the opponent there was random.
320,906 in-page assertions and 405,838 in the verifier. One file, inline CSS, and not a single external asset.
Part of a from-scratch series — one game a day, vanilla JS, one file, dependency-free engine: https://dev48.infy.uk/gamefromzero.php
Top comments (0)