Combinatorial Game Theory
who wins, and by how much
Generator

Two positions, one value

Two positions, one value
Two positions, one value. A Hackenbush sprig and an abstract game with the same value. Being equal means more than being worth the same in isolation: either can be substituted for the other inside any larger position, and nothing about who wins will change.

A Hackenbush sprig and an abstract game with the same value. Being equal means more than being worth the same in isolation: either can be substituted for the other inside any larger position, and nothing about who wins will change.

11 essays call same-value. 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

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

PositionWorth OutcomeDrawn in
LR 1/2 L Canonical form · Comparing positions · Squash every loop to a point · Hackenbush is a numeral · Nobody comes back · Nothing worth fighting over · The numbers came out of the game · The other sum, the one that nests · The reading that survives too much · The simplicity rule · The sum is the object · The values nobody's game produces · What the colon respects
LRL 3/4 L Squash every loop to a point · Hackenbush is a numeral · Nothing worth fighting over · The numbers came out of the game · The other sum, the one that nests · The reading that survives too much · The simplicity rule · The values nobody's game produces · What the colon respects · When the nested sum only sees the value
1/2 1/2 L Below zero · Canonical form · Comparing positions · Cooling adds and heating does not · Cooling by exactly one · Equal in every company · Turn the board through a right angle · How hot a day gets · Misère play has no negatives · Nobody comes back · Nobody wants to move here · Numbers avoid numbers · The fight never runs backwards · The operator chosen for one game · The operator that puts the star back · What is left when the small change is thrown away
3/4 3/4 L Turn the board through a right angle · Misère play has no negatives · When the nested sum only sees the value

Where it is called

Changing this generator changes every one of these figures.

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

Comparing positions

One position is worth at least another when the second player wins their difference. That is the only definition there is, it is a computation rather than a judgement, and it produces an order in which some pairs are simply not comparable.

 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.

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

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.

 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.

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

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.

 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. Where it stops

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.

 How much of the value the colon respects. Every form whose option lists are antichains of day-two values, grouped by the value it reduces to, and each group asked whether all its forms give the same ordinal sum with star. On 636 of the 640 groups they do. Sums and comparison

What the colon respects

The ordinal sum reads the form of its base rather than its value, which is why the colon principle is stated for positions and not for values. Built over 9,604 forms it turns out to read the value on 636 of the 640 values that have more than one form, and the four it can tell apart are zero, one, minus one and star — the values born by day one, and no others.

 No fifth value. Forms of day-three values built by adding day-three gift horses, and the ordinal sums they give. Over eighteen thousand forms and four followers, no value's forms disagree. Sums and comparison

No fifth value

The colon reads a form rather than a value, and the rung below found the forms of a value disagreeing at exactly four of them — the values born by day one. It could only check forms whose options came from day two. Built one day deeper, by adding day-three gift horses to day-three values, eighteen thousand forms give no disagreement at all, while the same treatment still splits nought four ways. The class is about the width of the base's form and not the depth of its options.

 The proposed case, scored. The gift-horse theorem and the domination argument proposed for it, each scored over every gift horse added. Sums and comparison

The proof needs both reductions

The gift-horse theorem was to be proved by showing the added option dominated. It is, on 97.8 per cent — and the other 232 are reversible instead, with nothing left over. The case the proposal missed is almost entirely one follower: none under a positive number, 190 under a negative one.

 The reversing move is the follower's. For each follower under which some gift horse escapes domination, the number of escapes, how many are reversed by Right's move inside the follower, and how many by a Right move in the base part. The follower's move reverses every one. Sums and comparison

The follower does the reversing

The gift-horse theorem for the ordinal sum needs two cases, and the second — the added option is reversible — was counted and not described. Recorded move by move, the reversing answer is always Right's move inside the follower: on all 410 escapes under five followers, and on every one of the 2,628 gift horses under every follower that gives Right a move at all. The case split is by follower, not by horse.

 What survived, and what did not. The gift-horse theorem, the two-case proof and the one-line description of the reversal case, each scored on the day-three sweep and its mirror and on the day-four sweep and its mirror. Sums and comparison

The split slips one day deeper

The reversal case of the gift-horse theorem was described in one line — the follower's own move reverses every gift horse, whenever the follower has one — and tested only where it was found. In the mirror it holds exactly, with 1 and −1 trading places. One day deeper it fails: under ↑ and ½, three gift horses on built day-four bases are not reversed by the follower's move. All three are dominated, so the theorem stands; the clean split by follower does not.

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