Every essay — page 20
Where it stops
Misère play and loopy games: the two places the theory itself gives way — values that stop composing, and a recursion with no bottom.
What survives a coalition
Three-player Nim has no winner without a convention and no sum theory at all. Fix one player against the other two and both come back: every position has a winner, the winner is read off the number of heaps of one modulo three and the number of larger heaps, and forty-five positions fall into six interchangeable classes — fewer than Nim's sixteen. Fix a scoring rule instead and the winner comes back, identical to one of the conventions, and nothing else does: no two positions are interchangeable.
One value more than Nim
Top Entails broke the nim-sum: nine of thirty-six two-heap positions came out wrong when a move could compel the reply. The repair is one extra value. Read each heap off the heap itself, and every heap of Top Entails and of a second entailing game is either a nimber or loony — a win for the mover in any company. One rule then decides every sum of those games and Nim together: 4,016 positions, and it is never wrong. A loony heap is a pass, and the compulsion is what buys it.
The table closes, until heaps of four
Classes that no company can tell apart always combine, so the question left by the held pass is not whether it has an algebra but whether the algebra is finite. Computed the way a misère quotient is, it is: four classes for heaps of one where misère play needs two, eleven for heaps up to two, fourteen up to three, nineteen for Kayles rows up to five. Admit Nim heaps of four and the table never closes — a single line of losses, 2k + 3 heaps of two beside 2k heaps of four, gives every count of twos a class of its own. And at the bottom of every closed table sits the normal-play group, with the loss moved to nim-sum one: on a crowded board the held pass is a heap of one.
A coalition counts to three
Three-player Nim with one player against two collapses to six classes, because every heap of two or more is a store of tempo either side can draw on. Put the same coalition on games whose heaps are not all stores and it does not collapse: subtraction {1, 2} keeps five kinds of heap, Kayles six, subtraction {1, 3} ten and {2, 3} twelve, each count settling as the range grows. Past a threshold the large heaps are interchangeable again — and in every one of the five, unlike Nim, a single large heap hands the game to the coalition. The classes neither refine the two-player values nor coarsen them: {1, 3} has two Grundy values and ten coalition classes.
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.
Units modulo three, and one choice
Nim's rule for one player against two has a shape: count the heaps that always last one move, modulo three, allow one heap that offers a choice, and give any second choice to the coalition. Subtraction {1, 2} has exactly that table — ten classes, nine of them a count of ones against nothing, a two or a three — and so do Kayles, where a heap of three is a heap of two with a unit beside it, and Dawson's Kayles. Subtraction {1, 3} and {2, 3} do not: a board with two choices on it can still be the lone player's, and the short key fails. And {2, 3} and Dawson's Kayles give every heap to ten exactly the same menu of game lengths, so what a coalition reads is not how long a heap can last.
A compulsion that points elsewhere
Top Entails and entailing Nim are decided by one value more than Nim because the compelled reply stays in the heap that compelled it. Point it at a different heap instead and the two games part company. Entailing Nim does not notice — its heaps are worth exactly what Nim's are, because Nim's winning reply was never in the heap just moved. Top Entails loses its loony heaps and then every value of the Nim kind: no assignment of nimbers explains its sums, because a heap of three beside two heaps of one is a win and beside two heaps of two is a loss.
Particular games
Hackenbush, Nim, Domineering, Toads and Frogs — the specific games the general theory was built to explain.
Hackenbush is a numeral
Draw a stalk of coloured edges. Read it as a string, blue for one and red for zero, and the string is the binary expansion of what the position is worth. Not approximately — exactly, and the site computes it both ways and refuses to build if they disagree.
Domineering
One player places dominoes vertically, the other horizontally, on a shared grid. The rules take one line, the values are a mess, and that mess is the point — this is what the theory looks like applied to a game nobody designed for it.
Toads and Frogs
Toads shuffle right, frogs shuffle left, and either may jump over one of the other. A strip six cells long is worth exactly up. Another six-cell strip is worth exactly down. Nobody has a formula for which.
Sprouts, and the game that is not one
Two games played with dots and curves, invented in the same room, all but indistinguishable on paper. One is unsolved past forty spots. The other has no decisions in it at all — the winner is fixed before the first curve is drawn.
One board, two rules
Col forbids painting next to your own colour. Snort forbids painting next to your opponent's. One word differs, the boards are identical, and the values that come out are not the same kind of object.
Cutcake, where every value is a whole number
A partizan game in which no position is ever worth a fraction, a star or a fight. Every value is an integer, the integer is a count of spare moves, and the pattern it follows is decided by binary digits.
Amazons, and when a position becomes a sum
Every technique on this site starts from a position already broken into independent parts. Amazons does not begin that way — the board is one fight until the arrows cut it, and the moment of cutting is something the play produces rather than the analyst assumes.
Squash every loop to a point
Colour every Hackenbush edge green and the game becomes impartial, so the whole picture is worth a single Nim heap. Two principles find which one without playing anything — fuse the cycles, then run one pass up the tree — and a nine-vertex lattice that costs 1,283 positions to solve costs twelve steps to read.
All ladders · Every object named here · The position index · Figures that play back · Search