Canonical form

Equality of games is defined by a quantifier over everything: $G = H$ when $G$ can replace $H$ inside any position without changing who wins it. Taken literally, checking it means checking infinitely many contexts.

The theory’s escape is that the definition collapses. There is a normal form, every position has exactly one, and two positions are equal precisely when their normal forms are identical trees.

The definition, and why it is unusable #

$G = H$ means $G - H$ is a second-player win, which is at least finite to check. The stronger statement — that $G$ and $H$ are interchangeable in every context — follows from it, and that implication is the theorem that makes the subject work.

But “$G - H$ is a second-player win” still requires playing out a game, and comparing a position against every candidate value means playing out one game per candidate. What is wanted is a canonical representative: reduce each position to a normal form, then compare the forms directly.

Two reductions suffice. That they suffice, and that the result is unique, is the content of the theorem.

Dominated options #

Left has two moves available, to $A$ and to $B$, and $A \ge B$. Then $B$ can be deleted.

The reason is monotonicity: under normal play, having more options cannot hurt, and an option that is worse for its owner than another option the same owner has will never be needed. Left, offered both, takes $A$; the presence of $B$ changes nothing anywhere.

Symmetrically for Right, with the inequality reversed — Right prefers smaller, so an option that is larger than another of Right’s options is dominated and goes.

$$\{0, -3 \mid 1\} = \{0 \mid 1\} = \tfrac12$$

Left would never move to $-3$ when $0$ is available. The option is not merely unhelpful, it is invisible: no sum, no context, no opponent behaviour makes it matter.

Domination is the easy reduction. It is a comparison between siblings, it needs nothing but the partial order, and it removes most of the clutter in a typical position.

Reversible options #

The second reduction is subtler and is where most first readings stall.

Left has an option $A$, and inside $A$, Right has a reply $A^R$ with $A^R \le G$. That is: Left’s move can be answered so effectively that the resulting position is no better for Left than the original was.

Then Left’s move to $A$ is reversible through $A^R$, and the reduction is not to delete it but to bypass it: replace $A$ in Left’s option list by all of Left’s options from $A^R$.

The logic is a small argument about play. If Left moves to $A$, Right answers with $A^R$, and Left has ended up somewhere no better than the start while spending a move. So the move to $A$ is only worth making if Left intends to continue from $A^R$ — and if that is the plan, the intermediate step can be skipped. Splicing Left’s options from $A^R$ directly into $G$ captures every line that mattered.

Two things about this reduction are easy to get wrong. It can increase the number of options, because $A^R$ may have several Left options spliced in. And the condition is $A^R \le G$ — a comparison with the whole original position, not with $A$ — which makes the check global rather than local.

The first of those is worth seeing rather than conceding, because “reduction” is a word that promises the opposite. $\{\,\{0 \mid \ast2\} \mid 0\,\}$ has one option a side. Left’s move is reversible — Right’s reply from inside it lands back at something no better than the start — so it is bypassed, and what is spliced in is two options where one stood.

So the reduction is a normal form rather than a small one, and nothing in the theorem promised smallness. What falls at every step is the node count — a bypass substitutes pieces that were already inside the tree — and the width is free to go either way.

Symmetrically for Right, with $A^L \ge G$.

Reversibility in a real position #

An abstract description of a detour is unpersuasive, so here is one that arrives from arithmetic rather than from an author choosing a shape.

Take $\uparrow$, which is $\{0 \mid \ast\}$, and add a star. The definition of a sum says each player moves in one summand and leaves the other alone, so the position written out has four options: Left may go to $\ast$ or to $\uparrow$, and so may Right — except that Right’s move in the star lands on $\uparrow + 0$, which is $\uparrow$ again.

That is the same value the widening example above arrives at from the other direction, and the pair is worth holding together: $\{\,\{0 \mid \ast2\} \mid 0\,\}$ grows into $\{0, \ast \mid 0\}$ and $\{\ast, \uparrow \mid 0, \uparrow\}$ shrinks into it. Neither form is the value; the third one is, and it is what both routes stop at.

The same pattern is everywhere in Hackenbush. A green edge at the base of a stalk gives both players a move that removes the whole stalk, and such moves are frequently reversible — the opponent’s reply undoes whatever was gained — so a green string’s canonical form is far smaller than the raw position the picture suggests.

The algorithm #

Put together, the procedure is:

1. Reduce every option to canonical form, recursively.
2. Delete dominated options on both sides.
3. Bypass reversible options on both sides.
4. If anything changed, go to step 2.

The loop is needed because the two reductions feed each other: bypassing a reversible option can introduce a new option that is dominated, and deleting a dominated option can make a previously non-reversible option reversible by changing the comparison.

The loop terminates, because each pass either strictly reduces the tree or leaves it unchanged, and the recursion bottoms out at the empty position.

What comes out is the canonical form, and the theorem is that it is unique: two positions are equal if and only if their canonical forms are the same tree, node for node. So equality becomes tree comparison, and the quantifier over all contexts has vanished.

A reduction, worked #

One position taken all the way down makes the loop concrete.

Start with $G = \{2, 0 \mid 5, \{3 \mid 1\}\}$.

Reduce the options first. The number options are already canonical. The compound option $\{3 \mid 1\}$ has both options numbers, but Left’s exceeds Right’s, so the simplicity rule does not apply — this is a switch, and it stays as it is.

Domination, Left. Left’s options are $2$ and $0$, and $2 \ge 0$, so $0$ goes. Left’s list is $\{2\}$.

Domination, Right. Right’s options are $5$ and the switch $\{3\mid 1\}$. Right prefers smaller. The switch is confused with neither — it lies between $1$ and $3$ in the relevant sense and is certainly below $5$ — so $5$ is dominated and goes. Right’s list is the switch alone.

Now $G = \{2 \mid \{3 \mid 1\}\}$.

Reversibility, Right. Right’s option is the switch, and inside it Left has a move to $3$. Is $3 \ge G$? The whole of $G$ is bounded above by something near $2$, so yes. Right’s move is reversible through Left’s reply to $3$, and the bypass replaces Right’s option by Right’s options from $3$ — of which there are none, since $3$ is a positive integer and Right cannot move in it.

So $G = \{2 \mid \;\}$, which is $3$.

A position with four options, two levels deep, is worth exactly three free moves for Left. Neither reduction on its own gets there: domination alone leaves a switch on the right, and reversibility alone cannot fire until domination has cleared the way. That interleaving is why the algorithm loops.

Why not just compare values #

A reasonable objection: if every position has a value, why not compute values and compare those instead of trees?

Because for most positions the value is the tree. Numbers can be written as fractions, nimbers as $\ast n$, and a handful of famous infinitesimals have names — but the overwhelming majority of canonical forms have no shorter description than themselves. A position worth $\{\,\{2 \mid 1\} \mid \{1 \mid 0\}\,\}$ is worth exactly that and nothing more compact.

So “the value” of a position is, in general, its canonical form. The named values are the small corner of the space that got names, and it is a mistake to imagine that behind every canonical form there is a number waiting to be found. Most of the space is trees.

This is also why the notation problem is real. Brace expressions grow unreadable at depth three, which is why every figure here shows the position alongside the braces, and why an essay that consisted of nested braces would have stopped explaining anything.

The cost of running it #

A last practical note, since this reduction is what the site runs on every figure it draws.

Canonicalising a position requires comparing options, comparing requires evaluating differences, and evaluating a difference requires playing it out. Each layer multiplies. For a position with a handful of options two or three levels deep, the whole thing finishes instantly. For a position with twenty options five levels deep it may not finish at all.

That ceiling is low and it is worth naming: the practical range of exact canonicalisation is a few dozen moves of depth, and the figures on this site stay inside it deliberately. Nothing here evaluates a Go endgame or a large Domineering board, because nothing can — the recursion is correct at every size and finishes only at the small end, and every position drawn above is one option or two wide for that reason rather than for a pedagogical one.

What the solver computed #

The reduction implemented here is the loop above, directly: it reduces options first, then alternates the two reductions until a full pass changes nothing.

Two implementation facts are worth recording because both cost time.

Comparison is the expensive part. Both reductions need ge, which is defined by “the second player wins the difference” and is therefore itself a recursion over play. A naive implementation recomputes the same comparisons thousands of times. The fix is memoisation keyed on a pair of game identities.

Games must be interned. The first version generated a structural key for each game by recursing over its options and concatenating. For $\ast 3 + \ast 5$ that key ran to megabytes and the reduction never finished. The fix is to give every distinct game an integer identity on construction, keyed on the sorted identities of its options, so a key is short and structurally identical games are literally the same object. Reference equality then answers most comparisons instantly, and the canonicalisation of positions with dozens of options became fast enough to run on every figure.

That is not an optimisation detail so much as the reason this site can assert its values. assertValue runs on every figure and would be unaffordable without it.

The reductions are checked against the definition. For each figure, the raw position and its canonical form are compared by the independent route — build the difference, ask who wins moving second — and the figure refuses to draw if the two disagree. $\{0, -3 \mid 1\}$ reduces to $\{0 \mid 1\}$ and the difference is confirmed a second-player win.

Uniqueness, and why it matters #

Uniqueness is not decorative. Without it, canonical forms would be a heuristic simplification and equality would still need a search.

The proof is a comparison argument. If two canonical forms are equal as games but different as trees, then one has an option the other lacks in a way that survives both reductions — and tracing what each player does with that option produces a contradiction with the reductions’ own hypotheses. Nothing deep happens; it is bookkeeping. The content is that the two reductions are exactly enough, neither leaving redundancy behind nor removing anything real.

Consequences follow immediately:

A finite decision procedure for equality. Canonicalise both, compare trees.

A well-defined notion of the simplest form of a value. The canonical form of $\tfrac12$ is $\{0 \mid 1\}$, and every other position worth $\tfrac12$ reduces to exactly that.

A birthday for each value — the depth of the canonical tree, which is the earliest day a position of that value can exist, and which is what the simplicity rule is quantifying over when it says “simplest”.

What the canonical form throws away #

The reductions discard real information about the position, and it is worth being precise about what.

Moves that were available. A dominated option was a legal move, and a player may well play it. The canonical form says it cannot change the outcome under perfect play, not that it does not exist.

How long the game runs. Bypassing a reversible option removes two plies. The canonical form is the same game in the sense that matters and a shorter one in the sense a clock would measure.

Robustness against a fallible opponent. An option that is dominated by a hair is discarded on the same terms as one dominated by a mile, and against an imperfect opponent the difference could be everything.

So the canonical form is the position’s behaviour in sums, with everything else stripped. That is exactly the right object for the theory and the wrong object for a player, which is a recurring tension — a value is not a strategy, and a canonical form is not a plan.

The forms that cannot be simplified #

It is worth knowing which positions the reduction leaves alone, because they are the interesting ones.

A position is already canonical when no option dominates a sibling and no option is reversible. That happens when the options are genuinely incomparable — each offering something the others do not — and when no opponent reply undoes a move.

$\{1 \mid 0\}$ is canonical: one option each, nothing to dominate, and neither is reversible because neither reply returns to something comparable with the whole. It is a switch, and switches are the canonical forms that make positions worth fighting over.

$\{0 \mid \ast\}$ is canonical: it is $\uparrow$, and its two options are of entirely different kinds.

$\{0, \ast \mid 0, \ast\}$ is the case that goes the other way, and it is the one worth being careful about. It looks reducible: each side has two options, they are confused with each other rather than incomparable, and a reader who has just learnt domination will reach for it. Nothing fires. The form is already canonical, and the value it carries is $\ast 2$ — which is not readable off the four options at all, and is why the figures above refuse to draw a position with no reduction in it.

That is the warning in both directions. A tangled-looking position may collapse to a small nimber, and a position that looks like it must simplify may be the canonical form of a value whose name it does not resemble. The only way to know is to run the algorithm.

Who found it, and when #

The reductions and the uniqueness theorem are Conway’s, in On Numbers and Games, 1976. The terminology — dominated, reversible, bypassed — is his, and it has not been improved on.

The reversible reduction is the part everybody remembers struggling with, and the histories are candid about it. Conway’s own presentation moves quickly; Winning Ways slows down considerably and still loses readers at the same paragraph. The difficulty is not technical, it is that reversibility is a statement about a two-move sequence with a comparison against the original position, and there is no way to say that briefly.

Uniqueness is what the reduction is for #

The canonical form is usually introduced as a simplification, and simplification is the smaller half of what it does. The larger half is uniqueness, and it is worth separating them.

Simplification says the form is small: dominated options gone, reversible ones bypassed, nothing left that a sum could not detect. That is a saving and it is measurable — and it is minimal in options and in no other currency, which is a caveat rather than a defect.

Uniqueness says two positions of the same value have the same canonical form. That is what turns equality from a search into a comparison of written objects: reduce both and look. Without it, deciding $G = H$ would remain a search over the difference game every single time, and the reduction would be a convenience rather than the foundation of everything above it.

The two are independent and only the second is load-bearing. A reduction that produced a small form without uniqueness would save memory and settle no equalities; a reduction that produced a unique form without shrinking anything would still be the whole apparatus.

That is why the confluence result matters as much as the reduction itself. The two operations may be applied in any order, and the answer is the same — which is what makes the form well defined rather than an artefact of how the reduction happened to run. A normal form is a claim about a procedure’s independence from its own schedule, and it is the claim that the rest of the subject rests on.

Where the model stops #

Normal play. Domination is monotonicity and monotonicity fails under misère play. Almost nothing here survives the swap, which is why the misère theory needed entirely different machinery.

Finite games. The recursion needs termination. Loopy games have canonical forms only in a modified sense, developed separately.

Uniqueness is not smallness in any other sense. The canonical form is the unique reduced tree; it is not guaranteed to be the smallest description of the position, and a position with a short rule statement can have an enormous canonical form.

The computation is exponential in general. Canonicalisation is fast for small positions and hopeless for large ones, which is the practical limit on everything this site computes. The figures use positions small enough to reduce exactly.

The ladder from here #

Nearby: the uniqueness proof in full; reversibility worked through slowly on a single position; the birthday of a value as the depth of its canonical tree; and the number-avoidance theorem, which is a statement about canonical forms in disguise.

Then infinitesimals, whose canonical forms are tiny and whose behaviour is not, and comparison, which is the operation canonicalisation is built out of and deserves its own treatment.