The sum is the object

Late in a game of Go the board is not one position. It is a dozen small independent fights, none of which affects any other, and a move goes into exactly one of them.

That decomposition is not a convenience. It is the structure the entire theory is built around, and the operation that describes it is called the disjunctive sum.

The definition #

Given games $G$ and $H$, their sum $G + H$ is the game in which a move consists of choosing one component and making a legal move in it, leaving the other untouched.

Formally,

$$G + H = \{\, G^L + H,\; G + H^L \mid G^R + H,\; G + H^R \,\}$$

Left’s options are: move in $G$, or move in $H$. Same for Right. The components never interact.

Play ends when neither component has a move, so under normal play the loser is whoever faces a sum in which every component is exhausted.

Why this is the operation that matters #

Two reasons, and the second is the deeper one.

Real positions decompose. A Go endgame, a Domineering board that has broken into disconnected regions, a Hackenbush picture of several separate drawings, a Nim position of several heaps — all of these are sums, and none of them can be analysed as a single monolith without an explosion in the state space.

A theory of single positions would be worthless. Suppose the only question ever asked were “who wins this position”. The answer would be one of four outcome classes, and it would be a fact about that position and nothing else. It would not compose. Analysing a board of six regions would require analysing the whole board.

What makes analysis possible is a value that composes: an object attached to each component such that the value of the sum is determined by the values of the parts. The requirement is additivity, and everything about game values — the numbers, the nimbers, the infinitesimals, the canonical forms — exists to satisfy it.

Sums come first. Values are what the theory has to invent in order to handle them.

Outcomes do not compose #

The immediate evidence that outcome classes are not enough:

$\ast + \ast = 0$. Two first-player wins summing to a second-player win.

$\ast + \ast 2 = \ast 3$. Two first-player wins summing to a first-player win.

Same input classes, different output classes. So no function of outcome classes can predict the outcome of a sum, and the failure is worth its own treatment.

The gap is exactly the gap between “who wins this” and “what is this worth”. The first question is answerable and useless; the second is harder and composes.

A sum, played out #

The definition is short and the experience of using it is not, so one sum played move by move is worth the space.

Take $G + H$ where $G$ is a Nim heap of two and $H$ is a Nim heap of three. Values $\ast 2$ and $\ast 3$, so the sum is $\ast(2 \oplus 3) = \ast 1$, a first-player win.

Left — impartial games have no sides, so read this as whoever moves first — takes one from the heap of three, leaving $\ast 2 + \ast 2 = 0$. The opponent now faces a balanced position and every move unbalances it.

Suppose the opponent takes both counters from one heap, leaving $\ast 2$. The reply takes both from the other, leaving $0$, and the opponent has no move.

Suppose instead the opponent takes one, leaving $\ast 1 + \ast 2$. The reply takes one from the two, leaving $\ast 1 + \ast 1 = 0$.

Every line ends the same way, and the reason is that after the first move the position is a sum of a game and its own negative — which for impartial games is a sum of two identical heaps — and the mirroring strategy takes over.

What the sum contributed here is that the two heaps never interacted. A move in one left the other exactly as it was, so the analysis of each heap could be done once, in isolation, and combined afterwards. That is the whole economy of the thing.

The size of what is avoided #

The saving is worth quantifying, because it is the reason anybody bothers.

A Domineering board with four disconnected empty regions, each admitting ten positions, has ten thousand joint positions. Analysed as a monolith, the recursion visits all of them, and each visit branches over every move in every region.

Analysed as a sum, each region is evaluated once — forty positions in total — and the four values are added. Four evaluations and three additions replace ten thousand.

The saving is multiplicative in the number of components, which means it is the difference between possible and impossible rather than between slow and fast. A late Go board has twenty or more independent regions, and the product of their state spaces is a number with no physical meaning. The sum of their values is a short calculation.

This is what it means to say the theory is about sums. It is not that sums are an interesting special case; it is that without the decomposition there is no analysis of anything larger than a toy.

Adding a component can change everything #

One caution, since additivity can be over-read as saying components are independent in every sense.

The components do not interact during play — a move in one leaves the others untouched. They interact completely in outcome: adding a component to a position can change who wins it, and that is the entire point.

A position worth $\uparrow$ is a Left win. Add a component worth $\downarrow$ and the total is zero, a second-player win. Add $\downarrow\downarrow$ instead and Right wins. Nothing about the first component changed; the answer to “who wins” changed completely.

So a value is a statement about a component’s contribution, never about its fate. Asking “who wins this component” is asking the wrong question of a part — the right question is what it is worth, and the outcome belongs to the whole.

That distinction is exactly what the failure of outcome classes is about, and it is the most common early misreading of the subject.

The group structure #

Once sums are the operation, the natural question is what algebraic structure the values form, and the answer is clean.

Associativity and commutativity are immediate from the definition — the components are a bag, and the order of writing them down is nothing.

Zero is the identity. $G + 0 = G$ for every $G$, where $0$ is the empty position. Adding a component with no moves changes nothing, which is exactly what an identity does.

Negation exists. $-G$ is $G$ with the players swapped, defined recursively as $-G = \{-G^R \mid -G^L\}$, and $G + (-G) = 0$ for every $G$.

That last identity is the load-bearing one, and its proof is the mirroring argument that runs through everything here. The second player in $G - G$ copies each of the first player’s moves into the other component. The position after each of the copier’s moves is of the form $X - X$, which always has a reply available, so the copier never runs out and the first player does.

So games under disjunctive sum form an abelian group. The values are the group elements, and equality of games is equality in that group.

The partial order that comes with it #

The group structure carries an order, defined in terms of the sum:

$$G \ge H \iff G - H \ge 0 \iff \text{Left wins } G - H \text{ moving second}$$

That definition is compatible with addition — if $G \ge H$ then $G + K \ge H + K$ for every $K$ — which is what makes it useful. Comparing components is meaningful precisely because the comparison survives being embedded in a larger position.

It is only a partial order, and that is not a defect. Some pairs are confused, meaning neither player wins their difference moving second, and confusion is a real relation with real consequences rather than a failure to decide.

The mirroring strategy in general #

The copying argument used above is the most reusable technique in the subject and deserves stating on its own.

If a position contains two components that are negatives of each other, the second player can neutralise both. Whatever the opponent does in one, copy it in the other. This never fails, because the components are mirror images and every move in one has an exact counterpart in the other.

That single idea proves $G - G = 0$, proves the two-heap Nim strategy, proves that a symmetric position is a second-player win, and underlies the strategy-stealing arguments used to show a first-player win exists in games like Hex without exhibiting one.

Its limitation is that it proves a position is worth zero without saying anything about a position that is not. Mirroring is a complete answer for symmetric positions and no answer at all otherwise, which is why the rest of the machinery is needed.

What the solver computed #

add(g, h) in lib/cgt.js implements the definition literally — Left’s options of the sum are the sums of each component’s Left options with the other component intact — and returns an interned game.

The additivity claims in the figures are computed rather than quoted. For the Hackenbush strings drawn above, each part’s value is computed twice: by the game recursion through canonical, and by reading the string as a binary numeral. The build asserts the two agree, for all 126 strings up to length six, before it will render anything. Then the sum’s value is computed by the recursion and compared against the sum of the parts’ values, computed independently in the arithmetic of dyadic rationals.

Where a component’s value is a nimber, the comparison is against the exclusive-or. Where it is infinitesimal, the comparison is by canonical form. In every case the check is: two independent routes to the same value, asserted equal at build time.

The interning matters here more than anywhere. Sums duplicate subpositions enormously — $G + H$ contains $G^L + H$ and $G + H^L$, which share structure — and without interning the recursion recomputes the same games exponentially often. With it, $\ast 3 + \ast 5$ evaluates instantly; without it, the first implementation did not finish.

The conventions this sum is not #

The disjunctive sum is one of several ways to combine games, and the others are genuinely different.

Conjunctive sum: a move must be made in every component simultaneously, and play ends when any component runs out. This has its own theory, involving a quantity called the remoteness, and it is not the sum on this site.

Selective sum: a move is made in any non-empty subset of components. Also different, also with its own theory.

Short sum, continued sum, and others appear in the literature for particular games.

The disjunctive sum is the one that models a board breaking into independent regions, which is why it is the default and why “sum” without qualification means it. Naming the convention matters: results about one do not transfer to another, and the theory of the disjunctive sum is by far the most developed because it is the one that describes real endgames.

Where the sum lives in real games #

It is worth being concrete about the decomposition, because it is the step that connects the theory to a board.

Go. Late in the game the board is a set of independent local fights separated by settled groups. Each is a small game; the whole is their sum. This is the case the theory was extended to handle, and temperature is the tool that came out of it.

Domineering. A partly filled board breaks into disconnected empty regions. Each region is a game; the board is the sum. Small regions can be evaluated exactly, and a board that decomposes into small regions is solved.

Hackenbush. Separate drawings are separate components, and even a single connected drawing often decomposes into stalks with independent values.

Nim. Each heap is a component, and the sum is the whole reason exclusive-or appears.

In each case the theory’s contribution is the same: evaluate the parts, add the values, and never build the product state space.

Who found it, and when #

The disjunctive sum in its modern form is Conway’s, but the idea is older in a special case: Bouton’s 1901 analysis of Nim is entirely about a sum of heaps, and the nim-sum is additivity for that game before anybody had the general concept.

Sprague and Grundy in the 1930s made the additivity explicit for impartial games — the Grundy value of a sum is the nim-sum of the values — and that is the first general statement of the pattern.

Conway’s contribution around 1970 was to see that additivity is the requirement, and to build a value system rich enough to satisfy it for partizan games as well. The move from “games have outcomes” to “games have values that add” is the founding move of the subject, and everything on this site is downstream of it.

Where the model stops #

The components must be independent. If a move in one region affects another, the position is not a sum and none of this applies. Real Go positions violate this — ko fights and shared liberties couple regions — and the theory applies to endgames precisely because that is where the coupling has ended.

Normal play, throughout. Additivity of values fails under misère play, which is the single fact that makes misère theory hard.

Finite play. Loopy sums need extra machinery.

Additivity is exact, not approximate. The value of a sum is exactly the sum of the values, with no error term. That is why the theory is worth having, and it is also why the values have to be as complicated as they are — a simpler value system would not have survived the requirement.

The ladder from here #

Next: comparison, which is the order the sum induces and the operation every reduction is built from; and why outcomes do not add, worked in detail.

Beyond: the theorem that a single component in a sum decides nothing on its own; atomic weight, which is additivity for infinitesimals at an approximate scale; temperature and the thermographic sum, where the values of a sum are combined by adding walls rather than numbers; and the conjunctive and selective sums, which show by contrast how much the disjunctive convention was doing.