The mirror was the floor

The rate was the alphabet found every ruleset’s rate of new values pinned to the size of the alphabet its positions are written in — two symbols, twice as many new values per extra square — and found the yield, the share of positions of a given size carrying a value nothing smaller carries, spanning two orders of magnitude instead. It closed on the question a falling sequence always raises:

Toppling Dominoes is the case to run, because its yield has fallen from one to a half over eight sizes and has fallen much less than the others; two or three more sizes would say whether it is heading for a floor or merely falling slowly.

Four more sizes say it is heading for a floor, the floor is one half, and the reason turns out to have nothing to do with values running out.

Four more sizes #

The sweep runs over every row of at most twelve dominoes — 8,190 rows, 4,096 of them at the top size — with each row’s value computed by the ordinary recursion and reduced to canonical form before being compared with everything seen at a smaller size.

Two decisions inside that sentence do most of the work, and both were made on the rung below rather than here. New means not equal to the value of any smaller row, where equal means equal as games — so a row counts as fresh only if nothing shorter is interchangeable with it in every sum whatsoever. And the comparison is over all smaller sizes at once rather than against the size immediately below, so a value that skipped a size and came back is caught. Both make the yield a harder number to score well on than the obvious alternatives, which is why it was the quantity the rung below kept when the excess turned out to be an artefact.

The yields come out as

$$1, \ \tfrac34, \ \tfrac34, \ \tfrac58, \ \tfrac58, \ \tfrac9{16}, \ \tfrac9{16}, \ 0{\cdot}5273, \ 0{\cdot}5313, \ 0{\cdot}5146, \ 0{\cdot}5156, \ 0{\cdot}5076$$

which is a sequence that has visibly stopped going anywhere in particular and has started sitting just above a half.

The distance above a half is the reading that separates the two hypotheses. It goes $\tfrac12, \tfrac14, \tfrac14, \tfrac18, \tfrac18, \tfrac1{16}, \tfrac1{16}, \dots$ — halving every two sizes, with the ratio between distances two sizes apart sitting at $0{\cdot}500$ nine times in ten and within three per cent of it on the other two.

A sequence still falling has no such structure; a sequence approaching a limit geometrically has exactly this one. So the answer to the rung below’s question is that the yield tends to a half, and the interesting work is the second question, which the rung below did not think to ask: why a half?

The half is a symmetry #

The obvious reading of a yield tending to a positive number is that the ruleset keeps producing new values forever, at a fixed proportion of its positions. That reading is right and it is not the mechanism. The mechanism is much simpler, and it is a fact about the rules rather than about the values.

A Toppling Dominoes row played from the other end is the same game. The rules name no end of the row — either player may topple one of their own dominoes leftwards or rightwards, and everything it falls on goes with it — so reversing a row is a relabelling and not a change of position. A row and its mirror image are equal games, and this is a statement about the rules rather than a measurement.

That halves the ceiling at a stroke. Of the $2^n$ rows of $n$ dominoes, the reversal classes number

$$\frac{2^n + 2^{\lceil n/2 \rceil}}{2}$$

— half the rows, plus half the palindromes back, since a palindrome is its own mirror. No census of rows can find more distinct values than that, whatever the ruleset does, and the ratio of that expression to $2^n$ tends to exactly one half.

The parity that runs through the yields is the same expression showing through. An odd size has as many palindromes as the even size below it — a palindrome of odd length is fixed by its middle domino and free elsewhere — so the ceiling steps down every second size rather than every size, and the yields come in equal pairs.

And the ruleset sits on the ceiling #

A ceiling explains why the yield cannot exceed a half. It does not explain why the yield reaches it, and that is a separate measurement with a stronger result.

At every size to twelve the number of distinct values is exactly the number of reversal classes. 136 at eight dominoes, 272 at nine, 2,080 at twelve. Not one pair of rows that are not each other’s mirror image shares a value, anywhere in 8,190 rows.

So the value map is as injective as the symmetry allows it to be. Toppling Dominoes is not merely producing new values at a fixed rate — it is producing every value it possibly could, given that half its positions are duplicates of the other half by construction.

That is a much stronger statement than the yield’s limit, and it is the one that answers what the rung below was really asking. A yield tending to a positive number could have meant a ruleset producing a constant fraction of new values with the rest genuinely colliding. Here nothing collides. The half is the mirror and nothing else.

Topple it from either end is where the game arrives on this site and where the reversal symmetry is first used as a convenience; it is worth reading beside a page where the same symmetry turns out to set the ceiling on what a whole census can count.

The three that come back #

Injectivity within a size is not quite the whole yield. A value can also be new-looking within its size and already have appeared at a smaller one, and three of them do.

$\ast 2$ arrives at four dominoes as LRLR and comes back at eight as LRRLRLLR. $\ast 3$ arrives at six and returns at ten; $\ast 4$ at eight and returns at twelve. Three values in 8,190 rows, and they are the same phenomenon three times.

The alternating row of $2m$ dominoes is worth $\ast m$ — the position where every domino is flanked by the other colour, so every move leaves an alternating row again, which is the shape a nimber has. The returning row is that row with LR wrapped round it at both ends: four dominoes added, and the value unchanged. Whatever those four dominoes do, they cancel, and they are the only construction in this family that adds material and changes nothing.

It is worth being precise about how small this is. Across the whole sweep the yield falls short of its ceiling by exactly one value at eight, ten and twelve dominoes and by nothing at all at every other size. If the three returning rows were removed from the census the yield would be the ratio of reversal classes to rows, exactly, at every size — a closed form rather than a measurement. The measured sequence and the closed form differ in the fourth decimal place.

That the leakage is entirely nimbers is worth a sentence. A nimber is the value a position has when neither player gains by moving there, and where the impartial theory stops is the account of why partizan rulesets keep producing them anyway. Here they are the one place a partizan ruleset repeats itself: the values that are not about the difference between the two players are the ones two different rows can both have.

Where the game came from #

Toppling Dominoes is from Lessons in Play, where it is the standard first example of a partizan ruleset whose positions are strings — a row of dominoes, blue ones Left may topple and red ones Right may, each falling leftwards or rightwards and taking everything in its path. It is chosen for teaching because the positions are trivial to write down and the values are not trivial at all, and because a reader can be shown a five-domino row and asked to find the winner before any theory is introduced.

That pedigree matters for what this page measures. A ruleset invented as an example has no reason to be economical with its values, and no reason to be prolific either; nobody designed it to hit its own ceiling. So the injectivity found here is a property the rules happen to have rather than one they were given, which makes it the kind of fact worth measuring rather than assuming — and it is the reason this ladder measures rulesets against each other instead of reasoning about them.

It also explains why the game is the affordable one. Its positions are written over two symbols where Push, Shove, Clobber and Toads and Frogs all need three, so a size that costs four thousand positions here costs half a million there. The rung below chose it for the extension on exactly that arithmetic, and the arithmetic is why this page has twelve sizes and the others have eight.

What a floor at a half means #

The rung below named the stakes precisely: a yield tending to nought would mean a ruleset with finitely many values, and a yield tending to a positive number would mean one whose value space grows as fast as its position space forever. It is the second.

That is a statement about saturation, and it is worth being careful about which kind. This site runs to saturation in the sense of running out of distinct arguments; a ruleset saturates in a different sense, by running out of distinct values. Toppling Dominoes does not, and now has a reason not to: it grows at half the rate of $2^n$, and the half is the mirror.

Read beside the values nobody’s game produces, which measured how much of the value space the games decline to use, this sharpens into something slightly odd. A ruleset can be prolific and parochial at once. Toppling Dominoes produces a new value for essentially every position it has, and the values it produces are still a vanishing corner of everything a game can be worth — because $2^{n}/2$ new values per size is fast against the positions and slow against the birthdays, where the count of values born by day $n$ grows like a tower.

What injectivity buys a reader #

A ruleset whose value map is injective on its symmetry classes is unusual enough to be worth stating as a property rather than as a statistic, because it changes what a position is.

If two rows can share a value, then knowing a row’s value is strictly less information than knowing the row. If they cannot — and to twelve dominoes they cannot, bar three nimbers — then the value is a complete description: a twelve-domino row and its mirror can be reconstructed from what the row is worth, at least in principle. That is a very strong statement about a game whose positions are 4,096 strings and whose values are arbitrary partizan games, and it is exactly the kind of statement that stops being true as soon as a ruleset has two ways of doing the same thing.

Compare Hackenbush is a numeral, where the value is the position read as a binary numeral and injectivity is not a measurement but a restatement of the reading. Toppling Dominoes has no such reading — nobody can look at LRRLRLLR and say what it is worth — and it is injective anyway. Those are two quite different reasons for a yield of one, and the census cannot tell them apart, which is why the rung below found the two Hackenbushes and this ruleset sitting in the same part of its table for different reasons.

What this does not settle #

It is one ruleset. The rung below measured seven and this page takes one of them four sizes further, because it is the one whose yield had not clearly resolved. The other six still have yields measured over eight sizes, and two of them — the Hackenbushes — have yields of exactly one that are known to break, at eight edges in the green case. Whether a ruleset with a falling yield has a floor of its own is untouched here. Toads and Frogs is the case to want, and it is written over three symbols, so the size that would settle it is nineteen thousand positions rather than four thousand.

The reversal symmetry is checked and not proved here. All 992 mirror pairs at ten dominoes agree, which is a check on a claim the rules already make. The argument is a sentence — the rules do not name an end of the row — and this page treats it as an argument with a check under it rather than as a measurement.

And the tables cannot show a value. Every figure here is a count, and a count of distinct values says nothing about which values they are. The one thing a reader might most want to see — the 2,080 different games a twelve-domino row can be worth, and how they sit relative to each other — is not drawable, and no figure on this page pretends otherwise. What is drawn instead is the arithmetic of the census: rows, classes, distinct values, and the one place the three columns disagree. How wide a form can get is where the shape of a value gets looked at directly, and it needs a different instrument entirely.

And the sweep stops where the recursion does. Twelve dominoes is 4,096 rows and about twenty-five seconds; thirteen is twice that, fourteen twice again. Nothing about the method fails at thirteen, and nothing about the finding would change, but the halving ratio would be measured on one more term rather than on eleven.

The conjecture at the end of this page is a conjecture. It fits one measured ruleset and a count of symmetries, and the count of symmetries for the other six has not been made. It is written down because it is cheap to refute and because a ladder is more useful when its next rung is stated than when it is left to be discovered again.

Normal play throughout, and canonical forms compared by name. Two rows count as sharing a value when their canonical forms are the same game, which is equality in every company rather than equality in Toppling Dominoes — a stricter test, and the one that makes a new value mean something outside the ruleset that produced it.

Where the ladder goes next #

The realisability anchor has seven rungs: the cheapest way to show a value, the birthday as a floor, which values no game produces, whether width accounts for the excess, the entry fee that was the cap, what a rate measures, and now what a yield’s fall ends at.

The rung above is the other rulesets’ ceilings. Toppling Dominoes’ floor is its reversal symmetry, and every ruleset here has symmetries of its own: Push and Shove have none that is obvious, Clobber has reversal and colour-swap together, Hackenbush strings have none at all — which is exactly why their yield is one. So the conjecture the sweep suggests is that each ruleset’s yield tends to the reciprocal of its symmetry group’s order, and it is testable without any new machinery: count each ruleset’s symmetries, predict a floor, and measure. A ruleset whose yield settles below its predicted floor would be the first genuine value collision on this ladder, and would be worth more than the conjecture.

Two neighbours are worth the trip. The entry fee was the cap is where a quantity on this ladder turned out to be an artefact of the sweep rather than a property of a ruleset, and it is the standing warning this page had to clear before its own number could be believed. And how long a row a value needs is the same game measured from the other side — which values need how much room — and the two together are the site’s whole account of what a row of dominoes can be worth.