Combinatorial Game Theory
who wins, and by how much
Generator

The same game, written twice

The same game, written twice
The same game, written twice. A position as it arises and the same position reduced. Left would never move to −1 when 0 is available, so that option is dominated and can go. The two games are equal — checked, not assumed — and the second is the canonical form.

A position as it arises and the same position reduced. Left would never move to −1 when 0 is available, so that option is dominated and can go. The two games are equal — checked, not assumed — and the second is the canonical form.

21 essays call canonical-form. The drawing above is what it returns with no arguments at all; every call below passes it something, because a placement that passes nothing draws whichever member of the family the generator happens to default to rather than the one its essay argues about.

The positions it draws

18 distinct positions, harvested by running this generator again at the options each essay passed it.

PositionWorth OutcomeDrawn in
{{0 | ∗2} | 0} ↑∗ N A reduction that reads a graph · The reduction that always shrinks · The reduction that puts options back
{ | ↓} −1 R An option nobody would take
{ | ∗} 0 P The reduction that puts options back
{{0 | ∗2} | 0} ↑∗ N Canonical form · The reduction that puts options back
{↑ | 1} 1/2 L The reduction that puts options back
{−1, 0, 1 | 1, 2} 1∗ L The move that gives counters back · Two hundred and fifty-six ways to write twenty-two things
{∗ | ∗} 0 P Equal in every company · How old a value is
{∗, ↑ | 0, ↑} ↑∗ N Canonical form
{0 | ↓} ∗ N The reduction that puts options back
{0, -1 | 1, 2} 1/2 L What a value leaves out
{0, -1 | 1} 1/2 L A reduction that reads a graph · Canonical form · Comparing two positions means playing a third · The notation was the argument · The reduction that puts options back · What a value costs to write down
{0, -3 | 1} 1/2 L Canonical form
{0, {0 | −1} | 0, {1 | 0}} ∗ N The same position, written once · Topple it from either end
{0, {1|0} | 1} 1/2 L Canonical form
{0, ∗ | ∗} ↑ L The reduction that always shrinks
{2 | {3|1}} 3 L Canonical form
{2, 0 | 1} 2 | 1 L A reduction that reads a graph
{2, 0 | 5, {3|1}} 3 L Canonical form

Where it is called

Changing this generator changes every one of these figures.

The same game, written twice. A position as it arises and the same position reduced. Left would never move to −1 when 0 is available, so that option is dominated and can go. The two games are equal — checked, not assumed — and the second is the canonical form. Values

Canonical form

Two positions are worth the same when neither player can tell them apart inside any larger game. Deciding that could be an infinite search. Instead there is a normal form — delete what nobody would play, bypass what backfires — and equality becomes a comparison of two small trees.

 Poker Nim from 3, 5, 7, with reserves of 4 and 4. Nim with one extra kind of move: a player may put any number of counters back onto a heap from a private reserve. It looks as though a losing player could stall for ever. They cannot, and the winner is decided by exactly the same nim-sum as ordinary Nim — checked here over every position within a stated range rather than argued. Impartial games

The move that gives counters back

Poker Nim adds one rule to Nim — a player may put counters back onto a heap from a private reserve. It looks as though a losing player could stall for ever. The winner is decided by exactly the same nim-sum, and the reason is the single most useful idea in the whole reduction apparatus.

 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. Sums and comparison

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.

 The same game, written twice. A position as it arises and the same position reduced. Three of the options are dominated — a sibling is at least as good for the player who owns them — so they can go. The two games are equal — checked, not assumed — and the second is the canonical form. Values

Two hundred and fifty-six ways to write twenty-two things

Every game whose options come from the four born on day one — there are 256 of them, and between them they carry 22 values. The reduction that collapses one to the other has choices in it at every step, and uniqueness is the claim that none of the choices matters.

 One position, three ways of writing it, and only one of them adds. The same positions as a sentence about who wins, as a description of the position itself, and in the notation Winning Ways introduced. The first two columns carry identical information and support no operation whatever. The third column can be added — and the sums below it are values that no manipulation of the first two columns could reach, because two of these pairs start from the same two outcomes and finish differently. How it was found

The notation was the argument

Up, star and the brace form are not abbreviations for case analyses. They are the claim that these objects add — and the arithmetic they support is arithmetic that no table of outcomes could ever produce, because two positions with identical outcomes can have different sums.

 7 positions of the same value, and how long each of them lasts. Nim positions whose heap sizes all nim-sum to zero. As games they are the same object: each is worth zero, each is a loss for the player to move, and each may be substituted for any other inside any sum without changing a single outcome. The bars are how many moves each one takes, from the shortest legal play to the longest. The value determines everything about who wins and nothing at all about when. Values

What a value leaves out

A value settles who wins, by how much, and what happens in every sum the position appears in. It says nothing about when. Seven positions here are worth exactly zero and interchangeable everywhere, and they run from two moves long to eighteen.

 How old a form is, and how old its value is. Every one of the 256 forms born by day two, placed by the depth it is written at and by the birthday of the value it carries. Nothing sits above the diagonal, because a form cannot be younger than the value in it; the diagonal holds the forms written at exactly their value's birthday, and everything below it is a position written older than it needs to be. The count in each cell was obtained by canonicalising all 256 forms and measuring both depths. Values

How old a value is

A form's depth bounds the birthday of the value inside it, and reducing to canonical form attains the bound — for all 22 values born by day two, with no exception. Twenty-four of the 256 forms are older than what they are worth. The same reduction that makes the bound tight is what puts day three within reach: 98 option sets a side instead of four million, 9,604 forms, 1,474 values, a quarter of a second.

 Options handed to Left in 1 | −1. A position, and one candidate option after another added to it. Where the gift is one the player would never take the value does not move at all; where it is one they would, it does. The last column is the value of the enlarged form, computed by the same recursion as the original. Values

An option nobody would take

Every reduction of a form deletes. The gift horse principle adds: a move may be handed to a player for nothing, provided it is one they would never choose. Over all 484 additions to the values born by day two, 283 leave the value exactly where it was and the 201 that move it are precisely the ones the condition forbids — with the boundary at *not better*, which is a weaker demand than *worse*.

 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. Sums and comparison

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.

 The same row, cut and toppled. Rows of blue and red drawn once and evaluated twice: as a Hackenbush string, where a player cuts an edge of their own colour and everything above it falls, and as Toppling Dominoes, where a player knocks one over and everything on the chosen side falls. Both values are computed by the same recursion from the two rulesets. Particular games

Topple it from either end

A row of blue and red is the picture this site opens with, and under Hackenbush's rules it is always a number. Knock the pieces over instead of cutting them — everything on the chosen side falls — and 480 of the 510 rows up to eight pieces stop being numbers. The two games agree on sixteen rows, every one of a single colour, and the temperature of the hottest row climbs by exactly a half for each domino added.

 The reduction that puts options back. How the two reductions change the width of a form. Domination only ever removes an option. Bypassing a reversible option substitutes the answer's whole option list, so it can leave the form wider than it started — and the finished canonical form can be wider than the form it came from. Values

The reduction that puts options back

Canonical form is presented as simplification, and half of it is. Deleting a dominated option takes one away. Bypassing a reversible one substitutes the answer's whole option list, so it can leave the form wider than it started — and 60 of 32,428 forms end up with a canonical form wider than they are.

 What deleting is worth on its own. The reduction split into its two halves and each measured. Deleting a dominated option removes exactly one option and can do nothing else; bypassing a reversible one substitutes an option list and can widen the form. The counts say how much of the reduction the monotone half accounts for. Values

The reduction that always shrinks

Canonical form is two reductions and they are not the same kind of operation. Deleting a dominated option removes one option and can do nothing else; bypassing a reversible one substitutes a whole option list. Over the 256 forms born by day two, deleting alone finishes 225 of them and accounts for 480 of the 520 options that come off — and the 31 it cannot finish are almost all the ones with a star in them.

 What a value costs to write down. Every one of the 1,474 values born by day three, grouped by the width of its canonical form, with the number of symbols the form takes when it is written out. Each count was obtained by walking the canonical form and counting its nodes, so a subposition appearing twice is counted twice — which is what writing it out does. The widest values of the day are not the longest to write. Values

What a value costs to write down

The canonical form is the smallest form of its value, and it is smallest in the one currency the reduction happens to spend: options. Counted in symbols it is nothing of the kind — the widest value born by day three is not the longest, the longest has six options rather than seven, and every canonical form on the day except the seven integers writes some position out twice.

 How hot a background has to be. Every pair of values born by day two that share a reduced canonical form, added to backgrounds of seven temperatures and three means — 609 comparisons in all — with the count of pairs whose outcome the swap changes. Safety is not monotone in the background's temperature, so the threshold the question asks for does not exist; every one of the 48 changes is at a position with a stop exactly on nought. Sums and comparison

How hot a background has to be

The reduced canonical form throws away infinitesimals, and the rung below asked for a bound: how hot must the rest of the board be for the discarded part not to matter? There is no such bound. Safety is not monotone in the background's temperature — an eighth is safe, a quarter is not, two is safe again — and the quantity that does decide it is not a temperature but a stop.

 What a day of canonical forms costs, written out and written once. Three costs for the values born by each of the first three days: every node written every time it occurs, every distinct subposition of a single form, and every distinct subposition of any form of the day. The last is one node per value, and the gap between the first and the last widens as the construction goes on. Values

The same position, written once

Writing out the canonical forms of day three takes 24,940 nodes. Naming each distinct subposition once inside each form takes 10,102, and naming each distinct subposition once across the whole day takes exactly 1,474 — one per value, because nothing appears inside a canonical form that is not itself a value of the day.

 Add, then reduce again. The arithmetic the homomorphism promises, measured: summing two reduced forms gives a reduced form on 88 per cent of pairs and needs a second reduction on the rest. Sums and comparison

Add, then reduce again

The homomorphism promises that a sum's reduced form can be computed from its parts', and says nothing about what the operation is. It is addition followed by a second reduction — needed on 431 of 3,600 pairs of day-three values, and on not one of the 1,751 pairs with a cold part. What the second pass removes is an option that only becomes dominated once the two fights are side by side.

 Eight ways to name it, and none of them works. Candidate rules for which option the second reduction deletes, scored on every pair where it deletes exactly one. The best reaches four in five and none is exact. Sums and comparison

The option nothing names

The rung below found the arithmetic on reduced forms to be add and reduce again, needing the second pass on 431 of its sums, and asked whether the option that pass deletes can be named from the parts. Eight rules were scored and the best reaches four in five — and on a pool closed under negation it falls to under half, which says the near-miss is a property of the population. What the second pass does have is a shape and a cheap test that rules it out.

 Not a domination, in the order the rung below meant. The second pass's deletions scored as dominations in two orders: the partial order on games, and the order on stops. Sums and comparison

Not a domination, in that order

The rung below asked which pair the second reduction acts on, taking for granted that the operation is a domination. It is not: on none of the 525 deletions is a surviving option greater than or equal to the deleted one. In the order the reduced form actually works in — both stops at least as good — every deletion with a survivor is a domination, the dominator is unique on all but twelve, and it always comes from the other part.

 The test, scored. The recognition test run on every deletion the second reduction makes, against what actually happens. Sums and comparison

A side about to lose its move

A fifth of the second reduction's work removes the last option a player had on a side, and no rule on the ladder had looked at one — because a deletion with no survivor has no pair in it. The recognisable object is not which option goes but whether the side is one an option can go from, and two comparisons on the parts decide it on all 525.

 A cross in the table. Pairs needing a second reduction, by the colder temperature and the gap between the two. Sums and comparison

A cross in the table

Which pairs need a second reduction had never been asked. Sorted by the two temperatures the answer is a cross — the whole gap-of-a-quarter column and the whole colder-is-three-quarters row — and it is exactly necessary on all 431 with no exception, and wrong 477 times in the other direction.

 The same game, written twice. A position as it arises and the same position reduced. Left would never move to 0 when 2 is available, so that option is dominated and can go. The two games are equal — checked, not assumed — and the second is the canonical form. Values

A reduction that reads a graph

The two reductions are defined as deletions from an option list, and the shared form has no option lists — a node is reached from several parents at once. Both restate as rewritings at a node, the rewriting is confluent, and its fixed point is the canonical form. What does not carry over is the sharing: four fifths of the shared nodes need a different answer under different parents.

The whole library · The position index · The figures that play back