Combinatorial Game Theory
who wins, and by how much
Series

Sylver — the series

9 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
  7. 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.

    part 7 · applied
  8. 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.

    part 8 · applied
  9. 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.

    part 9 · applied

All series