How long a row a value needs

Topple it from either end evaluated every row of blue and red dominoes up to eight long and closed by naming the colour it had left out:

The first rung out is green: the third colour, the universality construction, and the question of how long a row a given value needs. That is a measure of a value’s complexity in a currency a reader can hold, and it should agree with the birthday sometimes and not others.

A green domino may be toppled by either player. It is the analogue of a green Hackenbush edge — a move belonging to whoever wants it — and adding it changes the game’s reach completely. The rule is otherwise untouched: a topple still removes the chosen domino and everything on one side of it, and every option is still a contiguous piece of the row.

Seven dominoes in two colours are 128 rows carrying 149 values. Seven dominoes in three colours are 2,187 rows carrying 1,047.

That ratio is what makes the rest of this page possible. A game reaching a hundred and fifty values has a length measure with very little in it — most values are unreachable, and the ones that are reachable are reachable early. A game reaching a thousand has a length measure worth plotting against something.

What green is doing #

A blue domino is a move for Left and a red one is a move for Right, so a two-colour row is a supply of territory: each player’s moves are counted in their own dominoes and the values that result are overwhelmingly numbers.

A green domino is a move for whichever player wants it, so a row of them is a supply of tempo. It is exactly the resource an infinitesimal is made of, and it is why the third colour reaches values no two-colour row is worth.

The connection to Hackenbush is exact and is the reason green was worth trying. Squash every loop to a point shows that green Hackenbush is impartial and gives nimbers; the blue-red string that spells its own value shows that blue and red give numbers. A row of dominoes in all three colours is the mixed case in one dimension, and the values it produces are neither numbers nor nimbers.

The measure the rung below asked for #

With 1,047 values available, each one has a shortest row worth it, and that length is a measure of the value’s complexity in a currency anybody can check: how many dominoes it takes to write the value down as a position.

Two things come out of the table, and only the second was in doubt.

A row of $n$ dominoes is worth a value born by day $n$. Every option of a row is a shorter row, so the recursion has at most $n$ levels under it, and the value’s birthday is at most $n$. So the shortest row worth a value can never be shorter than that value’s birthday, and on all 1,047 it is not. That is asserted in the code rather than reported.

The bound is loose, and much looser than a reader would guess. A value born on day three can need seven dominoes. The worst case here is $1\!\uparrow$ — a one and an up added together — born on day three and needing the seven-domino row $\mathrm{LLRLRLL}$.

The value that costs the most #

$1\!\uparrow$ is worth pausing on because the reason it is expensive is visible.

An up needs a tempo structure: a position where one player has a move the other cannot answer in kind. In a row of dominoes that means an arrangement of colours which leaves Left with a spare topple, and the shortest such arrangement is not short. A one needs a blue domino nobody can reach. Getting both into one row means getting them into one row without the two interfering, and a topple removes everything on one side — so the two structures cannot be laid end to end without one of them destroying the other when it fires.

By contrast, a value born on day seven is available in seven dominoes — thirty-three of them are, and every one of them has to be, since a row of seven cannot carry a value born later. The deep values are cheap relative to their day and the shallow ones are not, which is the opposite of what a reader expects a complexity measure to do.

The ten worst offenders are all born on day three and all need seven dominoes, and reading their names together says what they have in common: $1\!\uparrow$, $1\!\downarrow$, $\{2 \mid 1\ast\}$, $\{2 \mid \downarrow\}$, $\{1 \mid \{1 \mid -1\}\}$. Every one of them is a number added to something small, or a switch with a follow-up on one side only — and both shapes need a piece of the row that produces the number and a separate piece that produces the small thing, without either being swept away when the other fires.

The two structures cannot overlap and cannot be adjacent, so the row has to be long enough to hold both with room between them. That is the whole mechanism, and it is a fact about how a topple reaches past the domino it starts at.

Why the two measures come apart #

The birthday counts levels of the canonical form. The row length counts dominoes in a position. Those are different objects, and what a value costs to write down makes the same point about symbols: a value’s canonical form is minimal in options and is not minimal in anything else.

Here the divergence has a specific cause. A row of $n$ dominoes has $\tfrac{n(n+1)}{2} + 1$ distinct positions under it at most — every option is a contiguous substring — so the shape of the game tree a row produces is heavily constrained. A value whose canonical form does not fit that shape has to be reached the long way round, by a row whose extra dominoes exist to produce a tree the value can hide inside.

So the length is measuring something the birthday cannot: how well a value fits the particular game. That is a fact about Toppling Dominoes and not about the value, which is exactly why it is worth having as a second measure rather than as a substitute for the first.

It is also the measure a reader can check. A birthday is the answer to a computation nobody can do by eye; a shortest row is a string of seven letters, and anybody willing to spend ten minutes can confirm that no shorter one works. That is the currency the rung below was asking for, and cheapness of verification is the whole of its value.

The values nobody’s game produces is the census of that across every ruleset here, and it closed by asking for exactly this quantity: “for each realised value, the smallest position of any ruleset producing it, and the growth of that size against the value’s birthday.” This page answers it for one game.

What the growth says #

Sorting the 1,047 values by the shortest row that reaches them gives 3, 5, 14, 30, 88, 224 and 683 — so two thirds of everything reachable at all needs the full seven dominoes, and the supply of cheap values runs out long before the supply of values does.

The value counts by length are 3, 8, 22, 52, 140, 364, 1,047. The row counts are 3, 9, 27, 81, 243, 729, 2,187 — powers of three, since each domino has three colours.

So the ratio of values to rows runs 1.00, 0.89, 0.81, 0.64, 0.58, 0.50, 0.48. It falls, and it falls slowly. Half of all seven-domino rows carry a value no other seven-domino row carries.

That is a much higher rate of distinctness than the two-colour game manages — 149 values from 128 rows is more values than rows, because the count is cumulative over lengths — and it is what makes the length measure meaningful. A game where every row was worth the same handful of values would give a length measure with nothing in it.

The smallest green rows #

The values arrive immediately, and running the first few by hand is the quickest way to see why the third colour is not a small addition.

A single green domino is worth $\ast$: whoever topples it wins, and there is nothing left. Two greens are worth $\ast 2$, three are worth $\ast 3$, and the pattern is exact — a row of $n$ greens is a Nim heap of $n$. The reason is that toppling the $i$-th green from either end leaves a row of some shorter length, and every shorter length is reachable, which is the move rule of a Nim heap written in dominoes.

Mix the colours and the nimbers stop at once. $\mathrm{LG}$ is worth $\{1 \mid 0\}$ — a switch, not a nimber and not a number — because Left toppling the green leaves a blue domino worth one and Right toppling it leaves the same blue domino, while Left toppling the blue leaves the green. Two dominoes and the game is already hot, which no two-colour row of length two manages.

$\mathrm{LGR}$ is worth $\{1 \mid -1\}$, the widest switch born on day two, in three dominoes.

The nimbers, by contrast, are the cheapest family in the game and the only one with a formula: $\ast n$ is a row of $n$ greens and nothing shorter, so seven of them are reachable here and the eighth needs eight dominoes. The numbers are nearly as cheap — twenty-six of them appear, with $\pm n$ as a run of $n$ same-coloured dominoes and $\pm\tfrac12$ as $\mathrm{LRL}$ and $\mathrm{RLR}$. The green in the middle is the whole reason: it is a move both players want, and a position both players want to move in is what a switch is.

By length three, three colours reach twenty-two values against eleven for two colours; by length seven the counts are 1,047 and 149. The gap is not a slow drift — it opens at the second domino and widens by a factor at every step.

Two colours, for comparison #

It is worth putting the two-colour numbers next to the three-colour ones, because the contrast is what makes green a change of kind rather than of degree.

Two colours give 149 distinct values in rows of up to seven, and the rung below established what they are: overwhelmingly numbers, with a scattering of switches and a star wherever the two colours meet at the ends. The game is about territory, and the value of a row is very nearly readable off the string.

Three colours give 1,047, and the extra 898 are not more of the same. They are the values that need a move belonging to nobody — the ups and downs, the switches with follow-ups, the sums of a number and an infinitesimal. Adding one colour to the alphabet takes the game from a family of positions the theory calls cold to a family that needs the whole apparatus.

That is the same jump green Hackenbush makes in the other picture, and it happens for the same reason: a move either player can take is what a tempo is, and every value that is not a number is a statement about tempo.

The other lower bound, and why it is no help either #

The birthday is one lower bound on how long a row a value needs. The rules supply a second, and it is worth working out because the two together are everything the game hands over for free — and neither of them explains the seven.

A row of $n$ dominoes has a bounded number of options. Toppling the domino in position $i$ leaves either the prefix before it or the suffix after it, so every option of the row is one of the $n-1$ proper prefixes or one of the $n-1$ proper suffixes. Left may topple only blue and green dominoes and Right only red and green, so each player has at most $2(n-1)$ options and after canonicalisation at most that many survive.

So a value whose canonical form is $w$ options wide needs a row of at least $w/2 + 1$ dominoes, whatever its birthday. That is a genuine second constraint and it is the one a reader who has met how wide a form can get would reach for, since width is the measure the birthday demonstrably fails to bound.

It is also nearly useless here, and the worst case says why. $1\!\uparrow$ is worth $\{1 \mid 1\ast\}$ — one option a side, width two — so the width bound asks for a row of two dominoes and the census finds it needs seven. The birthday bound asks for four. The truth is seven, and both bounds are looking at the value while the answer is about the string.

That is the honest state of the question this page leaves. Two lower bounds are available and both are read off the value; the quantity that actually decides is how many toppling positions a string has to carry to produce those options in the right relation to one another, and it is a fact about arrangements of three colours rather than about the value at all.

What the census cannot reach #

Seven dominoes is where this stops, and the reason is the enumeration rather than the evaluation: $3^8$ is 6,561 rows and $3^{10}$ is 59,049, each needing a full canonicalisation. The values reachable in eight or more dominoes are not here, so every “shortest row” above is shortest among rows of at most seven, and a value absent from the table might be reachable in eight.

That matters for the headline. $1\!\uparrow$ needs seven dominoes among rows of at most seven; it is the worst case found and not provably the worst case there is. A wider sweep could only make the gap between length and birthday larger, since it can only add values that are expensive.

The second limit is that this is one ruleset. The length measure is a property of Toppling Dominoes, and a value cheap here may be dear in Domineering and the reverse. A cross-ruleset version of the same measurement is the one the values nobody’s game produces asked for, and it needs every ruleset’s census rather than one.

The convention, named #

Normal play: the player unable to topple anything loses. A topple removes the chosen domino and everything on one side of it, chosen by the toppler, so a row’s options are its proper prefixes and suffixes and nothing else.

Green is the third colour and belongs to both players, which is the same convention green Hackenbush uses. Every value quoted was computed by the recursion in this site’s evaluator and reduced to canonical form; the birthdays are the depths of those forms, and a form’s depth is the value’s birthday exactly because the form is canonical.

Where the ladder goes next #

toppling-dominoes has two rungs: the game and its two-colour values, and now the third colour with the cost measure it makes possible.

The rung above is the universality claim itself. The count of 1,047 values in seven dominoes suggests that every short game is a row of some length, which is what universality would mean here — and proving it needs a construction rather than a census: a recipe that turns a canonical form into a row, with a bound on the length. The measurement above says such a bound cannot be the birthday.

Two neighbours are worth the trip. What a value costs to write down is the same question asked of notation rather than of a game, where the birthday is again the measure that fails. And the values nobody’s game produces is the census across rulesets, where the question of which values any game reaches is asked of the whole collection.