Turn the board through a right angle

Two Domineering boards on a table. The first is two squares tall and four wide; the second is the same board turned through a right angle, four tall and two wide. A move is a move on either board, and a player who cannot place a domino on either loses.

Whoever moves first, loses. Not usually — always, and it does not matter how the play is shared between the two boards.

Turning the board is not a metaphor. Left places dominoes vertically and Right horizontally, so rotating the board through a right angle exchanges what the two players can do — Left’s moves on the rotated board are exactly Right’s moves on the original. That is what negation is.

The definition, which is one line #

$$-G \;=\; \{\, -G^R \;\bigm|\; -G^L \,\}.$$

Swap the two option lists, and negate every option in them, all the way down. Nothing is negated in the arithmetic sense; the minus sign is applied to a game, and what it does is exchange the players.

The obvious worry about a definition that never mentions arithmetic is that it will disagree with arithmetic somewhere, and the place to look is the numbers, where the answer is fixed in advance and the game definition has no licence to differ from it. A whole number $n$ is the position in which Left has $n$ moves in hand and Right has none, so $2$ written out is $\{1 \mid\ \}$ — Left to $1$, Right with nothing at all. Exchange the players and that becomes $\{\ \mid -1\}$, which is exactly what being two moves behind looks like. The two minus signs turn out to be one operation, which is the whole reason the notation can be shared without confusing anybody.

Why the sum is always zero #

The claim is that $G + (-G) = 0$ for every game $G$: the second player wins, whoever that is, and however the first player plays.

The strategy is one sentence, and it is the same one that runs through the disjunctive sum: answer every move with its mirror image.

Suppose Left moves in the $G$ component, to $G^L$. The position is now $G^L + (-G)$, and $-G$ still has a Right option $-G^L$ — because the Right options of $-G$ are exactly the negatives of the Left options of $G$. So Right plays it, and the position becomes $G^L + (-G^L)$: the same shape as before, one level down.

The same works if Left moves in the second component, and the same works for Right. Every move has an answer, so the second player is never stuck. And play must end, so the first player runs out first, which is exactly what losing means under the normal-play convention.

The argument uses nothing about $G$ — not its size, not its value, not whether it is a number. It is the shortest theorem in the subject and the one carrying the most weight.

What it buys #

A group needs an identity, an associative operation and an inverse for every element. Games under the disjunctive sum have the first two easily: the empty position is the identity, and adding is associative because “a move in one component” does not care how the components are bracketed.

The inverse is this theorem, and with it the values become a group. From which:

Comparison becomes subtraction. $G \geq H$ is defined as “Left wins $G - H$ moving second”, and that definition would be circular or useless without a $-H$ to subtract. The whole partial order rests on negation existing.

Cancellation is available. From $G + X = H + X$ it follows that $G = H$, by adding $-X$ to both sides. That is why a shared component can be ignored when two positions are compared, which is what makes analysing a board by parts practical rather than merely possible.

Equality means interchangeable. Two positions are equal when their difference is zero, and the difference is a position somebody can play.

That last one is worth dwelling on, because it turns a definition nobody could check into one anybody can. The natural definition of “these two positions are worth the same” quantifies over every game in existence: swap one for the other anywhere, in any larger position, and nothing changes. There is no way to test that directly. Negation collapses it to a single question about a single position — build $G - H$, play it, and see who wins moving second — and the answer to that one question certifies the statement about all the others. A theory in which the identity element existed but inverses did not would have equality as an ideal rather than as a computation.

There is a fourth consequence, less often stated and heavily used on this site. Everything cancels with itself, so a component that appears on both sides of a comparison is free. Comparing a whole Domineering board against another differing in one region means comparing the two regions, because everything else subtracts away. That is why a decomposition is worth making at all, and it is negation that licenses it.

The one thing the mirror does not give #

It is worth being exact about what the theorem does and does not say, because the strategy it describes is very easy to over-read.

Mirroring wins $G + (-G)$. It does not say anything about how to play $G$ itself, and it does not say the two components are somehow equally good — the mirrorer is not playing well in either half, and could be losing badly in both considered alone. What the strategy guarantees is only that a reply always exists, which under normal play is all that winning requires.

That is a general habit of this subject and worth noticing early: a value tells a player who wins and not what to play. Here the strategy is handed over with the theorem, which is unusual and makes negation an easy case; almost everywhere else the value comes without one.

There is a second thing the theorem does not give, and it is the one that trips people. $G + (-G) = 0$ does not mean the position is empty. A two-by-four board beside its own rotation has room for four dominoes and a dozen lines of play; it is a real fight in which the second player happens to be able to answer everything. Being worth zero is a statement about the outcome, not about how much game is left.

Star is its own negative, and so is every nimber #

Negation exchanges the option lists, so a position whose two lists are the same is unchanged by it. $\ast = \{0 \mid 0\}$ is the smallest example, and every nimber has the same property.

That gives $\ast + \ast = 0$, which is worth restating in ordinary language: two identical impartial positions cancel. Somebody playing a sum of two identical heaps answers each move by copying it in the other heap, and the copying strategy is the mirroring strategy with the mirror doing nothing.

The property belongs to the position rather than to the notation, which is worth saying because the nimbers are usually met as symbols. Any position in which both players have the same moves is unchanged by the exchange: a green Hackenbush sprig, whose edges either player may cut, is its own negative for the same reason a heap is, and reversing the colours of a picture that has no colours to reverse leaves the picture alone.

Two things are worth getting right here, because both are easy to state slightly wrong.

The two conditions are the same condition. $G = -G$ and $G + G = 0$ say the same thing, immediately: add $G$ to both sides of the first, and $G + (-G)$ is zero by the theorem above. There is no near-miss between them and no reason to prefer one form.

And neither characterises the impartial games. The switch $\pm 1$ is its own negative — negating $\{1 \mid -1\}$ swaps the options and negates them, giving $\{1 \mid -1\}$ back — so $\pm 1 + \pm 1 = 0$, and $\pm 1$ is as partizan as a position gets. The self-negative values are a much larger family than the nimbers, thirty of them born by day three against four nimbers, and they include hot positions.

So being one’s own negative is a property impartial games have and do not own. It is not the reason the impartial theory collapses to a single number — that reason is hereditary, an induction using impartiality at every position of the tree, with the mex doing the work at each step.

The inverse is the axiom that is not free #

Three things are needed for a group, and it is worth noticing how differently the three arrive, because the essay lists them in a sentence and they are not comparable in difficulty.

The identity is a definition. The empty position is the identity because adding a component with no moves in it changes no move list. There is nothing to prove.

Associativity is a re-bracketing. “A move in exactly one component” does not care how the components are grouped, so $(G + H) + K$ and $G + (H + K)$ have the same options and are the same game — not merely equal, identical.

The inverse is a theorem with a strategy in it. Somebody had to exhibit $-G$, and somebody had to show that the mirroring reply always exists and that play ends. Nothing about the definition of the sum hands it over.

So of the three axioms, two are bookkeeping and one is the content. That is unusual — in most algebra the inverse is the cheap axiom and associativity is where the work is — and it is worth knowing which way round this subject sits, because it says which axiom fails when the setting changes.

And it is the one that fails #

Sure enough, the convention change in the next section leaves the first two untouched and takes the third.

Under misère play the empty position is still an identity for the sum, and the sum is still associative — nothing about “a move in exactly one component” has changed. What goes is $G + (-G) = 0$, and with it goes the group.

And everything this section listed as bought goes with it, in order. No inverse, no subtraction; no subtraction, no comparison by difference; no comparison, no order; no order, no domination test, no canonical form and no substitution. That chain is the whole of why misère play has a theory of quotients rather than a theory of values, and it comes off one axiom.

It is worth pressing how narrow the failure is. Misère play changes one clause about who wins, leaves every position, every move and every option list exactly as it was, and leaves two of the three group axioms standing. The theory it destroys is destroyed through a single missing element — and the mirroring strategy that proves the theorem here is the exact step that stops working, because under misère the second player’s inexhaustible supply of replies is what loses rather than what wins.

That is the sharpest available answer to why negation gets a whole essay. It is not that the theorem is hard, or that the definition is subtle. It is that this one line is the load-bearing one, and everything the subject can do sits on top of it.

Where it fails, and what goes with it #

The theorem needs the normal-play convention, and it is the first thing to break when the convention changes.

Under misère play the player who cannot move wins. Everything about the positions is unchanged — the same heaps, the same moves — and $G + (-G)$ is no longer a second-player win.

The mirroring strategy still describes a legal way to play. What it no longer does is win, because it guarantees the mirrorer makes the last move — and under misère that is the losing move rather than the winning one. The strategy has not become illegal or unavailable; it has become a way of losing on purpose, which is a much more unsettling kind of failure.

The smallest place to watch that happen needs no algebra at all. Two Nim heaps of one counter are a position beside its own negative, because a heap is its own negative and there is nothing for the exchange to exchange. Under normal play the copier answers the first take with the second and wins; under misère the copier is the one who takes the last counter and loses. Same position, same strategy, opposite verdict — and the equivalence that made positions substitutable for one another goes with it, and the additivity that let two components be evaluated separately and combined goes with that, so a misère board has to be analysed whole rather than region by region.

The misère theory that grows back is much smaller and is computed separately for each game, because the one general fact that made a general theory possible is gone.

What the solver computed, and how #

Negation is six lines of the site’s evaluator: build a new game whose Left options are the negatives of the old Right options and whose Right options are the negatives of the old Left options, memoised on the interning key so that $-(-G)$ returns the original object rather than an equal copy.

Every claim on this page is then an outcome computation. negation-mirror builds $G$, builds $-G$, adds them, canonicalises, and requires the name of the result to be exactly 0 — not “equal to zero”, not “worth about nothing”. If any row came out otherwise the figure would throw and the build would stop.

The Domineering pairs are checked differently, and more strongly. Rather than asserting that a rotated board is the negative of the original, the site builds both boards independently from their own move rules and compares the two computed values. A bug in negation would not produce agreement there, because negation is not used in building either one.

The gate runs the identity over the site’s standard sample of values — numbers, nimbers, switches and infinitesimals — and separately requires the misère outcome of two single-counter heaps to differ from the normal-play one. That second check is the one that would fail silently if somebody ever “simplified” the misère machinery to reuse the normal-play answer.

Where the model stops #

Short games only. Every position here has a finite game tree and play that must end. Negation is defined the same way for loopy games, but $G + (-G) = 0$ is no longer available in the same form — a game that never ends cannot be beaten by a mirroring strategy, because the mirrorer never gets to be the one who is stuck.

The theorem is about values and says nothing about difficulty. $G + (-G) = 0$ holds for every short game, including ones nobody can evaluate — the mirroring strategy needs no knowledge of $G$ whatever. So a position can be completely intractable and its difference with itself still trivially settled, which is worth remembering when a comparison turns out to be cheap and the two positions being compared are not.

Rotation is Domineering’s negation, and not every game has one. The right-angle turn works because Domineering’s two players differ exactly by a right angle. Most partizan games have no such symmetry, and their negatives are positions nobody would recognise as related to the original.

The group is of values, not of positions. $G + (-G)$ is not the empty position; it is a perfectly good board with plenty of play left in it. What is zero is its value, which is a statement about who wins rather than about what is on the table.

The group is abelian and that is worth noticing rather than assuming. $G + H$ and $H + G$ are the same game because “a move in one component” makes no reference to an ordering of the components. It is the sort of fact that looks too obvious to state until one of the other compounds is tried, where the components genuinely interact and the pleasant algebra evaporates. Commutativity, associativity and inverses are all consequences of one design choice — that a move happens in exactly one part — and none of them survives changing it.

Who found it, and when #

The definition and the mirroring argument are Conway’s, in On Numbers and Games (1976), where they arrive early because everything after them depends on them. The observation that the short games form an abelian group under the disjunctive sum is stated there as a theorem and used as an assumption for the rest of the book.

The copying strategy is much older than the theory. It is the standard trick for two equal Nim heaps, known well before Bouton wrote it down in 1901, and probably as old as anybody playing a game with two identical halves. What the twentieth century added was the observation that the trick is not about heaps at all: it works for any position beside its own mirror, which turns a piece of folklore into the axiom a whole algebra rests on.

It is also the reason the subject looks so unlike the other thing called game theory. Von Neumann and Morgenstern’s games have payoffs, and a payoff is a number a player is trying to make large; there is no operation on games that produces a third game, so there is nothing for an inverse to be. Here a position is an element of an algebraic structure, addition of positions is a legal thing to do to a board, and the negative of a position is another position somebody can set up on the table. That is a very different starting point, and this theorem is where the difference becomes visible.

Where the ladder goes next #

This is the base rung of a ladder about the algebra of positions rather than about their values. The next rung is the other direction the group structure runs in: cancellation, and the fact that a component common to two positions can be struck out of a comparison — which is what makes it legitimate to analyse a board region by region and is not obvious from the definition.

After that comes the question this essay only gestures at. The disjunctive sum is one way to add games and there are others; the mirroring strategy is what singles this one out, because it is the only compound in which answering in the mirror is a legal reply to every move.