A numeral in the empty squares

Push is Shove with one clause changed: a coin shoves the whole run in front of it rather than sliding alone, so a player can move a coin only if the run it heads has an empty square in front of it. Nothing worth fighting over established that Shove’s values are read straight off the board — count the free squares each coin can travel over, signed by colour — and the criterion that cannot exist established that Push’s are not, ruling out every criterion built from lengths, colours and run structure.

That page closed on the object a repaired reading would need:

The rung above is the numeral. The errors depend on the order of the colours inside a run, that is the signature of a binary expansion … What a repaired reading would have to do is combine a numeral over the coins with a count over the empty squares — and the two are different kinds of quantity, so the interesting question is whether they combine at all or whether Push has no reading of any kind.

The numeral is real, the two ingredients are the other way round, and it does not compose.

The formula #

For a strip of $g$ empty squares followed by $k$ coins of one colour and then one of the other, the value is exactly

$$-\frac{1 - 2^{-kg}}{2^{k} - 1},$$

signed the other way for the mirrored colours. Checked against the game recursion on every $k$ up to four and every $g$ up to five, in both colours — forty strips, no exceptions.

So .LR is $-\tfrac12$, ..LR is $-\tfrac34$, ...LR is $-\tfrac78$: a binary expansion converging on $-1$. And .LLR is $-\tfrac14$, ..LLR is $-\tfrac{5}{16}$, ...LLR is $-\tfrac{21}{64}$: an expansion in base four converging on $-\tfrac13$.

What each half of the position decides #

The two ingredients divide cleanly, and not as the rung below guessed:

• the colours pick a rational number — $-1$ for LR, $-\tfrac13$ for LLR, $-\tfrac17$ for LLLR, $-\tfrac1{15}$ for LLLLR;
• the empty squares pick the precision — each extra gap multiplies the remaining shortfall by $2^{-k}$, so $g$ gaps give $kg$ binary places.

That is a numeral, and it is a numeral in the gaps: the count of empty squares is not a quantity to be added to anything, it is the number of digits. The rung below expected a numeral over the coins and a count over the gaps, and the coins turn out to supply the fraction while the gaps supply the expansion.

The formula is checked rather than derived, and the check is the site’s usual one: the left-hand column is the game recursion over positions, the right-hand column is arithmetic on two integers, and nothing in the code makes them agree. Forty strips, both colours, no exceptions.

The mechanism is visible in one move. A push moves the whole run one square left, spending one gap; the position afterwards is the same run with $g - 1$ gaps. So the game is a chain of positions differing only in a counter, which is exactly the shape a binary expansion has — each move resolves one more digit — and the limit is what the position tends to when the gaps are inexhaustible.

The resemblance to Hackenbush is not an accident of notation. A Hackenbush string is a binary numeral for the same reason: each edge cut resolves one digit of the value, and the colours say which way. What is different here is that the digits live in the empty squares rather than in the pieces.

Two coins, by hand #

The smallest case is worth doing by hand, because the recursion is three lines and the answer is the whole pattern in miniature.

Take .LR: one empty square, then a Left coin, then a Right coin.

Left pushes the Left coin into the gap and leaves L.R — the Left coin at the wall, a gap, the Right coin. That position is worth $-1$: Left has nothing left to push, Right can push once, and a position where only Right can move once is worth $-1$.

Right pushes too, and Right’s run is the whole block LR, so both coins move left together and the strip becomes LR — worth nought, since neither player can move at all.

So .LR is $\{-1 \mid 0\}$, and the simplicity rule gives the simplest number strictly between: $-\tfrac12$.

That is the digit. Each further gap gives Right one more push before the wall, and each one halves what is left of the difference.

And it does not compose #

A strip with two runs is not worth the sum of its runs’ values. .LL.RR is worth $-2\tfrac12$ and its two runs are worth $2$ and $-2$; ..L.R is worth $-1$ and its runs are worth $2$ and $-1$. Six splits, six disagreements, and the errors are large rather than marginal: the sum of the parts is out by two and a half on one of them, which is more than either part is worth.

The reason is the clause that makes Push Push. A run’s gaps are shared with whatever stands behind it. When the front run is pushed it moves into its gap, and the run behind it now has one more empty square in front — so the second run’s numeral changes when the first one moves, and the two are not independent games at all.

There is a smaller observation in the same table that sharpens it. The disagreement is not even in the right direction consistently — .LR..RL is worth more than its parts and .LL.RR less — so no fixed correction, and no correction of a fixed sign, could repair the split. That is what rules out the easy repairs before they are tried.

That is the honest answer to the rung below’s question, and it is the stronger of the two outcomes it offered. Push has a reading — an exact closed form — for a single run, and no reading for a strip, because a strip is not a sum of its runs in any sense the value respects.

Against the count #

The rung below’s count reading — free squares in front of each coin, signed — gets 2,724 of 6,560 number-valued strips exactly right, which is 41.5 per cent. The numeral gets all forty strips of its family right and says nothing about the rest.

That is the trade, and it is worth naming because this site keeps meeting it. One reading is nearly right everywhere and wrong in a way nobody can characterise; the other is exactly right on a class and silent elsewhere. A player wants the first and a theory wants the second, and Push is a game where the two do not meet in the middle.

The same trade appears in the packing count on a Domineering region, where a band replaces a point estimate, and in the stop reading for a switch, where an exact condition replaces a hit rate. In each case the exact statement covers less ground than the approximate one, and in each case the exact statement is the one that composes into an argument.

Except here, where it does not compose either.

What Push turns out to be #

Reading the three rungs together gives a clear picture of a game that resists every reading in a specific way.

Every value is a number, so Push is cold everywhere and there is never anything to fight over — the same as Shove, and for the same reason: the players’ moves are independent of each other’s colours.

A single run is a numeral, exactly, with the colours choosing a fraction and the gaps a precision.

And a strip is not the sum of its runs, so nothing extends the numeral to a board — not a correction term, not a weighting, nothing that has been tried. The failure is not in the reading, it is in the game: Push does not decompose.

That last sentence is what makes the whole ladder worthwhile. The board falls apart is the standing reason a partizan game is tractable at all — components are independent and their values add — and Push is a game where a natural-looking decomposition into runs is not a decomposition. There is no theorem being broken, because runs were never components; what is broken is the expectation.

What a player can use #

Two readings for somebody at a strip, and the second is the surprising one.

A single run is exactly readable, and the reading is short: count the leading coins of one colour, take one over two-to-that-power less one, and knock off the tail according to how many gaps there are. On a strip with one run that is the whole answer, no search required.

And the value barely moves after three gaps. The expansion converges geometrically, so ...LR at $-\tfrac78$ and ....LR at $-\tfrac{15}{16}$ differ by a sixteenth — which means a player looking at a long empty stretch in front of a run can read the limit and stop counting. That is unusual: most readings on this site get harder as a position grows, and this one gets easier, because the digits it is spending are worth exponentially less.

The catch is the one the previous section is about. As soon as there is a second run, neither reading applies, and the honest instruction is to evaluate.

Who reads a board as a number #

Reading a position as a numeral is Hackenbush’s trick and it is the oldest picture in this subject: a string of coloured edges is a binary expansion, and the value can be read off by anybody who has been shown the rule once. That it works there is a small miracle — most games have values that no reading produces — and the temptation to look for the same thing in every game is exactly what these three rungs have been resisting.

Shove has it. Push, which differs by one clause, does not — and the way it fails is informative rather than dull: the reading exists in miniature and dies at the first sum. A game can be locally readable and globally opaque, and Push is the site’s clearest example.

The general moral is worth carrying because it applies to every reading this collection measures. A reading is a claim about a class of positions, and the class always has an edge; what the three Push rungs add is a game where the edge is one run wide.

What makes a position readable at all #

Push joins a short list of games on this site whose values can be read off the board without evaluating anything, and it is worth asking what the members of that list have in common, because the property is not obvious from any of them alone.

Green Hackenbush is read by fusing cycles and walking a tree. Shove is read by counting free squares. Hackenbush strings are read as binary numerals. And a Push run is read as a numeral in its empty squares. Four rulesets, four different readings, and one shared feature: in each of them, a move consumes a resource whose remaining quantity is visible on the board and is not affected by the opponent’s choices.

That is a strong condition and it explains both the successes and the failures. Where it holds, the value is a function of a count, and a count is what a reader can take by eye. Where it fails — where a move by one player changes how far the other’s next move travels — there is a fight, and a fight is precisely the thing no count expresses.

It also predicts where a readable game stops being readable, which is at the join. Two runs each read perfectly and the strip containing both does not, because the resource one run is counting against is the other run’s coins, which move. So the readability is a property of a component with its boundary rather than of a rule, and joining two readable components can produce something with no reading at all.

Which is the honest place to leave a reading of this kind. It is exact where it applies, the applicability is a geometric condition a reader can check, and the condition fails in exactly the configuration a player is most likely to meet.

What this does not say #

Four limits.

One family. The formula covers runs of one colour followed by a single coin of the other. A run like LRL has values growing with $g$ rather than converging, and nothing here gives them a closed form — though the table shows them approaching $g - 1$ plus a binary expansion, which is the obvious next thing to write down.

The limit is not attained. No Push position is worth exactly $-1$ or $-\tfrac13$; the numerals converge on those and never reach them, which is the ordinary behaviour of a binary expansion and worth stating because the fractions are the memorable part of the result.

Strips of eight. The count reading’s 41.5 per cent is over strips up to eight squares. The share falls as the strips grow, so the number is a favourable one.

Number-valued positions only. Push has non-number values too, and every reading here is about the positions that are numbers. What the numeral does at a position that is not a number is not a question this page asks.

And six splits is not a theorem. A strip is not the sum of its runs is established by six counterexamples, which is enough to refute the composition and not enough to say what the interaction is. Whether the interaction has its own rule — a correction term depending on the gap between two runs — is untested.

The convention, named #

Normal play, Push on a strip: Left pushes a Left coin one square left, taking the whole contiguous run in front of it, and Right pushes a Right coin the same way. A player who cannot push loses. A push needs an empty square in front of the run, so a run against the wall cannot move at all.

A run is a maximal block of adjacent coins, of either colour or mixed; gaps are the empty squares in front of it. Strips are tidied by dropping trailing empty squares, since a square behind every coin can never be used.

The count reading is the rung below’s: for each coin, the number of empty squares between it and the wall that it could still travel over, signed by colour and summed. The numeral is this page’s closed form and is stated for a single run only.

The three rungs together give Push a description worth stating in one line. Every value is a number, one run is a numeral, and a strip is neither — a game that is readable in miniature and opaque as soon as it has two parts.

Where the ladder goes next #

The push anchor has four rungs to here, and the two above take the one thing this page’s reading does not cover: what happens when a strip has more than one run in it.

The cliff a cut invents goes looking for the correction term between two runs and finds there is none, because the thing being corrected is not there. Widen the gap and the strip’s value converges geometrically to a limit that is not the sum of the two runs, at a rate set by the length of the back run alone. And the control settles what is broken: Shove, whose reading is exact everywhere and adds across any genuine sum, fails at the same cut on 89 of the same 93 strips. The cut is what is broken, not the game — a Push strip is a line with a wall at one end, and cutting it hands the back half a wall it never had.

That is the sharpest available statement of what this page’s numeral is a numeral of. It is not a reading of a run; it is a reading of a run against the cliff, and the empty squares are places in the numeral only because the cliff is where they are counted from.

Read from the back forwards then asks what a third run does — whether the rates compound — and the answer is no, at every gap and every distance. Widen the front gap of a three-run strip, two whole runs away from the back, and the value still dies at the rearmost run’s rate. Shove, the game one clause away, compounds, which is what makes the non-compounding a fact about Push’s move rule rather than about strips.

So the information in a Push strip lives at the back. Whatever sits in front of the rearmost run, however far apart, the rate is fixed there — and the numeral this page reads is the one the back run writes.