Combinatorial Game Theory
who wins, and by how much
The collection

Every essay — page 21

One idea per essay, ordered so that the earlier ones set up the later ones — but nothing here depends on being read in sequence.

Sums and comparison

Real games break into independent parts. Adding them up is the whole method, and comparing them is how it is checked.

How many ups, bracketed. Every position here is all-small, so no number says anything about it and the yardstick has to be ↑ instead. Each bar spans the multiples of ↑ the position lies between: the largest it is at least, and the smallest it is at most. Four of the seven are pinned to a single multiple of ↑; the rest keep a band that comparison cannot narrow, the widest being ∗ at four ups of slack.

How many ups

When every component of a position is smaller than every positive number, no number can decide it. What decides it is a count of ups — and comparison can pin that count down exactly, except when a star is present, when it cannot.

7 figures · Infinitesimals Every position has an exact opposite. A position beside its negative, which is the same game with the players exchanged, and the sum of the two. The sum is worth zero every time — a second-player win — because the second player can answer each move with its mirror image. It is the fact that makes values a group, and it is what lets one position be subtracted from another.

Turn the board through a right angle

A two-by-four Domineering board is worth something no number can express, and Right is ahead on it. Turn a second board through a right angle, put the two side by side, and the total is exactly zero. Every position has an exact opposite, and that single fact is what makes subtraction — and therefore comparison — possible at all.

7 figures · Negation Three ways to add the same games. One list of components, added three different ways. Under the disjunctive rule a move is a move in exactly one part; under the conjunctive rule it is a move in every part at once, and play stops as soon as any part runs out; under the selective rule it is a move in any non-empty set of parts. The outcomes are computed by search from each rule's own definition.

Three ways to add the same games

A move in exactly one component is a choice, not a law. Move in every component at once and the game is different; move in any set of them and it is different again. The same two positions, added three ways, give three different answers — and only one of the three has values that add.

7 figures · Disjunctive sum Comparing two positions means playing a third. Pairs of positions with the relation between them, and the game whose solution decided it. There is no way to compare two games by looking at them: the question “is G at least H?” is answered by playing G − H and asking who wins, which is a search, and its cost is counted here beside each answer.

Comparing two positions means playing a third

There is no way to look at two games and see which is better. The question "is G at least H?" is answered by building G − H and asking who wins it — so the most basic operation in the theory is a decision problem, and every canonical form is built out of them.

6 figures · Comparison Three partizan positions against every nimber, and not one match. Sprague and Grundy give every impartial position a single number that is complete: two positions with the same value are interchangeable everywhere. The three positions here are partizan — the two players have different moves — and each is compared against every nimber up to eight. Nothing is equal to anything. The magenta cells are worse than inequality: a position confused with a nimber is not above it or below it either, so no ordering could rescue the substitution.

Where the impartial theory stops

Sprague–Grundy gives every impartial position one number, and the number is complete. The moment the two players have different moves no number works at all — not a harder one to compute, none — and three positions here are compared against every nimber to show it.

8 figures · Sprague–Grundy A boundary drawn, and a boundary there. One Domineering board split two ways. Above, a line imagined down the middle: the two halves are evaluated separately and their sum is not the value of the board, because every horizontal domino that would have crossed the line has been thrown away. Below, the same column blocked out: the halves are then genuinely independent and the sum is exact. Every value is computed from its own board.

Independence is a claim

Splitting a position into parts and adding the values is the whole method of this subject, and the splitting step is a claim about the position rather than a fact about the drawing. Where it is false the two answers differ — and the failures that matter are the ones that keep the same winner and change the value, because nothing reports those.

8 figures · Disjunctive sum Comparing two positions is playing their difference. To decide whether one position is worth at least another, subtract and see who wins moving second. It is the only definition of comparison the subject has, and it produces a partial order — some pairs come out confused, which no comparison of numbers ever does.

Confused is not the same as unknown

Two positions can be neither greater, nor smaller, nor equal. That is a fourth relation with its own symbol, it is a fact about the pair rather than a limit of the method, and it is what makes a game worth playing — a position is a first-player win exactly when it is confused with zero.

7 figures · Comparison 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.

8 figures · Ordinal sum The context that tells them apart. Two positions put into the same company, one context at a time. Each column is a game X; each cell is the outcome class of that side added to X. Equality means every column agrees, for every X there is — so a single disagreeing column is a disproof, and agreement across a bounded list of contexts is evidence rather than proof. The proof is that the difference is zero.

Equal in every company

Two games are equal when no third game can tell them apart — a quantifier over every position there is, discharged by one finite test. A search over 184 contexts separates all 5,790 unequal pairs it is handed and still calls two different games the same, which is exactly why G − H = 0 is a theorem and an exhaustive search is not.

8 figures · Equality The bracket of a sum, against the sum of the brackets. Two all-small positions, the interval of multiples of ↑ each lies between, those two intervals added coordinatewise, and the interval the sum actually lies between. The added one always contains the computed one — greater-than survives addition — so the bracket never widens under a sum. Where it narrows, the parts were each too vague to pin down and the sum is not.

When the ups add

Atomic weight brackets do not add over a sum — they bound it. Over all 120 pairs from a fifteen-game family the sum's bracket came out exactly the sum of the parts' brackets 56 times, strictly narrower 64 times, and wider never; and the rule separating the two is one line long, because every one of the 54 pairs with a pinned part is exact and only 2 of the other 66 are.

8 figures · Infinitesimals The values born by day three that are their own negatives. Every game satisfies G + (−G) = 0, so a game equal to its own negative satisfies G + G = 0 — it has order two. The nimbers do, and they are not the only ones: a switch symmetric about zero is unchanged by negation, and so is anything whose Left options are the negatives of its Right options. Each row carries the value, whether it is a nimber, and its outcome.

The values that are their own negatives

Every game satisfies G + (−G) = 0, so a game equal to its own negative satisfies G + G = 0 — it has order two in a group whose elements otherwise have infinite order. The nimbers do. So does ±1, on sight. Over the 1,474 values born by day three there are 30 of them and only four are nimbers, every one of the 900 sums of two is another, and the equality test and a symmetry of the written form agree 1,474 times out of 1,474.

7 figures · Negation Swapping a branch for another of the same value. The ordinal sum of a base with a branch, and the same sum with the branch replaced by a heap of a different game carrying the same Grundy value. The two are compared by playing their difference, not by inspection — and they agree every time, which is what the colon principle claims and what the partizan case denies.

When the nested sum only sees the value

The ordinal sum reads the form and not the value: three positions all worth zero, placed under a star, give three different answers. On impartial games it reads the value after all — 72 substitutions of an equal-valued heap from a different game, and every ordinal sum comes back unchanged. That difference is the whole reason a green Hackenbush tree can be collapsed one branch at a time.

7 figures · Ordinal sum Every day-three value, moved by every quarter. Four claims counted over 3,000 translations — 120 values, each moved by every quarter from −3 to 3: that adding a number leaves the temperature alone, that it shifts both stops by exactly itself, that the interval between the negated stops is where the two players are confused, and that the only failures of the last are on its endpoints.

What a number does to a fight

Adding a number to a position moves everything and changes nothing: over three thousand translations the temperature never once shifted and both stops moved by exactly the number added, every time. What the number decides is whether the fight is worth having — and the interval where the two players are confused is exactly the open interval between the negated stops, right in all 2,890 cases away from its endpoints and wrong in 110 that are all on them.

8 figures · Translation How often one value is above another. The partial order counted on two successive days. The proportion of pairs that can be compared at all falls sharply, and so does the proportion of values that can be compared with zero — which is the proportion of positions whose winner does not depend on who moves.

How rare it is to be bigger

Values are partially ordered, and 'partially' does most of the work. On day two, 179 of 231 pairs can be compared and 13 of the 22 values can be compared with zero. One day later the shares are 60% and 29%, and the largest set of mutually incomparable values found rises from four to at least twenty-three. Comparison is the exception; confusion is what values normally do to one another.

7 figures · Comparison What the reduction collapses. Each reduced form with the values that reduce to it. The largest class is the one that reduces to zero and it holds every infinitesimal on the list, which is exactly what the reduction is for — against a hot background, none of them is distinguishable from nothing.

What is left when the small change is thrown away

Canonical form answers a demanding question: which positions are interchangeable inside every sum whatever. A player with a hot board does not have every sum — an infinitesimal difference cannot decide anything against a genuine fight — so there is a coarser question with an exact answer. The reduced canonical form takes the 1,474 values born by day three to 61, with 292 of them collapsing to zero, and it is a homomorphism on all 8,100 pairs tested only when a second pass is made.

7 figures · Reduced form

All ladders · Every object named here · The position index · Figures that play back · Search