Combinatorial Game Theory
who wins, and by how much
Concept

Frobenius number — where it appears

The largest amount that cannot be made from a set of coprime numbers, which is the last gap a numerical semigroup has. In Sylver Coinage it is always removable on its own, which is what makes the longest play use every gap.

Named by 7 essays across 2 fields — each of them below, with the objects they name alongside it.

Also named here as numerical semigroup — the same set of essays touches all of them, so they are one junction rather than several.

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.

applied · Sylver Two ways to be certain and ignorant at once. Ten positions from two games that both terminate for reasons no bound comes out of. Sylver Coinage's proof counts something that goes down and can be counted; the hydra's counts an ordinal, which cannot, and the last column shows what that difference is worth.

Two ways to end with no bound

Sylver Coinage and the hydra are both guaranteed to finish and neither will say when. The difference is that one of them carries its own bound: every move in Sylver removes at least one gap, the gaps can be counted in a moment, and over ten openings the longest play uses every single one. The hydra has no decreasing quantity a solver can hold — three hydras of five nodes each take seven chops, twenty-one, and a number past two hundred and seventy-nine that this machine never reaches.

limits · Termination 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.

applied · Sylver 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.

applied · Sylver 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.

applied · Sylver 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.

applied · Sylver 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.

applied · Sylver

Named alongside it

The objects these essays reach for when they reach for this one.

Exhaustive searchNumerical semigroupSylver CoinageImpartialMove selectionSearch costSymmetryCertificateDominanceEnumerationHeuristicIntractable

All concepts