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.

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 on a board.

Consider $\{0 \mid \ast\}$, which is $\uparrow$, and add a star: $\uparrow + \ast$. The sum has a Left option in which Right’s immediate reply returns the position to something no better than it began. That is the reversible pattern exactly, and bypassing it is how $\uparrow + \ast$ reduces to the two-option form it has, rather than the four-option form the definition produces.

The same thing happens all over Hackenbush. A green edge at the base of a stalk gives both players a move that removes everything, and those moves are frequently reversible — the opponent’s reply undoes whatever was gained, so the reduction splices past them and the canonical form is much smaller than the raw position.

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 build.

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.

What the solver computed #

canonical(g) in lib/cgt.js implements the loop 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 build.

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 build fails 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\}$ reduces, because the two Left options are confused with each other rather than incomparable in the required way — and what it reduces to is $\ast 2$, which is not obvious from looking at it.

That last case is the warning. Incomparable options are not automatically irreducible, and a position that looks maximally tangled may collapse to a small nimber. 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.

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.