Combinatorial Game Theory
who wins, and by how much
Concept

Sylver Coinage — where it appears

The game of naming numbers that are not sums of multiples of earlier ones, which must end and whose length nothing bounds. The number of gaps bounds the length from any position, and over ten openings the longest play uses every one of them.

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

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 Hydras, and how long each takes to kill. Six small hydras with the ordinal the termination proof assigns to each and the exact number of chops it takes to finish it. Two of them are not finished here: the fight is guaranteed to end and the machine runs out of memory long before it does, which is the gap between a termination proof and a bound.

It ends, and nothing says when

The recursion this site runs needs every line of play to reach a position with no moves, and the condition is usually met by an obvious decreasing quantity. The hydra meets it with no such quantity anywhere: the tree grows at nearly every step and the fight ends regardless, because the only thing that decreases is an ordinal. A four-node hydra dies in twenty chops; one level deeper and 279 chops reach forty thousand nodes with no end in sight.

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

Which games end at which level

Between a game that ends within a computable bound and one that ends with no bound at all there are levels, each corresponding to a strength of induction. This site's games sit at three of them, and which level a game is at is decided by exhibiting its termination measure and checking that every move lowers it.

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 Keeping the table, and the price that stays. Median cost of four proof searches over Sylver Coinage survivors, as a multiple of the pruned search that finishes, for every irreducible position of eight to 20 gaps. A fresh table at each depth reaches 18.7 times; keeping the mover's positions 9.7; keeping both players' 5.9; told the depth in advance 2.9. None falls to one.

A different question at every depth

A Sylver Coinage proof that deepens over survivors was never cheaper than the search that skips struck moves and finishes. Keep everything it proves and refutes and it gets cheaper — 41 per cent at twenty gaps, and more when the opponent's positions are kept too — and it is still never cheaper, on any of 1,766 positions, and the gap widens with the gaps. Told the right depth in advance it wins on seven. The finishing search asks one question of a position; a proof asks a different one at every depth.

applied · Sylver The order decides the exceptions. The pruned search that finishes and the told proof, both under five move orders, over the 1766 irreducible Sylver Coinage positions to twenty gaps: the number where the proof is cheaper and the median ratio of their costs. Smallest first gives seven, largest first 55, and a free winning-move-first order none.

The seven were the order

A Sylver Coinage proof told its depth beat the search that finishes on seven positions of 1,766, and on all seven the winning move came fifth when moves were tried smallest first. Run both searches under five orders and the seven vanish under every other one; try the largest move first and there are fifty-five new ones instead. Give both searches the winning move first, free, and the proof is cheaper on none. The exceptions were never positions where proving is easy. They were positions where one order made the finishing search stumble — and what is left when the order is perfect is the price of asking a proof's question.

applied · Sylver Heights from ω² down to nought. Thirteen Sylver Coinage positions with the gcd of the named numbers, its prime factors counted with repeats, the gaps of the semigroup scaled by the gcd, and the ordinal height those give: ω² for the empty position, ω·4 for {16}, ω for {2}, 3 for {3, 5} and 0 for {2, 3}.

No number bounds it

Sylver Coinage cannot be given a termination measure in the natural numbers: from {2} the game can last one move, two, or any number the second player chooses. The measure proposed for it — the gap count beside the number of distinct primes the named numbers share — rises on {4} + 6. Count the primes with their repeats and it falls on every one of 42,519 moves checked, and it is exact: the game tree is ω squared tall, and the height of a position is ω times the prime factors of its gcd plus the gaps that are left.

limits · Termination Two moves fewer at every node. Total closures of the Sylver Coinage finishing search over 1766 irreducible positions under eight move orders: a winning move first, for free 444,803, smallest first, from four 1,198,585, a fixed order learned on smaller positions 1,235,721, most often winning first 1,236,529, odd gaps first, the sorting free 1,330,926, most often winning, then odd gaps left 1,418,022, smallest first 1,536,301, a fixed random order 2,529,255, leaving an odd number of gaps first 2,559,245.

Start at four

Every order a program could compute had made the Sylver Coinage search that finishes dearer than trying the smallest move first, and the free oracle that puts a winning move first costs under a third of it. Two orders a game program would actually use do better: a history table of numbers that have won before wins back 27 per cent of that gap, and a fixed order learned on small positions the same on larger ones. Both are learning one thing. Trying the smallest move first, but from four, wins back 31 per cent and beats smallest first on 1,695 of 1,766 positions — because naming 2 leaves a two-generator semigroup, which is symmetric and never lost for the opponent, unless 3 is already reachable.

applied · Sylver

Named alongside it

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

Exhaustive searchNumerical semigroupFrobenius numberProofCertificateImpartialSearch costTerminationHeuristicInductionOrdinalSymmetry

All concepts