How much a list of options can lose

A Left option is dominated when some other Left option is at least as good, and the reduction throws it away. The reduction that always shrinks counted the throwing: 480 of the 520 options that come off the 256 forms born by day two come off by deletion, and the operation never once adds an option or changes a value.

That essay closed by naming a quantity nobody here had measured. The length of the longest chain in an option list is the exact number of deletions the form admits. It was written without being computed, and it is a lower bound and nothing more.

The correct statement is shorter than the guess and does not mention chains at all.

What a list of options is #

Write out Left’s options and ask, of each pair, which is at least as good as which. The answer is a comparison between games, so it has four possible outcomes rather than three: one may be greater, one may be less, they may be equal, or the pair may be confused — neither is at least as good as the other, and no amount of further computation will settle it, because there is nothing there to settle.

That makes the list a partial order. Not a ranking, which is what a reader coming from a scoring game expects, and not an arbitrary jumble either: the relation is transitive, so the options arrange themselves into a shape with a top and a bottom and a good deal of incomparability in the middle.

The reduction reads that shape and nothing else. Left’s option $A$ goes exactly when some other option $B$ has $B \ge A$, so what survives is the set of options that nothing else is at least as good as. Those are the maximal elements of the order, and they are what a mathematician would call an antichain: pairwise incomparable, because anything comparable to a maximal element and not below it would be above it, and then the first would not have been maximal.

So the count is forced:

$$\text{deletions} \;=\; |\text{list}| \;-\; |\text{maximal elements}|$$

with no dependence whatever on what the values are. Two lists with the same shape lose the same number of options, whether their members are integers, switches or infinitesimals.

The census #

The pool is every subset of the twenty-two values born by day two, taken two, three and four at a time. Subsets rather than multisets: a repeated option is dominated by its own copy and says nothing about the order, so including repeats would inflate the count with a case that has no shape.

Two elements give 231 lists and 179 deletions, which is to say that 52 of the 231 pairs are incomparable and lose nothing. That number is not new — the simplest game above both found the same 52 while asking a different question about the same order — and its reappearance here is a check rather than a discovery.

Three elements give 1,540 lists and 2,549 deletions. Four give 7,315 and 18,921, which is an average of 2.59 deletions from a list of four. Most option lists lose most of their options, which is the practical reason canonical forms are small.

The one four-element antichain #

Among the 7,315 four-element lists there is exactly one that loses nothing, and it is worth naming: $0$, $\ast$, $\{1 \mid -1\}$ and $\ast 2$.

Every one of the four is confused with every other. That is not a coincidence about four particular games. A position confused with zero is one where whoever moves first wins, and by day two the collection of such positions is small; the four here are the whole of it, and the order among them is empty. Every other four-element list born by this day has a comparison somewhere inside it.

A list like that is the worst case for the reduction and the best case for a player: four genuinely different moves, none of which can be ruled out by comparing it with another.

Why the longest chain is a bound and not an answer #

A chain is a run of options each at least as good as the next. Every element of a chain except its top is dominated — by the top, if by nothing else — so a chain of $c$ elements guarantees at least $c - 1$ deletions. That is the whole content of the guess, and as a bound it is correct on every list here.

It stops being exact the moment the list contains two chains that are incomparable with each other. Two chains of three, side by side, lose four options between them and have a longest chain of three, which predicts two. The bound sees one chain at a time and the reduction sees all of them at once.

The counts say how often that matters. On lists of three the bound is exact 1,259 times out of 1,540, which is 82 per cent. On lists of four it is exact 3,859 times out of 7,315, which is 53 per cent — barely more than half, and falling.

And the widest antichain is not the survivors #

There is a second quantity a reader reaches for, and it fails differently. The survivors form an antichain; the natural guess is that they form the widest antichain in the list — the largest set of pairwise incomparable options anywhere in it.

They need not. An antichain sitting low in the order can be wider than the set of maximal elements above it, and then the reduction keeps the narrow one. On four-element lists the survivors are the widest antichain 4,580 times out of 7,315, which is 63 per cent.

The two failures are not the same failure, and the census separates them. The list $0$, $-1$, $\ast$, $\{0 \mid -1\}$ has two maximal elements and two deletions; its longest chain has two elements and predicts one; and its widest antichain has two, which is right. So the chain bound can fail while the antichain reading holds. The reverse never happens in this pool, which is a fact worth reporting and not one this essay can explain.

Why the reverse cannot happen #

That the chain bound can fail while the antichain reading holds, and never the other way round, is not a fact about this pool. It is forced, and the argument is four lines of order theory with nothing about games in it.

Write $n$ for the length of the list, $m$ for the number of survivors — the maximal elements — $c$ for the longest chain and $w$ for the widest antichain. The reduction deletes $n - m$ options, and the chain bound predicts $c - 1$.

A widest antichain can never be larger than $n - c + 1$. Take a longest chain, which has $c$ elements. Any two of them are comparable, so an antichain contains at most one of them, and everything else in the list is fair game: $w \le (n - c) + 1$.

And the survivors are an antichain, so $m \le w$. Nothing else is needed. If the chain bound is exact then $n - m = c - 1$, which rearranges to $m = n - c + 1$; putting the two inequalities together gives

$$m \;\le\; w \;\le\; n - c + 1 \;=\; m,$$

so $w = m$ and the survivors, being an antichain of the maximum possible size, are a widest antichain. Chain-exact implies antichain-correct, on every list of every length in every partial order, and the census could not have found a counterexample however wide the pool was made.

The converse fails because the two inequalities can both be slack at once. The list of two incomparable three-chains has $n = 6$, $c = 3$, $m = 2$ and $w = 2$: the survivors are the widest antichain, and the bound predicts two deletions against four. There the second inequality is tight and the first is not, which is exactly the configuration the census reports 47 per cent of the time on lists of four.

So the pool’s asymmetry has a reason and the reason says the two readings are not two guesses of equal standing. The antichain reading is implied by the chain reading and holds in cases the chain reading misses, which makes it the better of the two — and it is still only 63 per cent, because $m \le w$ can be slack on its own.

The count, and the machine that does the counting #

An argument is not a measurement. Deletions equal length less maximal elements is a two-line proof, and a two-line proof about a reduction is exactly the sort of thing that turns out to be about a slightly different reduction than the one the code runs.

So every list in the census is also turned into a real form — Left’s options and nothing for Right — handed to dominationOnly, which is the reduction this site uses everywhere, and asked how many options it actually removes.

The habit is the same one the Hackenbush figures follow, where a value is computed twice — once by the game recursion and once by reading the drawing in binary — and the figure refuses to build if the two disagree.

How the count behaves as lists get longer #

The distribution is worth looking at rather than the average. Of the 231 two-element lists, 52 lose nothing and 179 lose one. Of the 1,540 three-element lists, 22 lose nothing, 487 lose one and 1,031 lose two. Of the 7,315 lists of four, one loses nothing, 207 lose one, 2,607 lose two and 4,500 lose three.

The mode moves to the right faster than the length does. At three options the commonest outcome is losing two of the three; at four it is losing three of the four, which leaves a single option standing. That is a statement about how much comparability there is among the day-two values, and it is why canonical forms stay small while the number of forms explodes: 256 forms carry 22 values, and most of the collapsing happens here.

The lists that lose nothing are the antichains, and they thin out at exactly the rate the numbers above imply — 52, then 22, then one. There is no five-element antichain among the day-two values at all, so from five options upward every list on this day loses something.

A ranking would make the reduction trivial #

It is worth saying what would happen if the order were total, because that is the intuition a reader arrives with and it is wrong in a specific way.

If every two options were comparable, every list would be a chain, the maximal element would be unique, and the reduction would keep exactly one option a side. Every canonical form would be $\{A \mid B\}$ with one option each way, the whole apparatus of dominated options would collapse into take the best move, and there would be nothing to write down beyond a pair.

That is what happens in a scoring game, where the options carry numbers and numbers are totally ordered — and it is why a scoring game has no theory of this kind and needs none. The reason combinatorial game theory has canonical forms with several options a side is precisely the fourth relation: a position can be confused with another, so a player can hold two moves neither of which dominates, and the form has to keep both because there is a context in which each is right.

So the count above is a measure of something real. Every deletion is a move a player never has to consider again; every survivor is a move whose merits depend on the rest of the board.

What this says about the other reduction #

Domination is the half of the canonicalisation that behaves. It removes exactly one option, it never adds one, and its total is decided by the shape of the order, which is the strongest form of “no surprises” available.

The reduction that puts options back is the other half, and none of the three sentences above survives the move. Bypassing a reversible option replaces it with a whole option list — the Left options of the position it reverses through — so a form can come out of a single step wider than it went in. There is no order to read the count off, because the options that arrive were not in the list to be ordered.

That asymmetry is why the two are usually described together and behave nothing alike, and it is why reducing to a fixed point is necessary rather than tidy: a bypass can put back an option that a deletion had just removed, and a deletion can become available for the first time after a bypass has arrived.

What the picture cannot show #

A drawing of an option list shows the order and hides the values. That is deliberate and it is also a limitation: two lists with identical drawings can produce forms whose canonical values are wildly different, because the value of $\{A, B \mid C\}$ depends on what $A$, $B$ and $C$ are and not merely on which of them beat which.

So the count of deletions is a fact about the shape and the result of the deletions is not. The reduction takes the same number of options off two lists with the same order and leaves two forms with nothing else in common.

There is a second thing the drawing cannot show. Every arrow in it is a comparison, and a comparison between two games is a search over the game tree of their difference — expensive in a way an arrow makes invisible. A four-element list needs twelve of them before a single option can be deleted, which is why a canonicalisation is not cheap even when its answer is small.

The convention this depends on #

Normal play, throughout. Domination is defined by $\ge$, and $\ge$ is defined by outcomes: $A \ge B$ means Left does at least as well in $A + X$ as in $B + X$ for every position $X$, with the player unable to move losing.

Reverse that last clause and the order changes completely. Misère play has no negatives, so $A - B$ is not a test for anything, and the relation this whole essay is about has to be rebuilt from outcomes directly. The shapes are different, the maximal elements are different, and the reduction that reads them keeps almost nothing.

The strength of that convention is easy to understate. It is not that $\ge$ happens to be defined by outcomes; it is that every relation in this subject is, and the order on an option list is the same order that decides which of two whole boards is better. So the shape drawn above is not a diagram of a local preference. It is a fragment of the one order the theory has, restricted to four of its members, and the reduction is reading that order rather than a summary of it.

That is also why the shape cannot be guessed from the notation. $-1$ and $-1\ast$ differ by a star and sit one above the other; $0$ and $\ast$ differ by a star and are incomparable. The same difference, two different answers, and the only way to know which is to run the comparison.

Where the ladder goes next #

dominance has two rungs to here: what deleting removes, and what decides how much. The five above take the question this page points at — which options are deleted rather than how many — and follow it until the instrument breaks.

Which option the reduction keeps puts the two candidate descriptions this page ends on to a vote over 1,586 Domineering option lists. Takes the most space is right 47 per cent of the time; leaves the opponent fewest replies is right 90 per cent. The second wins, and it is not the one a player asked in advance would name.

The margin a count needs then turns the nine-in-ten into a bound by asking how large the gap in that count has to be before it is never wrong. Over 57,879 pairs of options the reply count points the wrong way 1,052 times at a margin of one, seventy-two times at two, and never at three. The weight that blunts the count tries the obvious refinement — weigh a reply by whether it leaves the opponent anything — and it is worse in every direction, with all seventy-two of the pairs it was written for unaffected.

The last two rungs are about the census rather than the game, and they are the ones worth knowing before starting. The threshold was a fact about the census inspects those seventy-two one at a time: they are not a class of shapes but sixteen positions up to symmetry, on the largest board of the sweep, at two depths — and one board larger the count fails at a margin of three, the number the ladder had been quoting as the point where it never does. A threshold is a detection limit runs eleven more sweeps and finds no property of a board orders the thresholds at all. What moves, on every board measured twice, is the depth of the sweep.

So the ladder above this one ends by measuring its own reach rather than the game’s. That is the honest fate of a rule that is right nine times in ten: the tenth is not a class, and looking for one finds the resolution of the instrument instead.

The neighbour worth the trip is the simplest game above both, which reads the same order for a different purpose: not what the reduction removes, but what structure the order carries. It finds far more of it than a partial order is entitled to, and its 52 incomparable pairs are the same 52 that survive here.