Combinatorial Game Theory
who wins, and by how much
Series

Sylver — the series

6 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. The gaps of ⟨5, 7⟩, which are the moves. A Sylver Coinage position drawn as the numerical semigroup it is. Gold squares are the numbers already named; plain squares are sums of them, and so cannot be named again; magenta squares are the gaps, which are exactly the legal moves. The largest gap is the Frobenius number, marked F — past it every integer is reachable, which is why the game has finitely many moves left and must end.

    The game that is a number system

    In Sylver Coinage two players name integers and nobody may name a sum of what has already been named. Its positions are not boards — they are numerical semigroups, its termination is a theorem of Sylvester's from 1884, and the question of who wins after the opening move 16 has been worth a thousand dollars since 2017.

    part 1 · applied
  2. Every position, by how much is left. Sylver Coinage positions counted by genus — the number of integers still unnameable — with the share on which the player to move loses. The parity of the genus very nearly decides the game: odd rows run between a fifth and a half, even rows between nothing and a thirteenth.

    A parity with a first exception

    Sort every Sylver Coinage position by how many numbers are still unnameable and the game very nearly falls to parity: odd rows are between a fifth and a half positions the mover loses, and the first three even rows hold none at all. The rule has a first counterexample at genus eight, where it is a single position out of sixty-seven, and eleven more at genus ten. It is a tendency wearing away from both ends rather than a law with exceptions.

    part 2 · applied
  3. The positions that pair their gaps off, and who loses them. Every Sylver Coinage position with at most sixteen unnameable numbers, counted by genus, split into the symmetric and pseudo-symmetric semigroups — the irreducible ones — and the rest, with the positions lost for the player to move in each. Of 584 irreducible positions exactly one is lost, the single position whose only gap is 1; the remaining 11,185 positions include 1,405 losses.

    Every move closes the largest gap

    A census of Sylver Coinage by genus finds a parity that nearly decides the game and asks whether any known property of a numerical semigroup predicts the outcome. One does, completely: a semigroup whose gaps pair off around the largest one is never lost for the player to move — none of 583 up to genus sixteen. The reason is strategy stealing, and it is the same reason the top-right square decides Chomp: every move from such a position closes the largest gap.

    part 3 · applied
  4. The gaps of ⟨5, 7, 9, 11⟩, and which of them the pairing removes. A Sylver Coinage position drawn as the numerical semigroup it is, with every legal move marked by what a single pass says about it. Gold squares are the numbers already named; plain squares are sums of them; magenta squares are the gaps, which are the legal moves. Under each gap is "struck" when the position that move reaches has its own gaps paired around its own largest gap — a position the opponent wins, so the move loses — and "wins" when the search says the move wins.

    The pairing removes moves it cannot name

    Symmetric positions were settled by an argument that names a winner and no move. Turned on the moves instead, the same one-pass test strikes off 27,215 of the 159,728 moves in the census and not one of the 21,234 winning ones — a quarter of a full search — and still names nothing. On 583 paired positions nine arithmetic descriptions of the winning gap reach at most 123, and 367 of those positions have exactly one winning move.

    part 4 · applied
  5. Seven orders, and none of them better than chance. Seven quantities a one-pass scan could compute about each move surviving the pairing test — the number itself, how many gaps it closes, what it leaves behind — each read as an order over the survivors and scored against the winning moves of 583 positions. The best puts a winner first on 24.9% of positions against 22.3% at random, and every one of the seven places the winner deeper in its order than chance would.

    A shortlist with nothing at the top

    The one-pass test leaves 9.58 moves of 12.27 and names none of them. Seven quantities a scan could compute about the survivors were turned into orders and scored on 583 positions: the best puts a winning move first on 24.9% against 22.3% by chance, and every one of the seven places the winner deeper in its order than chance does. Read as sieves instead, the gentlest keeps half the list and throws the only winner away on 264 positions.

    part 5 · applied
  6. A move that leaves no surviving reply. A Sylver Coinage position whose gaps are 1, 2, 3, 4, 6, 7, 8, 9, 12, 13, 14, 17, 18, 23, 28, with the number of the opponent's surviving replies under each move that survives the pairing test. Naming 4 leaves no surviving reply, which proves it wins; the other winner leaves as many replies as the losing moves.

    A move whose every reply is struck

    Read two moves at a time, the Sylver Coinage shortlist is no better ordered than read one at a time: preferring the survivor that leaves the opponent the fewest surviving replies puts a winner first on 24.7% of 583 positions against 22.3% by chance, and places it deeper than chance does. Read as a proof, the same count does what no order could. On 57 positions a survivor leaves no surviving reply at all, and wins by a certificate a few lines long; searched deeper, the survivors prove every position by thirteen moves — at a price that is never below the search that simply finishes.

    part 6 · applied

All series