Combinatorial Game Theory
who wins, and by how much
Concept

Binary — where it appears

Base two, which is the numeral system Nim's criterion is a statement about and which makes its winning move a repair of parities. Reading a Hackenbush string in it gives the position's value directly, which is the site's shortest route from a picture to a number.

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

The picture is the numeral. Blue-red Hackenbush strings and their values. Left may cut a blue edge, Right a red one, and everything above the cut falls. The value of each string is a number, and reading the string from the ground upward gives the binary expansion of exactly that number.

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.

positions · Hackenbush Nim with heaps of 3, 5, 7. Heaps of counters; a move takes any number from one heap. The position is a loss for the player to move exactly when the binary digits of the heap sizes cancel in every column — the nim-sum — and that is the whole of the theory of Nim.

Nim, and the nim-sum

Three heaps of counters, take as many as you like from one of them, and the player who takes the last counter wins. The winning condition is not a search, not a table, and not a heuristic — it is the bitwise exclusive-or of the heap sizes, and it was found in 1901.

impartial · Nim The simplest number in between. A game whose options are numbers is worth the simplest number strictly between them — and simplest means born earliest, so integers come before halves and halves before quarters. It is not the midpoint, and the difference is the whole content of the rule.

The simplicity rule

When both players' options are numbers, the position is worth the simplest number strictly between them. Not the midpoint, not the average, and the difference between "simplest" and "middle" is the entire content of the rule.

values · Numbers Cutcake: every value an integer. The value of an m by n cake, for every small m and n. Left cuts down, Right cuts across, and neither player ever gains by moving — so nothing is ever at stake, every value is a whole number, and the number says exactly how many spare moves one player has.

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.

positions · Cutcake Turning Turtles: a row of 12 coins. A row of coins, some heads and some tails. A move turns some of them over, and the rightmost coin turned must go from heads to tails — which is what makes the game end. The number under each place is what a lone head there is worth, and the row is worth the exclusive or of the places showing heads.

A row of coins is already a sum

Everywhere else on this site a sum is several positions side by side. In a coin-turning game it is one row — each coin showing heads is a game in its own right, and the row is worth the exclusive or of them. The decomposition is inside a single picture.

impartial · Sprague–Grundy A green edge is not a number. Green edges may be cut by either player, which makes the position impartial in that part. A single green edge is worth ∗ — a value that is neither positive, negative nor zero, and which no number can equal.

A green edge on a blue one

Blue over green and green over blue are the same two edges in the other order. One is worth 1∗ and the other ↑∗ — a number with a star on it against something smaller than every positive number — so a stalk with all three colours in it stops being a numeral and starts being a position whose value depends on what is underneath.

positions · Hackenbush The cold positions, written in Fibonacci base. The first several cold pairs of Wythoff's game with both heap sizes written in Fibonacci base — as sums of non-consecutive Fibonacci numbers, which every integer has exactly one of. Blue is the smaller heap and red the larger. Read as digits, the pair is a shift: the larger numeral is the smaller one with a zero appended, and the smaller one always ends in an even number of zeros.

The digits say which move wins

Wythoff's cold positions are usually given as a pair of golden-ratio formulas. Written in Fibonacci base they are a statement about digits instead — the smaller heap ends in an even number of zeros and the larger is the same numeral shifted up a place — and a rule about digits answers a question about a heap of a trillion.

applied · Wythoff's game The picture is the numeral. Blue-red Hackenbush strings and their values. Left may cut a blue edge, Right a red one, and everything above the cut falls. The value of each string is a number, and reading the string from the ground upward gives the binary expansion of exactly that number.

The other sum, the one that nests

A move in one part wipes the other out entirely. That is the ordinal sum, it is what a Hackenbush stalk actually is — 1 : (−1) is a half, and 1 : (−1) : 1 is three quarters — and it is not an operation on values at all: three positions all worth zero give three different answers under it.

sums · Ordinal sum Moore's Nim with k = 2: the columns, divided by 3. The heap sizes in binary, with each column added as an ordinary sum rather than exclusive-or. In Moore's Nim a move may take from as many as k heaps at once, and the position is lost for the player to move exactly when every column sum is divisible by k + 1. Ordinary Nim is k = 1, where divisible by two means an even number of ones — the same picture with a different divisor.

Taking from several heaps at once

Moore's Nim lets a move take from as many as k heaps at a time, and the losing positions are still read off the binary columns — divisible by k + 1 rather than by two. The rule agrees with exhaustive search over 54,264 positions and never disagrees, and it decides every outcome while supplying no value at all: reading the same columns as a base-3 number gets the Grundy value right on 42 of 330 positions.

impartial · Moores-nim Mock Turtles on 8 coins: finding the move is decoding. Every row of the game, sorted by what it takes to win from it. The lost rows are the codewords; a won row is a codeword with errors, and the winning move is the error pattern that turns them off. The distance column is a fact about the code and the coins column is a fact about the rules, and the two do not quite agree.

The code names the move

If the lost rows of a coin-turning game are a linear code, then a won row is a codeword with errors in it and the winning move is whatever turns the errors off. Over all 256 rows of Mock Turtles on eight coins: 16 codewords, 240 won rows, none more than two coins from a lost one — and 64 of them whose cheapest winning move has to turn three coins anyway.

impartial · Codes Welter positions and what they are worth. Coins on a strip, with the Grundy value the recursion returns and the nim-sum the squares would have if they were independent heaps. The two columns are the essay: they hardly ever agree.

No two heaps alike

Welter's game is Nim with one extra clause — no two heaps may be the same size — and the clause is fatal to the nim-sum, which gives the right answer in none of the 120 three-coin positions. What replaces it is a function of pairs: ⟨a | b⟩ = (a ⊕ b) − 1, exact on all 55 two-coin positions, and nim-added over every pair it is exact on the whole board provided the number of coins is even.

impartial · Welter Shove strips, and what each is worth. A shelf of positions with the value the recursion returns beside each. Every one is a number: Shove has no hot positions at all, which is unusual for a partizan game and is the first of the essay's three claims.

Nothing worth fighting over

Shove is a strip of coins beside a cliff, and both players have completely different moves. Every one of its 728 positions is worth a number, so nobody ever wants to move; the winner is the owner of the coin furthest from the cliff, in all 728; and the number the board is worth is not the sum of its coins — that reading is exact on 126 strips and wrong on 588 of the other 602.

positions · Shove Trees, and what each is worth. A row of blue-red Hackenbush trees with the value the recursion returns under each. Every one is a number, and none of them is the binary reading of anything a reader can see in the picture.

A tree is still a number

A Hackenbush string spells its own value in binary. Put a fork in it and the numeral has nothing to read — there is no leftmost anything. The value is still a number, in all 10,066 forests up to six edges; it is still computable, by the ordinal sum, in all 3,238 single-trunk trees; and the reading is right on 762 of them, of which 126 are the strings it was written for.

positions · Hackenbush Three strips a criterion cannot tell apart. Three Push strips identical in length, reading, coin counts and run structure, whose readings are wrong by a quarter, a half and a quarter more than one. The order of the colours inside the run is the only thing separating them.

The criterion that cannot exist

The rung below asked for a quantitative version of its condition — turn 'the reading survives mixing three quarters of the time' into a statement about the strip. Three strips of four squares settle it. `.LLR`, `.LRL` and `.RLL` have the same length, the same reading, the same coins and the same single run, and their readings are wrong by 1¼, ¼ and ½. The error is a fact about the order of the colours, and 207 of 805 statistical classes carry more than one of them.

positions · Push A numeral in the empty squares. Runs of coins with one to five empty squares in front, and the value of each. Every row is a binary expansion converging on a fraction the colours determine.

A numeral in the empty squares

The rung below ruled out a quantitative criterion for Push and asked for a numeral over the coins combined with a count over the gaps. The two ingredients are the right way round: the colours pick a fraction — −1, −1/3, −1/7, −1/15 — and the empty squares give the binary precision, so a run of k coins before one of the other colour with g gaps is worth exactly (1 − 2^(−kg)) ÷ (2^k − 1). And it does not compose: a strip of two runs is not the sum of them, on any pair tried.

positions · Push Moving them apart does not make them independent. The value of a two-run Push strip as the gap between the runs widens. Each row converges, and none of them converges to the sum of its two runs.

The cliff a cut invents

The rung below asked for a correction term in the gap between two Push runs. There is none, because the gap's contribution vanishes: widen it and the strip's value converges geometrically, at a rate set by the back run's length alone, to a limit that is not the sum. And Shove — whose reading is exact everywhere — fails at the same cut, which says the broken thing is the cut and not the game.

positions · Push Every gap dies at the last run's rate. Three-run Push strips with each gap widened in turn, and which of four candidate rates the convergence matches. The rearmost run's rate wins every family and the compound rate wins none.

Read from the back forwards

The rung below found a two-run Push strip converging at a rate set by the back run and asked what a third run does — whether the rate is still the rearmost run's, or whether the rates compound. It is the rearmost run's, and for every gap: widen the front gap of a three-run strip, two whole runs away, and the value still dies at the last run's rate. Shove, the game one clause away, compounds.

positions · Push The two proofs, beside each other. Maundy Cake's rule was proved by restating its lemma so the short side vanished into a multiset of primes and a term count. Cutcake's rule takes the same five steps, with the multiset replaced by a binary length — one integer instead of a multiset — and the closing argument correspondingly shorter. The one line where they differ is which cut a reader would guess.

The obvious cut is the wrong one

Maundy Cake's rule was proved by restating its lemma so the short side vanished. Cutcake's collapses the same way — into a binary length instead of a multiset of primes — but the cut the argument needs is not the one the ladder predicted. Halving is wrong on a third of all cakes, and the smallest counterexample is six squares by two.

positions · Cutcake How far a description of that kind could ever have gone. Subtraction games sorted by whether a Bouton-style column criterion describes their losing positions. His test reads the heap sizes in binary and counts the marks in each column, which works exactly when a heap's value is a function of its own bits — and that is true of a small minority of the family. Below it, the weaker readings: a criterion on the low bits, and a sequence that merely repeats. The method itself is available for every game and says nothing; what 1901 supplied was a set with a description shorter than the game.

A set with a short description

Bouton's argument is a closure argument about a set, and every impartial game has such a set — its own losing positions. So the method is complete and proves nothing. What made 1901 a theorem is that his set had a description shorter than the game, and swept over fifty-six subtraction games, exactly seven have one of his kind.

history · Bouton Lasker's Nim in sixteen cells. A four-by-four table. Each row and column is a residue mod 4 of one part of a split heap, with the residue of that part's Grundy value beside it; each cell is the residue mod 4 of the split's value, the nim-sum of the two parts. Every split of every heap to four hundred lands in the cell its residues name.

The proof is sixteen cells

Lasker's Nim has a four-clause formula that was checked on two thousand heaps and never proved. The proof fits in a four-by-four table: the last two bits of a split's value are fixed by the last two bits of its parts, so no split can land in its own heap's class — except at 3 mod 4, where it lands exactly on the one value the takes leave missing and pushes the answer up by one.

impartial · Lasker

Named alongside it

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

HackenbushPartizanDisjunctive sumClosed formExhaustive searchGrundy valueImpartialNim-sumNormal playSimplicity ruleEnumerationInvariant

All concepts