An option nobody would take

Every simplification on this site runs one way. Canonical form deletes a dominated option and bypasses a reversible one; the census of forms counts how many drawings collapse onto one value; the reduction is a machine for throwing things away. A reader who has met only that machinery could be forgiven for believing that a position’s options are precious — that each one is load-bearing until proved otherwise.

They are not, and the demonstration runs in the opposite direction. A move can be handed to a player, for nothing, and the position is worth exactly what it was worth before.

The fourth row is the one to look at twice. Left is handed a move to $1$ — the best thing on the board, the value Left is fighting for — and the position does not budge. That is not because $1$ is a bad move. It is because $1$ is exactly as good as the move Left already had, and an option that is not better than something already available is worth nothing to add.

The principle, stated so it can fail #

The rule is the gift horse principle, and it has one hypothesis:

$$G = \{G^L,\, H \mid G^R\} \quad \text{whenever} \quad H \ntriangleright G$$

where $H \ntriangleright G$ is read “H is not greater than or equal to G” — H is below the position, or confused with it. The mirror statement holds for Right with the inequality reversed.

Stated that way it is a prediction, and a prediction is something a census can disagree with. So every value born by day two was handed every value born by day two, on both sides, and the results were compared against what the principle says should happen.

The four relations sort themselves completely. Of the 484 additions, 179 hand over a gift strictly below the position and all 179 are free; 104 hand over one confused with it and all 104 are free; 179 hand over something above and none is free; and 22 hand the position itself back, none of which is free. There is no mixed case anywhere in the grid. The boundary the census draws is exactly $H \ntriangleright G$, with no exception in either direction.

The grid is the order table #

Once the boundary is known to be exactly $H \ntriangleright G$, the census stops being a measurement of the principle and becomes a measurement of something else: the filled cells of that grid are the complement of the order relation on day two, printed in full.

That reading pays immediately, because it says how many free gifts a position has without trying any. A value $G$ admits exactly $22 - |\{H : H \ge G\}|$ of them, so a position’s supply of gift horses is a count of how much of the day sits above it. The two extreme rows in the figure are the two extreme positions in the order: $-2$ is below everything, so nothing is a legal gift to it and its row is empty; $2$ is above everything but itself, so 21 of the 22 are legal. Every other row is somewhere between, and its length is a statement about where the value sits rather than about gifts at all.

The tallies then say something about day two that the essay was not looking for. There are $22^2 = 484$ ordered pairs, of which 22 are a value with itself. Of the remaining 462, 179 have the gift strictly below and 179 strictly above — necessarily equal counts, since each is the other transposed — and 104 are confused. Confusion is symmetric, so those 104 ordered pairs are 52 unordered ones, and of the $\binom{22}{2} = 231$ unordered pairs of distinct day-two values, 179 are comparable and 52 are not.

So a little over three quarters of day two is ordered, and a quarter of it is not. That is a much higher rate of comparability than the deeper days sustain, and it is worth flagging as the reason a reader’s intuition about these values is formed on unusually well-behaved material — how rare it is to be bigger measures the same ratio where it matters, on a population large enough for the partial order to look partial.

It also explains the shape of the filled region. The figure notes that it is not a triangle; the sharper statement is that it is a triangle plus the incomparabilities, and the incomparabilities are a quarter of the off-diagonal grid. A total order would have given a clean staircase and a rule phrased as “a worse move may be added” would have been correct. The staircase has 52 holes punched through it, and each hole is a gift the weaker rule would have refused.

Why the boundary is where it is #

The condition looks like a technicality until it is unpacked, at which point it stops being a condition at all and becomes a restatement of what a comparison is.

Adding a Left option can never hurt Left, so the enlarged game $G'$ satisfies $G' \geq G$ for free. The whole question is the other direction: is $G' \leq G$? By the only definition there is, that asks whether Right, moving second, wins the difference $G' - G$.

Right’s job is to answer every Left move. Against Left’s old options, Right answers exactly as they would have in $G - G$, which is a second-player win. Against the new option, Left has moved to $H - G$ and it is Right’s turn — so Right needs to win $H - G$ moving first, and “Right moving first wins $H - G$” is character for character the statement $H \ntriangleright G$.

The hypothesis is not a sufficient condition somebody found by trying things. It is the exact requirement, written out, and that is why the census has no ragged edge.

Every row of the hero figure is that argument run once. $\ast$ against $\pm 1$ comes back confused and $1$ against $\pm 1$ comes back confused, so Right moving first wins both differences and both gifts are free. $\pm 1$ against itself comes back equal, so Right moving first in the difference loses, and that is the row where the value moves. The three verdicts are three different outcomes of one comparison, and the principle is nothing more than a name for which of them is wanted.

Not better is weaker than worse #

The interesting half of the census is the 104.

When an option is deleted as dominated, the reason is that a sibling is at least as good: one Left option beats another, so the loser is dead weight. That is a comparison that succeeded. When an option is added as a gift horse, the requirement is only that the comparison $H \geq G$ fails — and in a partial order a comparison can fail in two quite different ways.

It can fail because $H$ is genuinely smaller. It can also fail because $H$ and $G$ are incomparable: neither is at least the other, and whichever player moves first in their difference wins. Of the 283 free gifts, 179 are of the first kind and 104 are of the second. Better than a third of the additions this principle permits are options that are not worse than the position at all.

$\pm 1$ is the clearest instance. Every one of $0$, $\ast$, $\tfrac12$, $\uparrow$, $\ast 2$ and $1$ is confused with it — none of them is below it — and every one of them may be handed to Left for nothing. A rule phrased as “a worse move may be added” would forbid all six and would be wrong six times.

The equal case, which is not a rounding error #

Twenty-two of the 484 additions hand a position itself as an option, and every one of them changes the value. That is the boundary sitting at $\ntriangleright$ rather than at $\ntriangleright$-or-equal, and it is worth a sentence because it is the one place where “an option nobody would take” stops being an accurate gloss.

If Left is given a move from $G$ to $G$, then in the difference $G' - G$ Left moves to $G - G$, which is zero, and Right — to move in a second-player win — loses. So $G' > G$ strictly. Handing a player a move that leaves the position unchanged is handing them a free tempo, and a free tempo is worth something in every game on this site.

That is also why the rule cannot be softened to “any option that is not strictly better”. Equality is not strictly better and equality is not free.

What the solver computed, and how #

Three exhaustions, none of them large.

The grid builds all 22 values born by day two — the 256 forms $\{L \mid R\}$ with $L$ and $R$ subsets of $\{0, 1, -1, \ast\}$, canonicalised and deduplicated — and for each ordered pair $(G, H)$ constructs $\{G^L, H \mid G^R\}$, canonicalises it and tests equality against $G$ by playing the difference. That is 484 constructions, and their relation is recorded beside the result rather than inferred from it.

The mirror runs the same 484 with the gift on Right’s side. The tallies come back transposed exactly — 283 free again, with the 179 above now free and the 179 below now not — which is the statement that nothing in the principle is about Left.

The third exhaustion is the one that turns the principle into a fact about forms rather than about additions somebody chose to try. Take every form born by a day and ask, of each option it already has, whether that option would have been a legal gift.

The theorem hiding behind it #

That first row is a standing theorem in this subject, usually met long before gift horses and rarely connected to them: no Left option of a game is ever greater than or equal to the game itself, and symmetrically for Right. The proof is one line of the same kind as the one above, and its consequence here is a pleasing collapse of two ideas into one.

The gift horse principle says: H may be added exactly when H already satisfies what every option satisfies. The permitted gifts are not a strange class of degraded moves. They are the class of things that look, to the comparison, exactly like options — and the census says so with a zero: no exception among 38,416 options of 9,604 forms.

What the principle is worth in an argument #

Gift horses are a proof technique before they are anything else, and the technique is worth spelling out because it is the reason the lemma exists.

Suppose two games have to be shown equal and their forms do not match: one has options the other lacks. Canonicalising both would settle it, and canonicalising is a search whose cost grows with the trees. The gift horse route is to enlarge both — hand each side the options it is missing, provided each gift is legal — until the two option sets coincide, at which point the two games are identical as written and equality is a matter of reading.

Zero is the smallest worked example and it is in the section above: $\{\ \mid\ \}$ becomes $\{-1 \mid\ \}$ becomes $\{-1 \mid 1\}$, both steps free, and a game with no moves in it has been turned into a game with two bad moves in it without changing what it is worth.

The technique’s real use is in the other direction, in proofs about families. A theorem that says “every game of such-and-such a shape equals such-and-such” is much easier to state when both sides can be given a common option set first, and the gift horse principle is what licenses adding options to the side that lacks them.

That is why it is a lemma in Winning Ways with a joke for a name and a paragraph of treatment. It is machinery, and the exhaustion in this essay is an attempt to say exactly how much machinery it is: 283 of 484 additions, more than a third of them options that are not worse than the position at all.

Where the model stops #

It stops one day later than a reader would guess, and the failure is worth having.

If the reduction only ever removed gift horses, then every form would contain the options of its own canonical form: take the canonical form, hand out gifts, and any form of that value appears. On day two that is exactly true — all 256 forms contain their canonical form’s options, with no exception. It is tempting to promote that to a description of what canonicalisation is.

Day three refuses. 1,468 of the 9,604 forms fail it. The simplest instance is $\{\ \mid \downarrow\}$, which is worth $-1$, whose canonical form is $\{\ \mid 0\}$ — and $0$ is not an option of the original at all. The move to $\downarrow$ is reversible: Right’s move there has a Left answer that gets back to something no worse than the whole position, so the option is not deleted but replaced by what lies beyond it.

So the addition picture explains one of canonicalisation’s two rules completely and the other not at all. Domination is exactly the gift horse relation read backwards — an option that could have been given away for free can be taken back for free. Reversibility is a different operation with a different shape, and the census says how often the difference shows: 15% of the day-three forms.

The generalisation, and what it is for #

The principle earns its place because it makes a form bigger on purpose, and a bigger form is sometimes the only way to compare two positions written differently.

The standard use is matching. To prove two games equal, it is enough to show their canonical forms identical — but reaching the canonical form is a search, and the gift horse principle offers a cheaper route in the cases where it applies: enlarge both forms with free gifts until their option sets coincide, and the equality falls out of the writing. Zero is the smallest example. Written $\{\ \mid\ \}$ it has no options at all; hand Left a move to $-1$ and it is $\{-1 \mid\ \}$, still worth zero by the simplicity rule; hand Right a move to $1$ and it is $\{-1 \mid 1\}$ — a position with two real moves in it, both bad, worth exactly nothing. Two gifts turn the emptiest game there is into a game with a fight in it and no value in the fight.

The name is Conway’s, and the joke is the point — a gift horse is not to be looked in the mouth, and the mathematical content is that examining the gift is unnecessary provided it fails one comparison. Winning Ways states it as a lemma and moves on within a paragraph. What the exhaustion adds is the shape of the permitted set: it is not the small, degenerate class the phrase suggests, but 283 of 484 additions, more than a third of them options that are not worse than the position in any sense a reader would recognise.

The asymmetry that is not there #

One reading to head off. The principle is stated for Left, the census is run for Left, and the mirror is drawn in one figure — which invites the thought that Left’s side is the important one.

It is not, and the transposed tallies are the evidence. Run the same 484 additions with the gift going to Right and the counts come back exactly reflected: 283 free again, with the 179 gifts above the position now free and the 179 below it not. Nothing in the principle is about Left; it is about the player receiving the gift, and the inequality points whichever way that player’s preferences point.

The reason is the same symmetry that makes negation work. Exchanging the two players everywhere turns a Left-gift statement into a Right-gift statement and back, so a proof of one is a proof of the other with every symbol reversed.

It is worth checking anyway rather than asserting, because the check is cheap and because this site has found asymmetries in places the symmetry argument said there were none — the printer that named 1∗ correctly on one side and not the other, for instance. A symmetry that has been run is worth more than a symmetry that has been noticed.

Where the ladder goes next #

Two directions lead out. One is the order itself: the census sorted 484 additions by four relations, and the relations are the order on values, which turns out to have far more structure than a partial order is entitled to — every pair of day-two values has a least upper bound inside day two. The other is what the census could not settle: reversibility, which produced the 1,468 counterexamples here and is the half of canonical form that adding options will never account for.