Combinatorial Game Theory
who wins, and by how much
Sums and comparison

Which part to move in

The value of a sum is the sum of the values. The move in a sum is not the move in any part, and there is no rule that reads it off the values — in the smallest interesting example, the only winning move is in the component worth nothing.
17 min read 8 figures The sum is the objectNot every game is a numberSmall things decide

The additivity theorem is the reason this subject exists. A position that breaks into independent parts has a value equal to the sum of the parts’ values, so a dozen small regions can be evaluated separately and added rather than searched as one enormous tree.

It is worth being exact about what that buys, because it is less than it first appears. The theorem is about values. It says nothing whatever about moves.

Which part to move inA sum, and every move one player has in it. Each row is a component, the option taken in it, and what the whole position becomes. The values of the parts say who wins; they do not say where to play, and the winning move here is in the component worth the least.↑ + ∗worth ↑∗, outcome NLeft to movemove inleavingthe whole position becomesverdict↑0∗loses∗0↑winsexactly one of the 2 moves wins, and it is in ∗each verdict is the outcome of the whole position after the move, computed rather than judged
Fig. 1 The smallest sum where the point is visible. Left has two moves: one in the up, one in the star. The up is worth something and the star is worth nothing, and the only move that wins is the one in the star.

The smallest example

↑\uparrow is positive. Left wins it whoever moves first, and it is smaller than every positive number but genuinely greater than zero.

∗\ast is confused with zero. Whoever moves first wins it, and it is worth nothing in the sense that nobody is ahead.

Add them. ↑+∗\uparrow + \ast is ↑ ⁣∗\uparrow\!\ast, which is confused with zero — so whoever moves first wins the sum. Left, moving first, has exactly two options, and they can be listed in full.

Move in the up. ↑\uparrow is {0∣∗}\{0 \mid \ast\}, so Left’s only option there is 00. The sum becomes 0+∗=∗0 + \ast = \ast. It is Right’s turn, ∗\ast is a first-player win, Right takes it and Left has lost.

Move in the star. ∗\ast is {0∣0}\{0 \mid 0\}, so Left’s option there is 00. The sum becomes ↑+0=↑\uparrow + 0 = \uparrow. It is Right’s turn, ↑\uparrow is positive, Left wins whatever Right does.

One of two moves wins, and it is the one in the component that was worth nothing. A player reasoning that the up is the asset and should be developed would lose. A player reasoning that the star is worth nothing and should be left alone would lose.

What went wrong with the intuition

The intuition being violated is that a component’s value measures how much a player should care about it. It does not, and the reason is worth stating precisely.

Moving in a component changes it, and the change is what matters, not the level. Left’s move in the up takes it from ↑\uparrow to 00 — a loss of ↑\uparrow. Left’s move in the star takes it from ∗\ast to 00 — a change of ∗\ast, which is not a loss at all because ∗\ast is not positive.

So the correct accounting is by differences, and a component’s value tells nothing about what its options do. A component worth a great deal may offer only moves that destroy that value; a component worth nothing may offer a move that costs nothing.

Which part to move inA sum, and every move one player has in it. Each row is a component, the option taken in it, and what the whole position becomes. The values of the parts say who wins; they do not say where to play, and the winning move here is in the component worth the least.∗ + ∗2worth ∗3, outcome NLeft to movemove inleavingthe whole position becomesverdict∗0∗2loses∗20∗loses∗2∗0winsexactly one of the 3 moves wins, and it is in ∗2each verdict is the outcome of the whole position after the move, computed rather than judged
Fig. 2 The same shape in a purely impartial position. Both components are first-player wins on their own, the sum is a first-player win, and of the three moves available exactly one leaves the opponent with nothing — the move that makes the two heaps equal.

That impartial case is the familiar one and is worth setting beside the partizan one, because in the impartial world the rule is readable off the values: take the nim-sum and equalise it. The winning move is computed from the parts by a formula.

The partizan world has no such formula, and the reason is structural. The nim-sum works because impartial values live in a group where every element is its own inverse, so “which component to change, and to what” has an arithmetic answer. Partizan values live in a partially ordered abelian group with no such property, and the move has to be found by asking each option what it does to the whole.

Three components

With two components the listing is short enough to be unconvincing. Here is a sum with three, and it is a sum a real position could produce: an infinitesimal, a settled point, and a fight.

Which part to move inA sum, and every move one player has in it. Each row is a component, the option taken in it, and what the whole position becomes. The values of the parts say who wins; they do not say where to play, and the winning move here is in the component worth the least.↑ + 1 + {0 | -2}worth {{1 | {1 | 1}} | {-1 | {-1 | -1}}}, outcome NLeft to movemove inleavingthe whole position becomesverdict↑01 | -1loses10{{0 | {0 | 0}} | {-2 | {-2 | -2}}}loses{0 | -2}0{1 | {1 | 1}}winsexactly one of the 3 moves wins, and it is in {0 | -2}each verdict is the outcome of the whole position after the move, computed rather than judged
Fig. 3 Three components and every move Left has among them. Only one wins, and the two that lose fail for different reasons — one spends a move on a settled region, the other throws away the infinitesimal that was holding the position together.

The move in the number loses for the reason numbers avoid numbers gives: it spends a turn on a component with nothing at stake. That much is a theorem and could have been predicted.

The move in the up loses for a different reason and no theorem covers it. The up was the entire margin — the difference between the fight resolving in Left’s favour and against — and giving it away leaves the fight decided the wrong way. There is no rule that identifies the up as load-bearing except computing what happens without it.

The same problem in a game somebody plays

The examples so far are written in braces, which makes them easy to check and easy to dismiss as constructions. The situation is not a construction.

A position is the sum of its partsFour separate Hackenbush sprigs. A move is a move in one of them, so the position is their disjunctive sum, and its value is the sum of their values. Which part to play in is the entire decision, and the values are what makes it decidable.3/2+−1/2+∗+1/2={3/2 | 3/2}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
Fig. 4 Four Hackenbush sprigs standing separately on the ground. A move is a cut in one of them; the position is their sum, and the total was computed by adding the games rather than the labels. Which sprig to cut is the whole of the decision a player faces.

Four sprigs, four values, one total. A player with the total knows who wins. A player deciding what to cut has to work out, for each of the nine or ten possible cuts, what the total becomes — and the values of the individual sprigs do not shortcut that, for the same reason they did not in ↑+∗\uparrow + \ast.

The green edge is the interesting one. It is worth ∗\ast, which is to say worth nothing, and it is frequently the cut that matters, because removing it is the only move either player has that costs them nothing at all.

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↑∗not a numberoutcome N{1 | 1}not a numberoutcome L∗2not a numberoutcome Ngreen may be cut by either playerand that is enough to leave the number line
Fig. 5 Green edges and what they are worth. A green edge either player may cut is star; a green edge with a blue one above it is up-star, which is positive; and the arrangement decides which. A sprig worth nothing and a sprig worth an infinitesimal look nearly identical and behave completely differently in a sum.

That pair of figures is the practical form of the essay’s claim. Two sprigs that differ by one edge can have values that differ by an infinitesimal, and the infinitesimal can be the entire content of the position — while a third sprig, worth a whole point more than either, offers no move worth making.

What the solver computed, and how

The figures on this page are listings, not arguments, and every verdict in them is the output of the same recursion.

The construction is direct. Each component is built from its written form; the sum is built by add; the canonical form of each component supplies its option list. For each option in turn, the sum is rebuilt with that component replaced by that option, and the resulting position is asked one question: can the opponent, moving next, win it? A move that leaves the opponent unable to win is marked as winning, and every other move is not.

That question — rightMovesFirstWins of the position after the move — is the definition of a good move and not an approximation to it. There is no search depth, no evaluation function and no cut-off, because the positions are small enough to unroll completely.

The listing is exhaustive rather than filtered. The figures show every option each component has, including the ones that lose, because a figure that showed only the winning move would be asserting the conclusion instead of demonstrating it.

The site’s gate makes the general claim these figures instantiate. It builds sums of a number and a non-number, finds every winning move by the recursion, and requires that at least one of them lies in the non-number component — the number-avoidance theorem, checked rather than quoted. And it separately requires the check to come out false on sums of two numbers, where no component offers a free move, so that a test which passed everything could not masquerade as a test that passes.

Where the model stops

Exhaustive listing is exactly as far as these positions go. Every figure here has fewer than a dozen options. A real position has hundreds, and listing them is not a method — it is what a method has to replace. Temperature is the replacement, and it is approximate.

A verdict is about optimal play from both sides. “This move wins” means it wins against every reply. Against a fallible opponent, moves that lose to perfect play may be better, and nothing here has anything to say about that.

The decomposition is assumed, not derived. Every figure starts from a position already written as a sum of independent parts. Establishing that a real position decomposes — that no move in one region affects another — is a separate piece of work, and in some games it only becomes true partway through.

Normal play, and the components are loopfree. A component from which play can return has no value in this sense and cannot be added to anything, which is a restriction with its own consequences.

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. 6 The result one rung below, for contrast. Outcome classes do not determine the outcome of a sum, which is why values exist. This essay is the same complaint one level up: values do not determine the move, and nothing on this site claims to fix that.

What replaces the listing

The practical answer is temperature, and it is worth saying exactly how much it delivers.

Compute each component’s temperature. Play in the hottest. That rule is not correct, and it is correct up to a bounded error: a player following it finishes within the largest temperature of the position of what optimal play would have achieved. For a game with many components of widely varying sizes that is a good bound; for a game that comes down to two components of equal temperature it is no bound at all.

Move where it is hottestFour independent components of one position, ordered by temperature. The temperature is how much a player loses by moving somewhere else instead, so the hottest component is the one to take — and a component that is already a number has no temperature at all, because nobody gains by moving in it.{6 | 0}t = 3a big fight{2 | 0}t = 1a smaller one{1 | 0}t = 1/2small change{0 | 1}no temperaturesettled — a numbercomponenthow much is at stakethe whole position is worth {{{19/2 | 17/2} | {15/2 | 13/2}} | {{7/2 | 5/2} | {3/2 | 1/2}}}and the first move goes in the hottest part, which is a theorem up to a small error rather than a rule of thumb
Fig. 7 The rule that replaces exhaustive listing. Components sorted by what is at stake, with the settled one last. It is a theorem up to a bounded error rather than a rule of thumb, and the bound is the largest temperature on the board.

The bound is where the infinitesimals come back. When two components have equal temperature, the hottest-first rule cannot separate them and the decision falls to a quantity smaller than any number — which is why ↑\uparrow and ∗\ast are not curiosities but the tie-breakers of a close game.

That is the honest summary of what this subject offers a player. The values reduce an intractable search to arithmetic. The arithmetic identifies who wins. Finding the move needs one more layer, that layer is approximate, and the error term is made of exactly the objects that look too small to matter.

Why the difference cannot be arranged away

A natural response to all of this is to look for a better invariant — some quantity attached to a component that would determine the move. It is worth explaining why the search fails rather than merely reporting that it has.

Suppose such a quantity existed: a function μ\mu on positions with the property that the right move in G1+G2+…G_1 + G_2 + \ldots is always the move that maximises some combination of the μ(Gi)\mu(G_i) and the μ\mu of the options. Then two components with the same μ\mu and the same option-$\mu$s would be interchangeable for the purposes of choosing a move.

They are not. ↑\uparrow and ∗\ast both have a single Left option worth 00. Whatever μ\mu assigns to that option, it assigns the same thing to both, so any rule of the shape above treats Left’s two moves in ↑+∗\uparrow + \ast identically — and one of them wins while the other loses.

The escape would be to let μ\mu depend on the rest of the position as well as the component, and at that point it has stopped being a property of the component and become a re-description of the original problem.

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. 8 The reason the escape is not available. Comparison in this subject is a computation on the whole difference, and some pairs come out confused rather than ordered. A quantity that ranked every component on a line would be imposing a total order on objects that are only partially ordered, and the confused pairs are exactly the ones where the move matters.

What survives is temperature, and it survives by being explicitly approximate. It ranks components on a line, it is a property of each component alone, and it comes with a stated error rather than a claim of correctness. That is the most a local quantity can do, and the theorem that says so is a bound rather than an equality.

The generalisation

There is a general principle here that has nothing to do with games, and it is worth naming because it explains why the subject’s central theorem is so easily over-read.

Additivity of a value under composition is a strong and useful property. Additivity of the argmax — of the decision that produces the value — is a much stronger property, and it almost never holds. A function can decompose beautifully while the choice that optimises it does not decompose at all.

In this subject the gap between the two is unusually visible because both sides can be computed exactly and compared. In most places it is invisible, and a decomposition theorem gets quietly used as though it licensed local decisions.

The one case where the argmax does decompose is the impartial one, and it decomposes because the value group is Z2 ∞\mathbb{Z}_2^{\,\infty} under exclusive-or, where changing one component to fix the total is always possible and always unique. That is a fact about the group, and it is the reason Sprague–Grundy is as strong as it is and why nothing like it exists for partizan games.

Who found it, and when

The additivity theorem is Conway’s, and so is the recognition of its limits. On Numbers and Games is careful throughout to state results about values rather than about play, and the temperature theory that follows exists precisely because values are not enough for a player.

The practical version came from Go. Berlekamp’s endgame work in the 1990s is a sustained attack on exactly this problem — the values of the regions are known, and the question is where to play — and the machinery it produced is considerably heavier than the additivity theorem that motivates it.

The impartial case had been settled forty years earlier by Sprague and Grundy, and the contrast between the two is instructive. The impartial answer is a formula anybody can execute; the partizan answer is a research programme, and the reason for the difference is one algebraic property of the value group.

The ladder from here

This anchor began with the disjunctive sum and the additivity theorem, which is the reason a position can be broken up at all. This rung says what breaking it up does not buy.

Later rungs: the temperature bound stated and proved, with the error term made explicit. Sums with many components of equal temperature, where the bound is worthless and the infinitesimals decide. The reduced canonical form, which is what happens when a value is stripped of everything that does not affect play against a large background. And the algorithmic question — finding an optimal move in a sum is hard even when every component is trivial, which is a result about sums rather than about any game in them.

The thing to carry is the distinction the essay is built on. Knowing what a position is worth and knowing what to play in it are different pieces of information, both computable, and the theory computes the first far more cheaply than the second.

Where this goes next

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. {2 | 0} + 1worth 3 | 1, outcome L — Left wins whoever movesLeft moves in the fight{2 | }worth 3outcome Lstill a win for LeftLeft moves in the number{2 | 0}worth 2 | 0outcome Nnow whoever moves next wins — and it is Right's turnthe number was worth a whole point and moving in it cost the gamea number is never the right move while anything that is not a number is available Numbers avoid numbers In a position with a number in it and anything else, the number is never the right move. That is a theorem rather than a heuristic, and it is the closest this subject comes to advice a player can carry into a real game. {6 | 0}t = 3a big fight{2 | 0}t = 1a smaller one{1 | 0}t = 1/2small change{0 | 1}no temperaturesettled — a numbercomponenthow much is at stakethe whole position is worth {{{19/2 | 17/2} | {15/2 | 13/2}} | {{7/2 | 5/2} | {3/2 | 1/2}}}and the first move goes in the hottest part, which is a theorem up to a small error rather than a rule of thumb Playing the hottest Given several independent fights, play in the one with most at stake. The rule is simple, it is what strong Go players do without being told, it is provably close to optimal — and it is provably not optimal, which is the interesting part.