Equal in every company

The equals sign has been at work in almost every essay here and has never once been asked to justify itself. A two-by-two Clobber board is zero. ∗ + ∗ is zero. Two hundred and fifty-six written forms carry twenty-two values between them, which is a sentence about equality and nothing else.

In each of those the sign means something stronger than “the same player wins” and something far weaker than “the same drawing”. Here is what it means.

Two games G and H are equal when nothing can tell them apart. For every game X whatever — every board, every heap, every position anybody will ever write down — the sums G + X and H + X fall in the same outcome class.

That is a quantifier over every game there is, and there is no end of them. It is settled by one finite computation, and the whole of this essay is the distance between those two sentences.

Why knowing the winner is not enough #

The obvious definition — call two positions equal when the same player wins them — is available, costs nothing, and is wrong in the one way that matters.

It is wrong because the disjunctive sum does not respect it. Real boards come apart into independent regions, a move is a move in exactly one region, and the whole question of this subject is what the parts contribute to the total. A relation that two positions can satisfy while contributing differently to a total is not equality of anything.

Outcomes do not add establishes that in full, and the shape of the demonstration is worth carrying here in one line. Take ∗ against ∗2, ∗ against ∗, and ↑∗ against ↑∗: every one of those six positions is a first-player win on its own, and their sums are ∗3, 0 and ⇑ — a first-player win, a second-player win, and a win for Left however the moves fall. Identical outcome classes going in, three different outcome classes coming out. The consequence for equality is immediate. ∗ and ∗2 are both first-player wins; add ∗ to each and the first becomes a second-player win while the second stays a first-player win.

So the definition has to quantify over company. Equality is not a property of a position at all — it is a relation between two positions, tested by putting both in the same room as a third and asking whether anything changed.

The definition quantifies over every game there is #

Written out: G = H exactly when o(G + X) = o(H + X) for every game X.

Three things about that statement are worth pausing on, because each of them is a place the definition could have been weaker and is not.

X ranges over everything, not over positions of the same game. The context may be a Nim heap when G and H are Domineering boards, a Hackenbush stalk, or a position nobody has a name for. That is what makes a value portable between games at all, and it is why a pawn ending may be added to a Nim heap without anybody having to justify the addition.

Only the outcome class is compared, not the play. Two equal games may take wildly different numbers of moves to finish. Equality is a claim about who wins every sum, never about how long anything takes.

Taking X = 0 recovers the naive definition. Equal games do have the same outcome class, because 0 is one of the contexts the quantifier ranges over. The naive definition is the special case, and the whole content of the real one is the rest of the range.

One finite test in place of the quantifier #

The quantifier is discharged by a single well-chosen context, and choosing it is the whole trick.

Every position has a negative: the game with both players’ options swapped, all the way down the tree. The negation is exact rather than approximate — under normal play G + (−G) is worth zero for every G, because whichever copy one player moves in, the other answers with the mirror move in the other copy, and the answerer therefore always has a reply.

Now take the quantifier at its word and choose X = −H. Equality demands that G + (−H) and H + (−H) have the same outcome class, and the second of those is zero, a second-player win. So if G and H are equal, G − H is a second-player win.

The converse is the easy direction. If G − H is worth zero then G + X is H + X + (G − H) for any X at all — which is H + X plus a game worth nothing, so the two have the same outcome class and the quantifier is satisfied without being run.

G = H if and only if G − H is a second-player win. An infinite quantifier collapses onto one game and one search, because among all the contexts there is one that already knows the answer, and it is built from H rather than searched for.

That is also the definition of comparison in its general form. G ≥ H when Left wins G − H moving second; G = H when both players win it moving second; and when neither does, the two are confused, which is a fourth relation and not a failure of the method.

What the two tests cost #

Both tests are computations, so it is fair to ask what each costs.

Five positions decide whether ∗ equals ∗2. The context test, over the universe this essay uses, evaluates 368 sums for the same pair — 184 contexts times two sides — and each of those sums is itself a game that has to be solved. Twelve positions decide {2 | 0} against {1 | 0}, against the same 368.

The gap is not an implementation detail. Comparison is a search, and the difference test turns a search over all games into a search over the finitely many positions inside G − H. That reduction is what makes canonical form computable, since every deletion of a dominated option and every bypass of a reversible one is a comparison, and a canonical form is thousands of them stacked up.

What the search computed, and how #

The context test was run anyway, on a universe built rather than chosen, because a definition that has never been exercised is a definition nobody has checked.

The universe. Every game whose options are drawn from the four born on day one gives 256 written forms, carrying 22 distinct values. Those 22, together with every sum of two of them, give 184 contexts. That is the range the quantifier was allowed — a sample of the real one, and the whole argument later turns on its being a sample.

The day-two census. Of the 22 day-two values there are 66 pairs that agree on outcome class, which is the only interesting case: a pair disagreeing at X = 0 is disposed of by the naive test. The universe separates 66 of 66 and fails on none. More than that, the simplest context that does the separating is never born after day one — 1 settles 31 of the pairs, −1 settles 23, ∗ settles the remaining 12, and 0 settles none of them, which it cannot, since agreeing on outcome is what put them on the list.

The whole universe against itself. The 184 contexts give 16,836 unordered pairs, of which 5,790 agree on outcome class. The universe separates 5,790 of 5,790. The simplest witness has a birthday of day one for 4,463 of them, day two for 1,212 and day three for 115 — never later than day three, over five and a half thousand pairs. Only 34 distinct games ever serve as the simplest witness for anything, and three of them do most of the work: 1 for 1,921 pairs, −1 for 1,857, ∗ for 685, which is 4,463 of 5,790, or 77%.

That is a much stronger result than an exhaustive search finding a witness somewhere: the quantifier ranges over every game there is, and in practice a handful of the smallest games settle almost all of it.

Where the exhaustion runs out #

Here is where the computation refused to say what it was expected to say, and it is the most important paragraph on this page.

Take the two games {0 | {0 | −2}} and {0 | {0 | −4}} — tiny-two and tiny-four, from the family tiny and miny is about. Both are wins for Left. Both are positive and smaller than every positive number. They are not equal: the first is strictly the greater, established the only way anything is established here, by solving their difference.

And not one of the 184 contexts tells them apart.

The reason is exactly the mechanism of the previous section. The context guaranteed to work is the negative of one of the two sides, and the negative of tiny-two is miny-two, { {2 | 0} | 0}, which is born on day four. The universe is built from day-two values and their pairwise sums; a day-four game is not in it and cannot be. Put miny-two in and the columns separate at once — tiny-two + miny-two is zero, a second-player win, while tiny-four + miny-two is a win for Right.

The birthdays make the trap visible. Tiny-two is born on day four and tiny-four on day six, while every context in the universe is a day-two value or a sum of two of them — so both sides of this pair are born later than anything the universe holds.

A bounded exhaustive search cannot prove equality; it can only fail to refute it. That asymmetry is not a weakness of this particular sample. Every disagreeing column is a proof of inequality, complete on its own, and no quantity of agreeing columns proves anything, because the quantifier was over all games and a search is over some of them. It is what makes G − H = 0 a theorem rather than a convenient shortcut, and it is why the machinery here cross-checks in the only direction that can be checked soundly: it throws if a separator ever turns up for a pair whose difference is zero.

Equal means interchangeable #

The payoff of defining equality this way is a licence, and the licence is the reason the rest of the site works.

Equality is a congruence for the disjunctive sum. If G = H then G + K = H + K for every K, which follows from the definition in one line: the contexts that would have to separate G + K from H + K are the games X, and each of them separates them only if K + X separates G from H, which nothing does. So an equal may be substituted for an equal anywhere inside a sum, at any depth, without recomputing anything.

Zero is where that licence is most visible, because zero has so many drawings. Written $\{\ \mid\ \}$ it has no moves at all; written $\{\ast \mid \ast\}$ it has six options in its tree, $\{-1 \mid 1\}$ four, $\{\downarrow \mid \uparrow\}$ ten and $\{\ast 2 \mid \ast 2\}$ eighteen. One of those is a game with no play in it and one is a game with eighteen moves available somewhere inside it, and the claim is that a sum cannot tell which of them it has been handed.

That is what makes a value an object rather than a label. A position’s value is its equivalence class under this relation, the classes add, and a canonical form is a choice of representative in each class — the smallest one, obtained by deleting options no player would take and bypassing options that backfire.

The arithmetic that licence permits is the ordinary kind. A board made of four components — $\{0 \mid 1\}$, which is a half; $\{-1 \mid 0\}$, which is minus a half; and two copies of $\ast 2$ — is worth $\tfrac12 - \tfrac12 + \ast 2 + \ast 2$, which is $0$, and is a second-player win. Neither of the first two components is written as the number it is worth, and nothing in the addition cares: each was replaced by its value before the sum was taken, and that replacement is the theorem of this section rather than a convenience of notation.

The licence is worth naming because it is not automatic, and this site has an operation that lacks it. Under the ordinal sum, where a move in one part destroys the other entirely, three positions all worth zero give three different answers when a star is stacked on them. Substitution fails there, and the colon principle is stated one-sidedly for exactly that reason. Equality is a congruence for one operation, and which operation has to be said out loud.

What the picture cannot show #

The figures in this essay are tables of outcome classes, and a table is the wrong shape for the claim being made.

Six columns is not 184, and 184 is not all games. Every context-witness drawing shows a handful of columns chosen to make a point. The counts underneath are the honest part — 26 of the 184 contexts separate ∗ from ∗2, 30 separate ↑ from 1/2, 36 separate {2 | 0} from {1 | 0} — and the drawn columns are a display, not the evidence.

The negative claim has no picture at all. “No context separates these” is a statement about an absence, and an absence cannot be drawn; it can only be reported as a count that came out zero. The figure where the exhaustion runs out is a row of agreeing cells, which looks precisely like the figure where the test passes, and on the page the two are indistinguishable. What can be drawn is the repair — one extra column, from outside the universe, that splits the row — and even that is a picture of the witness rather than of the absence. The distinction that matters is still a sentence: one of those two pairs has a difference of zero and the other does not.

And the mirroring strategy is not in the negation drawing. That figure shows three positions, three negatives and three sums worth zero. What makes those sums zero is a strategy — answer in the other copy — which is a rule about play over time, and a drawing is a snapshot. The outcome class printed beside each row is the computed consequence of the strategy, not the strategy.

Who settled it, and the convention it rests on #

The definition is Conway’s, from the late 1960s, published in On Numbers and Games in 1976 and given its playing manual in Winning Ways in 1982. What was new was not the observation that some positions behave alike — that is old and informal — but the decision to make behaviour-in-every-sum the definition of sameness, and then to prove it decidable.

Before that the subject had Sprague and Grundy’s theorem for impartial games, which is an equality result in disguise: two impartial positions with the same Grundy value are indistinguishable in every impartial sum. The partizan generalisation needed negation, and negation needed the games to form a group under the disjunctive sum.

The convention this all rests on is normal play: the player unable to move loses. Every claim above fails without it, and fails at the first step. Under misère play G + (−G) is a win for the mover, not the answerer — the mirroring strategy still supplies a reply to every move, and supplying replies is now the losing behaviour. So there is no zero, the difference test has nothing to test against, and equality has to be rebuilt from the indistinguishability definition alone with no shortcut behind it.

The second convention is that the games here are short: finitely many positions, no repetition, every play ending. The whole recursion rests on that, and so does the claim that G − H can be solved at all.

Where the ladder goes next #

This is the base rung of the equality anchor, and it opens onto four that are genuinely further up rather than sideways.

The substitution theorem, stated and proved properly. The congruence argument above is a sketch; the full statement is that equality is preserved by the disjunctive sum, by negation, and by forming options — so a game built from equal parts is equal, and induction over the position tree is legitimate. That last clause is what every recursive computation on this site quietly assumes.

Equality as an equivalence, and the quotient it defines. The relation is reflexive, symmetric and transitive, the classes are the values, and the values under the disjunctive sum form an abelian group with the partial order this essay’s difference test induces. Naming that object — a partially ordered abelian group — is what allows theorems to be proved about all games at once rather than about positions, and the atomic weight calculus is one of them.

Indistinguishability under misère play. The definition survives the departure from normal play and the theorem does not. Fix a single game, look only at sums of its own positions, and the relation is a congruence again on that restricted collection — which is precisely the misère quotient construction, and precisely the sampled-universe idea in this essay taken seriously rather than used as an approximation. There the bounded universe is the answer, because there is no unbounded theorem to fall back on.

Equality restricted to a universe, in general. Two games can be indistinguishable across every sum drawn from one family and separable by something outside it — which is exactly what tiny-two and tiny-four do to the 184 contexts here. A universe-relative equality is a coarser relation than the real one, it is computable where the real one is not, and knowing which universe a claim was checked in is the difference between a measurement and a theorem.