Combinatorial Game Theory
who wins, and by how much
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.
17 min read 8 figures Who moves lastNot every game is a number

Two players move alternately. There is no dice, nothing is hidden, and both can see the entire position. Play ends when somebody has no legal move, and that player loses.

That is the whole set of rules, and everything in this subject is downstream of the last clause.

Four things a position can beEvery 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.0outcome P= 0whoever must move, loses10outcome L> 0Left wins, whoever starts-10outcome R< 0Right wins, whoever starts∗00outcome N‖ 0whoever moves first, winsblue edges are Left's moves, red are Right'sthree of the four are comparisons with zero; the fourth is not
Fig. 1 The four things a position can be. Blue edges are moves available to Left, red ones to Right, and the number in each circle is the value the recursion computes. Only three of the four are comparisons with zero.

It is called the normal play convention, and the alternative — the player who cannot move wins — is called misère and breaks nearly everything. Naming which one is in force is not pedantry; almost no theorem below survives the swap.

The base case, which is a position

The recursion has to start somewhere, and it starts at the position with no moves at all.

Neither player can move, so whoever is to move loses. Equivalently: whoever moved last won. That position is written { | } — empty on both sides — and it is called zero.

Zero is not a number that has been attached to a position. It is a position, and the fact that it behaves like the number zero when positions are added is a theorem rather than a definition.

Every other game is built from it. A game is written

G={ GL,…∣GR,… }G = \{\, G^L, \ldots \mid G^R, \ldots \,\}

where the left-hand list is the positions Left can move to and the right-hand list is Right’s. Nothing else. A game is its options, and everything the theory computes — values, comparisons, sums, temperature — is derived from that recursion and the base case.

Four outcomes, not three

Given a position, there are two independent questions: can Left win if Left moves first, and can Right win if Right moves first? Two yes-or-no questions give four combinations, and all four occur.

P — the previous player wins, which is to say the player to move loses. Neither player can win by moving first.

L — Left wins whoever moves first.

R — Right wins whoever moves first.

N — the next player wins. Whoever moves first wins, so the outcome depends on whose turn it is.

Three of those correspond to comparisons with zero: a position in L is worth more than zero, one in R less, one in P exactly zero. The fourth does not. A position in N is not greater than zero, not less, and not equal — it is confused with zero, written G∥0G \parallel 0.

That is the moment the subject stops being arithmetic, and it happens on the first page.

The smallest example

The smallest position that is confused with zero is {0∣0}\{0 \mid 0\}: either player may move, and moving leaves the other with nothing.

It is called star, written ∗\ast, and whoever moves first wins — so it is in class N. Compare it with zero and none of the three relations holds.

∗≯0,∗≮0,∗≠0.\ast \not> 0, \qquad \ast \not< 0, \qquad \ast \neq 0.

A reader who has only met totally ordered things will look for the mistake. There is none. Two games are comparable when one player can win their difference playing second, and for ∗\ast and 00 neither can — the first player wins the difference, whoever that is.

A green edge is not a numberGreen edges may be cut by either player, which makes the position impartial in that part. A single green edge is worth ∗ — a value that is neither positive, negative nor zero, and which no number can equal.∗not a numberoutcome N∗2not a numberoutcome N{1 | 1}not a numberoutcome L↑∗not a numberoutcome Ngreen may be cut by either playerand that is enough to leave the number line
Fig. 2 Where star turns up in a real game. A single green Hackenbush edge — one that either player may cut — is worth exactly ∗, and adding one to a position that was a number takes it off the number line entirely.

Why the order is partial

The four outcomes are a symptom of something structural: games are only partially ordered.

For numbers, any two are comparable. For games, comparison is defined by

G≥H  ⟺  Left wins G−H moving second,G \ge H \iff \text{Left wins } G - H \text{ moving second,}

and there is no reason every pair should satisfy that in one direction or the other. When neither does, the two are confused, and the relation ∥\parallel is as legitimate as << or >>.

Comparing two positions is playing their differenceTo 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.↑ − 0= ↑outcome L↑ > 0∗ − 0= ∗outcome N∗ ‖ 0⇑ − ↑= ↑outcome L⇑ > ↑1/2 − 1/4= 1/4outcome L1/2 > 1/4↑∗ − ∗= ↑outcome L↑∗ > ∗the differencethe verdict‖ means confused: neither greater, nor smaller, nor equal — and no amount of care removes it
Fig. 3 Comparison as a computation. To decide whether one position is worth at least another, subtract and see who wins moving second. Some pairs come out confused, which no comparison of numbers ever does.

This is not a defect to be engineered away. It is the phenomenon the subject is about. A totally ordered theory of games would be a theory in which every position could be summarised by a single number on a line, and real games are not like that — whose turn it is matters, and ∥\parallel is how that shows up in the algebra.

Why more options can only help

Before any of that, one lemma is worth stating on its own, because it is used silently everywhere and it is the exact point where normal play enters the algebra.

Adding an option for Left cannot hurt Left.

Suppose GG and HH are identical except that Left has one extra move available in GG. Then G≥HG \ge H. The proof is the mirroring argument again: playing G−HG - H second, Left copies Right’s moves across the two components, and the extra option is simply never needed — but it is there if it helps.

This sounds too obvious to state. It is not, and the evidence is that it is false under misère play, where an extra option can be exactly the thing that forces a player to make the last move and lose. Every monotonicity result on this site — that a bigger heap is better, that a longer Hackenbush stalk is worth more, that removing a dominated option changes nothing — descends from this lemma, and therefore from the convention.

The value of LRL is computed, not readOne string with every option drawn. Left's moves are the blue edges she may cut, Right's the red ones; each leaves the part of the string still standing. The value follows from those options by the same recursion that defines every game in the subject.3/4the positionLeft cuts blue, leaving01/2Right cuts red, leaving1{1/2 | 1}
Fig. 4 The same Hackenbush stalk with one extra edge, and the values either side of it. More available to Left moves the value up the line, and never down, which is a theorem about normal play rather than an observation about pictures.

Once monotonicity is available, the machinery of canonical form becomes possible: an option that is worse for its owner than another option the same player has can be deleted without changing the value, because its owner would never need it. That is what “dominated” means, and it is the first of the two reductions that make values unique.

Outcome is not enough

A natural next thought is that outcome classes might be all anybody needs. Four classes, a rule for combining them, and the theory is finished.

They are not, and the failure is easy to demonstrate.

Knowing who wins is not enoughThree pairs of positions, every one of which is a first-player win on its own. Their sums are not all the same, and not all in the same outcome class — so the outcome of a sum cannot be worked out from the outcomes of its parts, and that is why the theory needs values.∗ + ∗N + N0outcome P∗ + ∗2N + N∗3outcome N↑∗ + ↑∗N + N⇑outcome Leach part is a first-player winthe sumsame outcome classes going in, different outcomes coming outso a position has to be given a value, not merely a winner
Fig. 5 Three pairs of positions, every one of which is a first-player win on its own. Their sums are not all the same and not all in the same class, so the outcome of a sum cannot be worked out from the outcomes of the parts.

Take ∗\ast and ∗\ast: both class N, and their sum is zero, class P. Take ∗\ast and ∗2\ast 2: both class N, and their sum is ∗3\ast 3, class N. Same classes going in, different classes coming out.

So an outcome class does not determine how a position behaves when it is added to another, and since real positions are always sums of independent parts, outcome classes on their own are nearly useless. What is needed is a value — an object fine enough that the value of a sum is the sum of the values.

That requirement is what forces the whole apparatus. Everything after this point exists because outcomes do not add.

What “equal” has to mean

Given that, equality cannot mean “the same outcome”. It has to mean something that survives addition, and there is only one sensible candidate:

G=H  ⟺  G+(−H) is a second-player win.G = H \iff G + (-H) \text{ is a second-player win.}

Two games are equal when their difference is worth nothing, which is exactly when either can be substituted for the other inside any larger position without changing who wins it.

Two positions, one valueA 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.1/2a blue edge with a red one above=verified, not asserted{0 | 1}1/2the number one halfequal means interchangeable in every sum, which is a much stronger claimtheir difference is 0, and its outcome is P
Fig. 6 Two positions with the same value: a Hackenbush sprig and an abstract game. Equality is not a statement about them in isolation — it says either can replace the other anywhere, and nothing about any outcome will change.

That is a far stronger claim than it first appears, and it is what makes values worth computing. A value is not a score. It is a certificate of interchangeability.

Negation, and playing the other side

The definition above needs −H-H, and it is exactly what it should be: the same game with the players swapped.

−G={ −GR∣−GL }-G = \{\, -G^R \mid -G^L \,\}

Left’s options become Right’s and Right’s become Left’s, recursively. In Hackenbush that is repainting every blue edge red and every red edge blue. In Domineering it is rotating the board ninety degrees.

The difference G−HG - H is then G+(−H)G + (-H): play both positions at once, with the second one’s sides reversed. If the two are worth the same, whoever moves second can mirror every move in the other component and always have a reply — which is why the difference is a second-player win, and why the definition is the right one.

That mirroring argument is the whole proof, and it is the standard trick of the subject.

Reading a position out loud

The notation is compact to the point of hostility, and it is worth slowing down on it once, because every later essay uses it without comment.

{0∣0}\{0 \mid 0\} — Left can move to zero, Right can move to zero. That is ∗\ast.

{0∣∗}\{0 \mid \ast\} — Left can move to zero; Right can move to star. That is ↑\uparrow, and it is positive but smaller than every positive number.

{1∣0}\{1 \mid 0\} — Left moves to a position worth one, Right to a position worth nothing. Left’s option is better for Left than Right’s, which is what makes this a hot position rather than a number, and it is the shape temperature is about.

{0∣1}\{0 \mid 1\} — the reverse, and it is worth exactly 12\tfrac12 by the simplicity rule, because 12\tfrac12 is the simplest number strictly between 00 and 11.

The last two look nearly the same and behave completely differently. When Left’s best option is worse for Left than Right’s best is for Right, the position settles down to a number and neither player is in a hurry. When it is better, both players want to move there first, and the position is worth fighting over. That distinction — which side of the inequality the options fall on — is the single most useful thing to notice about a position, and it is visible in the braces once the notation stops being noise.

This site’s rule is that a figure showing brace notation also shows the position it describes, because the braces are a compression and the position is the thing.

The convention is doing all the work

It is worth returning to the opening clause, because everything above rests on it.

Under normal play, “having a move” is good and “running out” is fatal. That makes a game with more options for Left better for Left, which makes the ordering behave, which makes sums behave, which makes values exist.

Reverse it — the player who cannot move wins — and every one of those steps fails. Having options becomes a liability, the ordering collapses, and the equivalences that make the theory work simply stop holding.

The same game, the opposite endingNim under normal play, where the player who cannot move loses, and under misère play, where they win. The positions are identical and only one class of them changes hands — which makes misère Nim look easy and is deeply misleading about misère play in general.heapsnormalmisère1, 1, 1NPthe answer flips1, 2, 3PPunchanged1, 1, 1, 1PNthe answer flips2, 2PPunchanged1, 1, 5NNunchangedmisère Nim differs only when every heap has one counterwhich is a special property of Nim, and not a feature of misère play at all
Fig. 7 The same game under both conventions. Only one class of Nim position changes hands, which makes misère Nim look easy and is thoroughly misleading about misère play in general.

Almost every result on this site is a theorem about who moves last. Stating the convention is therefore stating the hypothesis, and a result quoted without it is a result quoted without its assumptions.

Who found it, and when

The convention is old and the theory is recent, which is the usual shape in this field.

Nim was solved by Charles Bouton at Harvard in 1901 — the nim-sum, the winning strategy, the lot — and it stood as an isolated curiosity for forty years. Roland Sprague in 1935 and Patrick Michael Grundy in 1939 independently showed that every impartial game is a Nim heap, which generalised Bouton enormously and still only covered games where both players have the same moves.

The partizan theory — the four outcomes, the values, the sums, the whole apparatus above — is John Conway’s, worked out around 1970 and published in On Numbers and Games in 1976. Winning Ways, with Berlekamp and Guy, followed in 1982 and is where most people meet it.

So the framework this essay describes is younger than the transistor, and it was largely one person’s.

Where the model stops

Two players, alternating. Three-player games have no comparable theory, because coalitions become possible and the whole notion of a value breaks down.

No chance, nothing hidden. Both are essential. A game with dice has expected values rather than exact ones; a game with hidden information has beliefs, which is a different subject.

Play ends. The recursion assumes every line terminates. Loopy games do not, and they need separate machinery and admit a fifth outcome — a draw — which nothing here has a name for.

Normal play. As above, and it is the assumption most often left unstated elsewhere.

The figures show tiny positions. Every game drawn on this page has at most a handful of options. That is where the theory is exact and visible, and it is not where any interesting game lives — a real position has too many options to draw, which is a limit worth being explicit about.

What a value cannot tell anybody

One more caution, since the rest of the site is a machine for computing values.

A value says who wins and by how much, in a precise sense: it says exactly how the position behaves in every possible sum. It does not say what to play. Two positions can be worth the same and require completely different moves, and knowing a component is worth ↑\uparrow does not identify the move that keeps it worth ↑\uparrow.

Nor does the value record how the position was reached, how long the game will run, or which of several winning moves is most robust against a fallible opponent. Values are a theory of perfect play against perfect play, and against an opponent who blunders they are sometimes the wrong guide entirely.

Nim from 1, 2, 3 — and who winsA Nim position with the outcome stated before anybody moves. The reply to every move a reader can make was computed in advance from the nim-sum, so the machine is not searching or guessing — it is following the theorem, and there is no line of play in which it loses.123nim-sum 0the player to move losesstated before a move is madewith the script running, the heaps become clickable and this claim can be tested
Fig. 8 The winner is named before the first move. That is the whole demonstration — the replies were computed at build time from the theory, so a reader who wins here has found a mistake in a theorem rather than in an opponent.

Where the move matters, the figures on this site give the move as well as the value. Where a position is too large to evaluate exactly, the essay says so rather than quoting a number the code did not produce.

The ladder from here

Later rungs: the four outcomes derived from the two questions. Comparison and the partial order, proved. Negation and the mirroring argument. The simplicity rule. Canonical forms. Numbers, and the games that are not. Star, up and down. Sums and the additivity theorem. Misère play and what it costs. Loopy games and the fifth outcome. And the question of whether outcome classes ever suffice, which they do for impartial games and essentially nowhere else.

Conway’s On Numbers and Games builds the real numbers, the ordinals, and the theory of games from the same construction, in the same book, starting from a position in which neither player can move. The first chapter creates zero from nothing and the rest follows.

Where this goes next

011/2{0 | 1}021{0 | 2}-550{-5 | 5}1/43/41/2{1/4 | 3/4}13/25/4{1 | 3/2}the marked point is the value; the hollow one, where it differs, is the midpoint The simplicity rule When both players' options are numbers, the position is worth the simplest number strictly between them. Not the midpoint, not the average, and the difference between "simplest" and "middle" is the entire content of the rule. 2+-1+1/4+∗={5/4 | 5/4}outcome Leach sprig is a separate game; a move is a move in one of themthe total was computed by adding the games, not the labels The sum is the object Real positions come apart into independent regions, and a move happens in exactly one of them. That operation — the disjunctive sum — is what the whole theory is built to survive, and it is the reason values exist at all. 301151017111nim-sum001= 1some column does notthe player to move winstake 1 from the heap of 3outcome N Nim, and the nim-sum Three heaps of counters, take as many as you like from one of them, and the player who takes the last counter wins. The winning condition is not a search, not a table, and not a heuristic — it is the bitwise exclusive-or of the heap sizes, and it was found in 1901.