Three ways to add the same games

Two heaps, one counter each. Under the ordinary rules of this subject the position is a second-player win: whatever one player takes, the other takes the matching counter, and the first player runs out.

Now change one word of the rules. A move is a move in every component at once, and the game ends the moment any component runs out. The same two heaps are now a first-player win.

Nothing about the heaps has changed. What changed is the meaning of “and”.

A compound of several games is a rule saying what a move in the whole is, given the components. The disjunctive sum is one such rule and there are others; three are standard.

Disjunctive. A move is a move in exactly one component. Play ends when no component has a move for the player to move. This is the sum written $G + H$ everywhere on this site.

Conjunctive. A move is a move in every component simultaneously. Play ends as soon as any one of them has no move — so the compound lasts exactly as long as its shortest part.

Selective. A move is a move in any non-empty subset of the components. Play ends when none of them has a move.

All three are perfectly ordinary combinatorial games. All three are finite when their parts are. All three have well-defined outcome classes, computed the same way as any other position’s: ask who wins with each player to move.

Where the answers part company #

Two identical stars are the clearest case, and they are the first row of the figure.

Disjunctive: $\ast + \ast = 0$, a second-player win. The mirroring strategy applies — the fact that makes negation work — and copying the opponent’s move in the other component never runs out.

Conjunctive: a first-player win. The mover must move in both components at once, so the game lasts one move: the first player moves in both, both are exhausted, and the opponent has nothing to move in. Copying is impossible, because there is no separate turn in which to copy.

Selective: also a first-player win, for a different reason. The first player moves in both components in a single turn, which is legal here and leaves nothing behind.

The nim-sum of the two heaps is zero, which under the disjunctive rule is the whole story: the player to move loses. That nim-sum is a fact about disjunctive addition specifically and it says nothing whatever about the other two compounds — a good reminder that a value is a value with respect to an operation, and that quoting one outside the operation it was computed for is quoting nothing.

The second row of the figure is stranger. Components worth $2$ and $-1$: the disjunctive sum is worth $1$, so Left is a whole move ahead and wins whoever starts. Under the conjunctive rule the same two components are a second-player win — the advantage is worth nothing at all, because the game is over as soon as the shorter component is.

Only one of them has values #

Here is the property that singles the disjunctive sum out, and it is not that it is more natural or easier to state.

The value of a disjunctive sum is the sum of the values of its parts. That single sentence is what makes a theory possible: a component can be analysed once, reduced to a value, and combined with others by arithmetic. Every technique on this site depends on it — decomposing a Domineering board into regions, reading an endgame as a sum of switches, comparing two positions by subtracting them.

Neither of the other two compounds has anything like it. There is no function of the components’ values that gives the conjunctive outcome, and one table settles it: take four lists whose disjunctive values are all identical — all nought — and watch the conjunctive column disagree with itself. If the conjunctive answer were a function of the value it would have to be the same on every row, and it is not.

The rows that separate are separated by length — how many moves a component can be made to last, and by whom — and length is exactly what a value throws away. Two positions worth the same are interchangeable in every disjunctive sum and need not last the same number of moves, so the conjunctive compound can distinguish a pair the value theory certifies as identical.

That is the real content of the choice. The disjunctive sum is not the only way to add games; it is the way that admits a value.

Where the choice comes from in the first place #

It is worth asking why anybody would define a sum of games at all, because the answer explains which sum gets chosen.

The operation is not invented to be studied. It is invented because real positions come apart. A Domineering board late in the play is several regions no domino can bridge; a Go endgame is a dozen local fights; an Amazons position after the arrows have cut the board is a set of sealed rooms. In every one of those cases a move happens in exactly one part, because the parts are physically separate on the board.

So the disjunctive rule is not a design choice among equals. It is a description of what decomposition produces, and the other two compounds describe something else — several games being played at once by agreement, rather than one game that has fallen into pieces.

That also explains why the other compounds feel artificial when applied to a board: making a move in every region at once is not something the rules of Domineering permit, and a compound that describes no position anybody can set up is a compound with no examples.

Why the mirroring argument only works for one of them #

The technical reason is worth isolating, because it explains all three columns at once.

Almost every theorem in this subject is proved by a strategy of the form “answer the opponent’s move with a specific reply”. The mirroring strategy for $G + (-G)$; the copying strategy for two equal heaps; the argument that a number is never worth moving in.

Each of these requires that the opponent’s move leaves the answer available. Under the disjunctive rule it does: a move in one component leaves every other component untouched, so a prepared reply in a different component is still legal.

Under the conjunctive rule it does not. A move touches everything, so the position a reply was prepared for no longer exists. Under the selective rule it does not either: the opponent may move in exactly the components the reply was meant for.

So the independence of the components is not a convenience of the disjunctive sum. It is the hypothesis of nearly every proof in the subject, and the other compounds are not counterexamples to those proofs so much as different subjects.

The move that is not in any component #

There is a second, subtler difference, and it shows up in the selective column of the figure’s fourth row.

Under the selective rule a player may move in several components at once — and that is a move the disjunctive game simply does not contain. So the selective compound of $\uparrow$ and $\ast$ has options the disjunctive one lacks, which is why it comes out a win for Left where the disjunctive version is a first-player win. Left, moving first, can settle both components in a single turn.

That kind of move breaks something specific: it means the winning move cannot be located in a component even in principle, because the move is not in a component at all. Under the disjunctive rule the question “where should the next move be?” always has an answer of the form “in this part” — the hard part is finding which, and no rule reads it off the values. Under the selective rule the question does not even have that shape.

The last two rows are the ones to hold on to. The extra move is available to both players, so it is not a gift to whoever is ahead: it can take a position Left wins outright and hand it to whoever moves, and it can take a position either player might have won and hand it to Right. There is no direction the change reliably runs in, which is another way of saying that no summary of the components predicts it.

What the conjunctive compound is good for #

None of this makes the other compounds useless, and it is worth saying what they are for rather than leaving them as foils.

The conjunctive compound models a situation the disjunctive one cannot: several processes running in parallel where the whole thing stops when the first one finishes. That is the shape of a great many real contests — a race, a set of resources exhausted at different rates — and it is why the compound has a theory of its own, built on the remoteness of a position rather than on its value. Remoteness counts how long a component can be made to last, which is exactly the quantity the value throws away.

The selective compound sits between the two, and has its own analogue in the sprightliness of a position.

What the solver computed, and how #

Each outcome in the figures is computed by direct search from that compound’s own definition, and the three searches share nothing but their memo key format.

The disjunctive search tries each component in turn and each option within it. The conjunctive search walks the Cartesian product of the components’ option lists, since a move must pick one option from each; it declares the mover lost immediately if any component has none. The selective search walks every subset, leaving unchosen components alone, and rejects the empty move.

All three memoise on the components’ interning keys together with the side to move. Termination is by the same argument in every case: each move strictly reduces at least one component’s birthday, and birthdays are well founded.

The disjunctive column is then computed a second time, from the values — build the sum with sum(), take its outcome — and the two must agree. That check exists because the disjunctive column is the only one where a value theory makes a prediction at all, and a disagreement would mean either the search or the arithmetic is wrong. The other two columns have nothing to be checked against, which is the essay’s point stated as an engineering fact.

The gate requires at least three of the five standard component lists to give different answers under the three rules. Without that, a bug that computed the disjunctive outcome three times would pass silently, and the figure would show three identical columns and a caption claiming they differ.

The other compound does compose — under a different operation #

There is a way in which “only one of them has values” undersells the other two, and correcting it says something about what a value is.

The conjunctive compound has a composable invariant. It is not the value, and the essay’s argument that no function of the values gives the conjunctive outcome stands — but remoteness composes by minimum, and that is a genuine additivity theorem of exactly the same shape as the one this whole site is built on.

The reason is visible in the rule. A conjunctive compound ends the instant any component runs out, so what governs it is how long the shortest part can be made to last. Length is what remoteness measures; the shortest of several lengths is their minimum; and the compound’s remoteness is therefore the minimum of its parts’. One quantity per component, one operation, one answer — the same bargain the disjunctive sum offers.

So the difference is not that one compound composes and the others do not. It is which operation they compose under, and that turns out to decide everything else.

Why an operation with no inverse gives no theory #

Addition has inverses. Minimum does not, and almost every technique on this site is a consequence of the first fact.

Negation. $-G$ exists because addition has inverses, and it is what makes comparison a subtraction. Under minimum there is no $-G$: there is no length that, combined with another by taking the smaller, gives back a neutral one. So there is nothing to subtract, and the comparison test that decides every relation in this subject has no analogue.

Cancellation. $G + X = H + X$ implies $G = H$, which is what licenses removing a common component from both sides of an argument. Minimum cancels nothing: $\min(3, 1) = \min(7, 1)$, and no conclusion about 3 and 7 follows. A common component under the conjunctive rule can swallow a difference of any size.

And idempotence, which is the tell. $\min(a, a) = a$, so a conjunctive compound of a game with itself is that game again. Under the disjunctive rule $G + G$ is a genuinely different position from $G$ — and $G + G = 0$ for the self-negative values, which is a fact with real content. An operation where doubling changes nothing is an operation with no arithmetic in it.

Put together: minimum makes the invariants a semilattice where addition makes them a group, and every piece of machinery on this site — the canonical form, the partial order, the difference game, the whole notion of one position being substitutable for another — is machinery for a group.

Which is what singles the disjunctive sum out #

That is a better answer to the essay’s own question than “it is the one with values”, because it says what having values consists of.

The disjunctive sum is distinguished not by being natural, or by describing what a decomposed board does — though it is and it does — but by being the compound whose composable invariant lives in a group. Everything the theory can do is a theorem about groups with an order on them, and the other compounds have composable invariants in structures too poor to carry those theorems.

And it explains why the conjunctive theory looks so unlike this one. Remoteness is a number, quoted and compared, with no reduction, no canonical form and no substitution rule — not because the subject is less developed there, but because a semilattice has nothing for those to be about. What a theory looks like is decided by the algebra of its composition, and the three compounds have three algebras.

Where the model stops #

Short games only. All three compounds are defined for loopy games too, and the conjunctive one behaves particularly badly there — a single component that never ends makes the whole thing never end, which is the opposite of the finite case where the shortest component governs.

No remoteness theory here. The essay names remoteness as the quantity governing the conjunctive compound and does not compute it. That is a genuine gap and a candidate rung rather than an omission: the theory exists, it is in Winning Ways, and it deserves its own figure rather than a sentence.

The claim that no function of the values gives the conjunctive outcome is argued, not proved. The essay exhibits components with equal disjunctive values and different conjunctive answers, which settles it — but the exhibition is over a handful of small positions, and a reader entitled to the general statement should have it from the remoteness theory rather than from five rows of a table.

The searches are exponential and the components are small. Every component drawn has a birthday of at most three. The conjunctive search in particular walks a product of option lists, so it grows fast in the number of components, and five components of any size would be out of reach.

Who found it, and when #

The three compounds and their theories are in Winning Ways (1982), where the disjunctive one occupies most of the book and the other two are given a chapter apiece — conjunctive compounds with remoteness, selective compounds with sprightliness. Conway’s On Numbers and Games (1976) is about the disjunctive sum almost exclusively, and says so.

The choice was made early and deliberately. The disjunctive rule is the one under which a position decomposes into independent parts, and decomposition is what makes real games tractable — a Go endgame, a Domineering board late in the play, an Amazons position after the arrows have cut it. The other rules describe games nobody plays but processes that certainly happen, and the theory follows the games.

Worth noting that the vocabulary predates the analysis. “Conjunctive” and “disjunctive” are borrowed from logic — and against or — and the borrowing is exact: a player in the disjunctive compound must have a move in this component or that one, and in the conjunctive compound in this one and that one. Once the connective is named, the difference between the theories stops being a technicality about move rules and becomes a difference between two quantifiers, which is the kind of relabelling that makes a thing easier to remember and no easier to prove.

Where the ladder goes next #

This is the third rung on the disjunctive-sum ladder, after the sum itself and the question of which part to move in. The first two take the operation as given; this one asks why that operation and not another.

The next rung is the one this essay keeps deferring: remoteness, the quantity that plays for conjunctive compounds the role a value plays for disjunctive ones. It is a number, it is computed by a recursion, and it is not the value — which makes it the clearest available demonstration that “what a position is worth” is a question with more than one answer depending on what the position is going to be added to.