The reduction that puts options back

The canonical form is sold as a simplification, and the word does a lot of quiet work. It suggests that reducing a position is a matter of throwing things out, that the form only ever gets smaller, and that the process is a tidying-up whose result is obviously the tidiest thing available.

Half of that is true. The other half has a step in it that makes the form bigger.

The step is reversibility, and it is not a footnote to domination. It is the half of the reduction that carries the theory: uniqueness, the substitution of one position for another inside a sum, and the whole idea that a value is a small object rather than a game tree, all rest on it. This is what it does.

The two steps, and how differently they behave #

A form is a position written out: a list of Left options and a list of Right options, each of them a form in turn. Two forms can be different and be worth the same, and the reduction is the procedure that takes any form to the one distinguished representative of its value.

It has exactly two steps.

Delete a dominated option. If Left has moves to $A$ and to $B$ and $B \geq A$, then Left has no use for $A$ — whenever $A$ would be good enough, $B$ is at least as good — so $A$ goes. The list gets one shorter, the value does not move, and nothing else changes.

Bypass a reversible option. This one is different in kind, and its statement is longer for a reason. Suppose Left has a move to $A$, and from $A$ Right has a reply to some $B$ with $B \leq G$ — the reply gets Right back to something no worse for them than the position Left left. Then Left’s move to $A$ was, in a sense, refuted before it was made: whatever Left hoped to gain, Right can take back.

The reduction does not delete the move. It replaces it with all of Left’s options from $B$.

That is the whole difference. Deleting removes one item from a list. Bypassing removes one item and inserts a list, and there is nothing in the rule that says the inserted list is short.

What a bypass actually substitutes #

The reason a bypass has to substitute rather than delete is worth having, because it is the reason the step exists at all.

Deleting Left’s move to $A$ outright would be wrong. Left’s move to $A$ might be the only move Left has, and a position where Left cannot move is a different position. What the argument establishes is not that the move is useless but that it is not worth more than what happens after Right’s refutation — so the move may be replaced by the things Left could have done from there instead, which is a shortcut through two plies rather than a deletion.

So the size of the form after a bypass is the size before, minus one, plus however many options the refuting position hands over. If that position has two Left options, the form comes out one wider. If it has three, two wider. There is no bound in the rule.

Why the effect is invisible on day two #

The census above splits into two halves that look like they should agree and do not. Among the 256 forms whose options are the games born by day one, there are 128 bypasses available and every single one takes the form from $n$ options to $n-1$. Not one widens anything.

That is not luck, and it is not evidence that widening is rare. It is a fact about how little room there is one day in.

A bypass at a Left option widens the form when the refuting position has two or more Left options of its own. The refuting position in a day-two form is a game born by day one — one of $0$, $\ast$, $1$, $-1$ — and not one of those has two options on a side. So the substituted list is always empty or a single item, and the arithmetic can only come out at $-1$ or $0$.

This is worth stating plainly because it is a trap. Anybody checking the reduction on small examples — and small examples means day two, because day two is where a person can enumerate by hand — will see the form shrink every time, will conclude that reduction is monotone, and will be wrong about the first case beyond their reach.

The census, one day out #

Forms built with a single option on each side, the Left option drawn from the 1,474 values born by day three and the Right option from the 22 born by day two: 32,428 of them, offering 48,210 bypasses between them.

Of those bypasses, 33,749 narrow the form, 13,917 leave it exactly as wide, and 544 widen it. The largest widening in the sweep is by one option, and the position that produces it is small enough to print:

$$\{\{0 \mid \ast 2\} \mid 0\} \quad\longrightarrow\quad \{0,\ \ast \mid 0\}$$

Left’s move to $\{0 \mid \ast 2\}$ is answered by Right’s move to $\ast 2$, and $\ast 2 \leq \{\{0 \mid \ast2\} \mid 0\}$ fails — but the other direction of the reversibility test succeeds, and the substitution puts in the two Left options of the refuting position where there had been one. The value is $\uparrow\!\ast$, before and after.

The form the reduction reaches can be wider than the form it started from #

The 544 widening steps are steps, and a reader may reasonably suspect that whatever a bypass adds gets deleted again shortly afterwards. Mostly it does. Not always: of the 32,428 forms in the sweep, 60 have a canonical form with more options than they have themselves.

That is the sentence the essay exists for. “Canonical form” is not a synonym for “smallest form”. It is the unique form with no reduction available, and uniqueness is the property the theory needs; smallness is a property the theory never claimed and does not have.

The consequence is one rung across. The gift horse principle says an option may be handed to a player for free provided it is not better than the position — and a census run there found that every option of every day-three form is a legal gift, 38,416 of 38,416, while 1,468 of those forms fail to contain the options of their own canonical form. The two findings are the same fact from opposite sides. The reduction does not merely take gifts back; it takes some back and hands different ones out.

Then why does it stop? #

A reduction whose steps can make the thing bigger raises a question the essay has been walking past: what stops it running for ever, adding options to a form that never settles?

Something does decrease at every step, and it is not the width. It is the number of nodes in the whole tree.

Follow one bypass. Left’s option $A$ is removed, and what goes in its place is the Left options of $B$ — where $B$ is one of $A$’s own Right options. So every subtree inserted was already sitting inside the subtree that was taken out, two levels down. What is lost is $A$ itself, $B$ itself, $B$’s Right options and any of $A$’s other options; what is gained is a set of subtrees that were part of the loss.

The node count therefore falls strictly, at every bypass, without exception, and a deletion of a dominated option obviously falls too. A quantity that strictly decreases and cannot fall below zero cannot decrease for ever, so the procedure halts.

That is a satisfying resolution of the essay’s tension and it is worth naming as the shape it is. This is the same distinction the recursion itself rests on: a process terminates because some well-founded quantity descends, and the quantity need not be the one a reader is watching. Watching the width, the reduction looks as though it might not stop. Watching the nodes, it obviously does.

What “canonical” is and is not minimal in #

That leaves a sharper version of the essay’s central correction, and it is worth stating in full because two different denials are in play.

Not smallest in width. Sixty of the 32,428 forms have canonical forms with more options than they started with. Width is not what the reduction optimises and the reduction does not claim it.

Smaller in nodes than where it started. Every step strictly reduces the node count, so a form’s canonical form is never a larger tree than the form itself. That is a real monotonicity and it is the one doing the work.

And “canonical” means neither. It means the form on which no reduction step is available — the fixed point of the procedure — and the theorem that earns the name is that the fixed point is unique, reached whatever order the steps are taken in. Uniqueness is what licenses writing “the value of this position is $\uparrow\!\ast$” and treating two positions with the same reduced form as interchangeable everywhere.

Nothing in that requires smallness of any kind. The reduction could have terminated at a large form and the theory would be unaffected, provided it terminated at the same large form every time.

So the correct summary of the two halves is: the reduction is monotone in the measure that makes it terminate and not in the measure a reader is looking at, and the word “simplification” borrows its plausibility from the second while the mathematics runs on the first. That is why the sixty widened forms are a curiosity rather than a problem — they are a failure of a property nobody needed, in a procedure whose actual guarantees are untouched.

Where the extra options come from, and why they are legal #

A reader who has followed the arithmetic may still be uneasy about the legitimacy of putting options in. Deleting a move somebody would never make is easy to accept. Handing a player moves they did not have looks like changing the game.

It is not, and the reason is the one the gift horse principle is about. Adding a Left option to a position leaves the value alone provided the added option is not at least as good as the position itself, and the options a bypass adds satisfy that condition by construction: they are Left’s moves from a position $B$ that Right was happy to reach, and $B \leq G$, so nothing reachable from $B$ can be better for Left than $G$ is.

So a bypass is two legal operations run together. It hands Left every move it could have made from the refutation — all of them free — and it takes away the move to $A$, which is now dominated by the collection just handed over. Neither half moves the value, and the composite is the step.

That reading also explains why the substituted list is the whole list rather than a selected part of it. Selecting would require an argument about which of $B$’s options Left might want, and the reduction has no such argument to make. It hands over everything and lets domination sort it out afterwards, on the next pass.

That the four forms $\{0 \mid 1\}$, $\{0, -1 \mid 1\}$, $\{0 \mid 1, 2\}$ and $\{0, -1 \mid 1, 2\}$ are all worth a half is a claim about every sum they could be put into rather than about the pictures, and the reduction is what turns that claim into a finite check. The bypass is the step that makes the check terminate.

Two things this does not break #

It would be easy to read the above as a crack in the theory. It is not, and the two properties that matter survive untouched.

The reduction terminates. The width can go up, but the depth cannot: a bypass replaces an option by options of a position two plies down, so every substituted option is shallower than the one it replaced. The measure that decreases is not the number of options; it is the total depth of the tree, and it decreases at every step of either kind. A procedure whose obvious measure does not decrease and which terminates anyway is a completely ordinary situation once the right measure is found, and finding it is the proof.

The result does not depend on the order. At any moment several steps may be available — two dominated options, a reversible one, or all three — and an author picks. Uniqueness is confluence: whichever picks are made, the same form comes out. Reversibility is what makes that non-obvious, since a bypass changes which other options exist and therefore which dominations are available next.

The reason the theory needs this step at all #

Domination alone does not reach a unique form, and the failure is not subtle. Consider a position in which Left’s only move is one Right can answer straight back to something no worse than the start. No option is dominated — there is only one Left option, and a single option cannot be dominated by a sibling it does not have — so a reduction with only the first step available would declare the form finished, and two forms of the same value would come out different.

The bypass is what closes that gap, and it closes it by being allowed to look one ply deeper than domination does. Domination compares an option with its siblings, which is a comparison inside one list. Reversibility compares an option’s replies with the position, which crosses two levels. That extra reach is precisely what buys uniqueness, and it is also what makes the step capable of enlarging the form: an operation that can see two plies down can bring things up from there.

The trade is worth naming because it recurs, and the search it replaces is the reason anybody cares. Every strengthening of a reduction procedure that buys a stronger normal form buys it by allowing the procedure to look further, and looking further is what lets material move upward. A reduction that only ever deletes is a reduction that only ever sees one level, and one level is not enough.

What the solver computed, and how #

Every step is enumerated rather than applied blind. For a given form, the available dominations are found by comparing each option against its siblings, and the available bypasses by taking each option’s replies and comparing them with the position itself — both using the ordinary comparison, which plays the difference and reads its outcome.

Applying a step builds a new form: for a deletion, the list with one entry removed; for a bypass, the list with one entry replaced by the refuting position’s options on the same side, duplicates removed. The width is read off the result rather than predicted, which is what allows the census to report $-1$, $0$ and $+1$ as three distinct outcomes instead of asserting that bypasses simplify.

The check that could have failed is the one on day two. A sweep that reported widening there would have contradicted the argument about day-one option lists, and would have meant the substitution was implemented wrongly rather than that something interesting had been found. It reported none.

Where the model stops #

The sweep is over forms with one option on each side, which is a slice of day-four forms chosen because the full set is out of reach. That slice is enough to exhibit the phenomenon and is not enough to say how common it is: 544 in 48,210 is a rate about a particular slice, and a form with four options a side offers more places for a wide refutation to appear.

The largest widening found was by a single option. There is no argument here that one is the maximum, and the rule permits more — a refuting position with five Left options would add four. Finding one would need a pool of positions deeper than this evaluator can enumerate, which is the standing limit on every census on this site.

Where the ladder goes next #

This rung establishes that one of the two reductions is not a contraction. The rung above is the question that leaves open: whether the canonical form’s width is bounded by anything at all in terms of the form it came from, which is a question about day four and beyond.

Two neighbours run alongside. An option nobody would take is the same boundary approached from the additive side, and nobody wants to move here is the other characterisation of what the canonical form is doing — the one that never mentions options at all, and asks instead what each move costs the player who makes it.