Combinatorial Game Theory
who wins, and by how much
Generator

Four things a position can be

Four things a position can be
Four things a position can be. Every position falls into one of four outcome classes, and only three of them correspond to a comparison with zero. The fourth — first player wins — is a position confused with zero, neither greater, smaller nor equal, and it is where the subject departs from arithmetic.

Every position falls into one of four outcome classes, and only three of them correspond to a comparison with zero. The fourth — first player wins — is a position confused with zero, neither greater, smaller nor equal, and it is where the subject departs from arithmetic.

11 essays call four-outcomes. 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

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

PositionWorth OutcomeDrawn in
-1 −1 R How rare it is to be bigger · Misère play has no negatives · Numbers avoid numbers · The first theorem, and the winner it declines to name · The values that are their own negatives · Three players and no answer · Who moves last · Start at the end and work backwards
-3/2 −3/2 R Nothing worth fighting over
{-1|-2} −1 | −2 R Who moves last
{-2|-1} −3/2 R When a switch is not a switch
{{2 | 1} | {0 | −1}} {{2 | 1} | {0 | −1}} L Nobody wants to move here
{1|-1} 1 | −1 N Misère play has no negatives · Who moves last
{2|-2} 2 | −2 N When a switch is not a switch
{2|1} 2 | 1 L When a switch is not a switch · Who moves last
{4 | {2 | 0}} {4 | {2 | 0}} L Nobody wants to move here
*2 ∗2 N The values that are their own negatives
↑ ↑ L A number and a fight · The class where nobody runs out first · Below zero · Cooling adds and heating does not · Cooling by exactly one · Equal in every company · Turn the board through a right angle · Infinitesimals · Misère play has no negatives · Nobody has to move · Nobody wants to move here · One part that never ends · Three ways to add the same games · Outcomes do not add · The birthday of a sum · The company that is closed · The fight never runs backwards · The simplest game above both · The sum is the object · Toads and Frogs · What a number does to a fight · What a wider pool rescues · What an infinitesimal does to a fight · What can be struck out · What is left when the small change is thrown away · When the ups add · Which part to move in · Who moves last
↑∗ ↑∗ N Infinitesimals · Nobody has to move · Nobody wants to move here · Outcomes do not add · The fight never runs backwards · Toads and Frogs · Two misère outcomes are not enough · What a number does to a fight · What an infinitesimal does to a fight · When the ups add
↓ ↓ R Cooling adds and heating does not · Infinitesimals · Nobody has to move · Nobody wants to move here · Outcomes do not add · The fight never runs backwards · Toads and Frogs · What an infinitesimal does to a fight · Who moves last
−1 −1 R A rule with no promise at all · The fight never runs backwards · The other way to move a row
∗ ∗ N A move that must be answered · A number and a fight · A rule with no promise at all · A self-negative value costs a day · At least five hundred and seventy-one · Below zero · Cooling adds and heating does not · Cooling by exactly one · Equal in every company · Equal in this company · Turn the board through a right angle · Fifty-two errors and seven sizes · How hot a day gets · How rare it is to be bigger · Infinitesimals · Misère play has no negatives · Nobody has to move · Nobody wants to move here · Nothing worth fighting over · Numbers avoid numbers · One part that never ends · Three ways to add the same games · Outcomes do not add · The birthday of a sum · The company that is closed · The fight never runs backwards · The first theorem, and the winner it declines to name · The other way to move a row · The simplest game above both · The thirty that cancel themselves · The values that are their own negatives · Three players and no answer · Toads and Frogs · What a number does to a fight · What a wider pool rescues · What an infinitesimal does to a fight · What can be struck out · What is left when the small change is thrown away · When the ups add · Where the impartial theory stops · Where the order and the sum disagree · Which part to move in · Who moves last · Start at the end and work backwards
0 0 P A rule with no promise at all · A self-negative value costs a day · An option nobody would take · At least five hundred and seventy-one · Equal in every company · Fifty-two errors and seven sizes · How rare it is to be bigger · Nobody has to move · Nothing worth fighting over · The fight never runs backwards · The first theorem, and the winner it declines to name · The operator that puts the star back · The other way to move a row · The simplest game above both · The thirty that cancel themselves · The values that are their own negatives · Three players and no answer · Two people, four years apart, one theorem · What is left when the small change is thrown away · When a switch is not a switch · Where the order and the sum disagree · Who moves last · Start at the end and work backwards
1 1 L A rule with no promise at all · Cooling adds and heating does not · How rare it is to be bigger · Misère play has no negatives · Nobody wants to move here · Numbers avoid numbers · One part that never ends · The fight never runs backwards · The first theorem, and the winner it declines to name · The other way to move a row · The sum is the object · The values that are their own negatives · Three players and no answer · Which part to move in · Who moves last · Start at the end and work backwards
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
1/2 | −1/2 1/2 | −1/2 N Nobody wants to move here · What a number does to a fight
2 2 L Turn the board through a right angle · Misère play has no negatives · Nobody wants to move here · The fight never runs backwards · Two misère outcomes are not enough
2 | 0 2 | 0 N Nobody wants to move here · What a number does to a fight · What an infinitesimal does to a fight
3 | 0 3 | 0 N Nobody wants to move here
3 | 1 3 | 1 L Nobody wants to move here
3·↑ 3·↑ L Nobody wants to move here
3/2 3/2 L Nothing worth fighting over
3/8 3/8 L Nobody wants to move here
4 | 2 4 | 2 L Nobody wants to move here
6 | 0 6 | 0 N Nobody wants to move here

Where it is called

Changing this generator changes every one of these figures.

Backward induction on a game that ends, one round at a time. Zermelo's argument as it actually runs. Round zero is the positions where the player to move has no move at all, which is the only thing the procedure knows without being told; each later round is what those settle. Anything still unlabelled when nothing more can be deduced has no label and never will — and on a game with a cycle in it, that leftover is exactly the set of drawn positions. The theorem is a statement about this procedure terminating, and it names the winner of nothing. How it was found

The first theorem, and the winner it declines to name

Zermelo proved in 1913 that a finite game with no chance and no hidden information is decided before anybody sits down — every position is a win for one side or a draw, and which one is settled already. The proof is a labelling procedure, and watching it run shows exactly how little it says.

 Four things a position can be. Every position falls into one of four outcome classes, and only three of them correspond to a comparison with zero. The fourth — first player wins — is a position confused with zero, neither greater, smaller nor equal, and it is where the subject departs from arithmetic. Values

Who moves last

The player who cannot move loses. That single convention generates the whole theory — and it produces four outcomes rather than three, because a position can be confused with zero rather than greater, smaller or equal to it.

 a loop with a way out: what the backward analysis settles. A position graph in which the moves can lead back to where they started. The labels are the order in which a backward analysis settles each position, starting from the ones where a player has already run out of moves. Positions the analysis never reaches are drawn — and there is no test for that; being unreachable is what a draw is. Where it stops

Start at the end and work backwards

When play can return to where it started there is no bottom for the recursion to stand on. What replaces it begins at the positions where somebody has already lost and propagates outwards — and the positions it never reaches are exactly the draws. There is no test for a draw, and there does not need to be.

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

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.

 The same position, two conventions, two winners. Three-player Nim with the last counter winning. The two columns differ only in what a player does when they cannot win themselves, which is a question the rules do not answer — and the answer decides who wins. Where it stops

Three players and no answer

Every theorem here is about two players, and the reason is not convenience. With two players the game is zero-sum, so 'play well' needs no further explanation. Add a third and the winner of a Nim position becomes a fact about the convention: two reasonable ones disagree on 56 of the 71 positions swept. The one question no convention touches — can a player force a win against the other two together — is answered 'nobody' in 65 of the 71.

 Where a switch stops being a switch. The same Left option with the Right one raised past it. While the Left option is above the Right one both players want to move, the bar spans a real fight and the temperature is half the gap. Where the two meet the position is the number plus a star — no longer a switch, and not a number either. Above that the simplicity rule takes over: the value is the simplest number strictly between the options, and there is nothing to fight about. Values

When a switch is not a switch

A position {a | b} with numbers on both sides is a fight only while a is above b. Sweeping the boundary with a fixed at 2 and b climbing from −2 to 3 turns up three regimes rather than the two the definition suggests: eight fights whose temperature is exactly half the gap, one position at a = b that is 2∗ and is not a number, and beyond that numbers chosen by the simplicity rule — which on 8 of 12 sampled cases is not the midpoint.

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

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.

 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. Particular games

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.

 Four rules over 220 sums. Each rule plays every sum against an opponent evaluating exactly. Two of the rules come with a bound and two do not; the coldest rule is the control, and it violates the bound often enough to show that being inside it is a real constraint rather than a description of the pool. Temperature

A rule with no promise at all

Playing in a hottest component comes with a bound: never more than the largest single temperature below the mean of the board. Over 220 sums the bound holds 220 times — and so does the bound for a rule with nothing behind it, which scores exactly what perfect play scores on 205 sums against the hottest rule's 196. The control that shows the bound is doing work is the rule that plays the coldest component, which breaks it 74 times and loses up to eleven points.

 What each move is worth to the player making it. For each position: every incentive, whether they are all strictly negative, whether the position is a number, and its temperature. The middle two columns are two different computations of the same fact. Values

Nobody wants to move here

A position is a number exactly when every move loses ground for the player making it. The test never mentions numbers, it disagrees with the ordinary one on none of the 1,474 values born by day three — and the reason a position fails it is not that somebody wants to move. It is that somebody cannot afford to wait.

 Push and Shove over every strip up to 6 squares. The same strips under both rules. A cliff lets coins fall off and a wall does not, and the census says what that one clause is worth: both games are entirely made of numbers, they never agree on a value, and the obvious board-reading is right far more often under the wall than under the cliff. Particular games

The other way to move a row

Shove has a cliff and Push has a wall, and that is the whole of the difference. Both games make every one of the 728 strips up to six squares a number, so neither ever has anything worth fighting over — and the two rules do not agree on the value of a single position. The obvious board-reading is exact on 446 strips under the wall and on 140 under the cliff, and 486 strips contain a coin its owner cannot move at all.

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