Combinatorial Game Theory
who wins, and by how much
Concept

Rule change — where it appears

A single clause added to or deleted from a game's rules, and what it costs. A hop, a pass, a cap on the last move or a shared orientation each changes the values completely while leaving the picture alone.

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

Every strip, without the hop. Toads and Frogs with the jump deleted, over every strip up to eight squares. The fourth column is the argument: whenever the value is a number it is a whole number, without exception, so the fractions the ordinary game produces are made by the hop and by nothing else.

The strip where every number is a whole one

Delete the hop from Toads and Frogs and the halves, quarters and ups vanish completely: over 9,801 strips, every value that is a number is an integer, without a single exception. The guess that the hopless game therefore has a formula reading the gaps is half right and exactly wrong — 1,460 strips of eight squares are switches, and three strips with the same counts of toads, frogs and empty squares are worth 1, {2 | 1} and 2.

positions · Toads and Frogs Where running out of moves is permanent. Eleven rulesets, each walked position by position from three small boards, with every position at which a player has no move examined for whether any continuation gives them one back. Nothing here is evaluated: dead-ending is a property of the rules, and two boards worth the same value can differ on it. 9 of the 11 are dead-ending and 2 are not.

Nobody comes back

There is a class of games in which running out of moves is permanent, and it is the setting almost every modern misère result is stated in. Nine of this site's eleven rulesets belong to it across 5,334 positions; the two that do not are Toads and Frogs and Amazons, and Toads and Frogs loses the property to a single clause — delete the hop and it joins the list.

limits · Dead-ending What a component has to carry. Four impartial games, one of which is Nim. In the other three a component cannot say what its own legal moves are without knowing something about the past or about the rest of the board, so the Sprague–Grundy recipe does not apply — and the table says by how much. Every outcome was obtained by solving the sum outright rather than by any formula.

What a component has to carry

Three impartial games on this site break the sum, and they break it for the same reason: a component cannot say what its own legal moves are. Measured with one instrument — one number per part, exclusive-ored — the failure rate runs from a quarter to nearly half, against a control where the same recipe is a theorem and is never wrong.

limits · Memory Moore’s rule, reversed. Moore’s Nim under the misère convention at three values of k, with the normal-play rule and the same rule plus a clause about heaps of one. The patch is the one Nim takes, with the modulus the normal-play rule already carries, and it is right on every position swept.

The patch that generalised

Misère Nim takes a one-line patch: play the normal-play strategy until every heap holds a single counter, then invert. Moore's Nim, where a move may take from up to k heaps at once, takes exactly the same patch with exactly the same modulus — and the two rules disagree on six positions out of 923.

impartial · Moores-nim A fortress, and the counter that gives it a label. A pawn ending where the defender's king shuffles for ever and the attacker needs time. Down the rows, how many moves of preparation the breakthrough needs; across the columns, how many moves the rule allows before declaring a draw. With no breakthrough the position is drawn whatever the rule says, and drawn as a residue the backward induction never reaches. With a breakthrough and no rule the attacker wins despite the cycle. Where the march is longer than the counter allows, the rule turns a won position into a drawn one.

A position with no value, and the rule that gives it one

A fortress is a cycle in the position graph, so the recursion defining a value has nowhere to bottom out and the propagation never reaches it. Chess has a rule for that — count fifty moves and call it drawn — and the rule does not merely tidy the theory up. On eleven cells of the sweep it takes away a win.

applied · Chess The fee the geometry charges. The same endgames solved with the cost of declining changed. Two boxes on a chain and four on a loop are what a single cut and a pair of cuts complete; altering them changes the winner of a large share of positions, which is what says the law depends on them.

Two and four are not conventions

Declining costs two boxes on a chain and four on a loop, and those numbers are read off the geometry rather than chosen: one cut completes the last two boxes of a chain and two cuts complete the last four of a loop. Solved again with the fee changed, 418 endgames give a different winner on up to a third of themselves — so the endgame's law is a law about the fee as much as about the shapes, and the fee is not a free parameter.

applied · Dots and Boxes One split is enough, and some are not. Lasker's Nim beside five versions of it that allow only some splits, over the first twenty-four heaps, with every cell that leaves the formula outlined. Allowing only the split that takes one counter off reproduces the whole sequence; allowing only equal halves turns it back into Nim.

One split is enough

A heap of n in Lasker's Nim offers ⌊n/2⌋ ways to split, and the values use at most one of them. Allow only the split that takes a single counter off and every heap to six hundred keeps its value; of all sixty-three sets of split sizes up to six, a set keeps the formula exactly when it contains 1 or 2. Equal halves alone give back plain Nim, because a split into equal parts is a move to nought.

impartial · Lasker

Named alongside it

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

Exhaustive searchCounterexampleGrundy valueImpartialOutcome classClosed formComponentDecompositionEnding conditionLoonyMisère playNim-sum

All concepts