The other way to move a row

Shove is a strip of squares with a cliff at the left end. Some squares carry a blue coin, some a red one. Left moves a blue coin one square towards the cliff, shoving every coin already to its left one square along with it, and whatever was standing on the edge square falls off and is gone. Right does the same with a red coin. It is a partizan game in which every position is a number, which is a strange enough thing to be worth an essay of its own.

Push is the same strip with a wall where the cliff was.

The wall does not give. A coin moved towards it takes only the contiguous run of coins immediately in front of it, and nothing ever leaves the strip: the move is legal exactly when the square in front of that run is empty. Push it against the wall and it stops. That is one clause, and it changes every value on the board.

The clause, and the coin it strands #

The interesting consequence of the wall is not the arithmetic. It is that a coin can be stuck.

In Shove, every coin of one’s own colour is always movable: the cliff absorbs whatever reaches it and there is always room to shove. In Push, a coin sitting behind a run that is jammed against the wall has nowhere to go, and its owner cannot move it at all — this turn or any later turn, because nothing in the game ever moves a coin away from the wall.

Being stuck is a way of having no move that Shove has no analogue for, and it is what makes the game end. Shove ends because coins fall off the edge and eventually a player owns none; Push ends because coins jam against the wall and eventually a player owns none that can move. The termination condition is met either way and by different mechanisms, and the second one conserves the coins.

Four hundred and eighty-six of the 728 strips have at least one stuck coin somewhere in them. Two thirds of the board positions in this game contain a piece that its owner is simply never going to use.

Every position is still a number #

The first thing to check is whether the strange property survives the change of rule, and it does. All 728 Push positions up to six squares are numbers.

That is not obvious and it is not a restatement of Shove’s version. Being a number means the temperature is $-1$ — that there is nothing at stake, that moving first is never an advantage, and that both players would rather the other had to move. Under Shove the reason is easy to feel: every move is a loss of ground, and the position is a tug-of-war on a fixed axis with no choices in it.

Under Push there are choices. A coin with two empty squares in front of it can be pushed; so can the coin behind it, dragging the first along. Those lead to different positions, and a player has a decision to make. The decision never amounts to a fight.

The reason both games avoid heat is the same and it is worth naming. A position is a number exactly when every incentive is strictly negative — when every move either player has makes their own position worse. In both games every legal move moves a coin towards the wall or cliff, which is towards being stuck or being gone, and there is no move in either game that improves the mover’s standing. A game in which every move is a concession is a game made of numbers, and the two rulesets are two ways of arranging that.

And they never agree #

Zero of 728.

That is the count that surprised the sweep. Two rulesets, identical pictures, identical answer to the question “is this a number?”, and not one strip on which they return the same number.

A few small cases show why the gap is systematic rather than incidental.

A single blue coin on square one — against the wall, at the cliff edge — is worth $1$ under Shove, because Left shoves it over the edge and Right has nothing; and $0$ under Push, because the coin is jammed and Left has no move at all. The very smallest position already differs, and it differs because the wall strands what the cliff consumes.

A blue coin on square two is worth $2$ under Shove and $1$ under Push. In general a lone blue coin $d$ squares from the end is worth $d$ under Shove and $d-1$ under Push, because Shove gets one extra move out of the coin — the one that pushes it off.

That single-coin offset does not survive contact with a second colour. $\mathsf{LR}$ is worth $-\tfrac32$ under Shove and $0$ under Push; $\mathsf{L.R}$ is $-\tfrac52$ and $-1$; $\mathsf{R.LL}$ is $\tfrac{13}2$ and $2$. There is no constant, no scaling and no formula relating the two columns, which is exactly what one would expect of two games that happen to share a picture.

What can be read off the board #

Both games invite the same wrong guess, and the guess is much better under the wall.

Under Shove the natural reading is that a coin $d$ squares from the cliff is worth $\pm d$ and the position is the sum. It is exact on all 126 single-colour strips and right on 14 of the other 602.

Under Push the natural reading is different, because the quantity a coin owns is the room in front of it. A coin cannot pass another, so the run of coins ending at a given square has exactly the free squares in front of it to travel over, and counting those signed by colour is the obvious guess.

It is exact on all 126 single-colour strips and right on 320 of the other 602 — better than one time in two, against Shove’s one time in forty-three.

The reason the wall’s reading is better is that under Push, a coin’s travel is genuinely a local quantity most of the time. What breaks it is a run: when coins of both colours end up adjacent, pushing one moves the other, and a player’s move spends the opponent’s room as well as their own. Under Shove, every move moves every coin to the left of it, so interaction is not an occasional complication — it is the rule.

The fractions, and where they come from #

A number in a partizan game is a dyadic rational, and the denominators say how deep the position’s decisions run. Under Push the 728 positions produce these:

446 integers, 90 halves, 90 quarters, 56 eighths, 36 sixteenths, 6 thirty-seconds and 4 sixty-fourths.

Sixty-fourths, on a strip of six squares. A denominator of $2^6$ means a value produced by the simplicity rule applied six levels deep — that the position sits in an interval so narrow that no simpler number fits in it — and it means the strip has six nested decisions in it that all bear on the answer.

Three fifths of the positions are integers, and those are mostly the strips where one colour has no coin able to reach the other. The fractions arrive exactly where the two colours are close enough to interfere.

The seven counts are worth reading as a ladder rather than as seven separate figures, because every rung of it is occupied. There are strips worth a half, strips worth a quarter, strips worth an eighth and so on with no gap anywhere up to the sixty-fourth — so the depths the simplicity rule reaches on this board are a continuous range rather than a scatter, and the question of which strips sit at the bottom of it has an answer.

That the deepest strips all have that shape is the useful part. A run of one colour is what gives a player a long series of forced concessions; the single opposing coin behind it is what makes each concession a decision rather than a formality; and the empty squares at the wall are the room the whole exchange happens in. Take away any of the three and the value is shallower.

A third rule at the same edge #

There is a variant between the two and it is the one the Shove essay warned about without computing.

Keep the full shove — the moved coin takes every coin to its left along, as under the cliff — and simply forbid the move whenever the edge square is occupied. Nothing falls off, and nothing has a run of its own to move within: one coin sitting against the wall freezes the entire strip for both players.

That rule is harsher than either of the others and it is the only one of the three whose values are not all numbers.

The stars have an exact description. A position with a gap at the wall and one coin of each colour able to reach it gives both players a move to the same place, and a position in which each player has exactly one option and the two coincide is $\ast$ — the smallest thing that is not a number, and a tie.

So the middle rule is where the arithmetic of the strip first breaks. Neither the cliff nor the run-only wall ever produces a value that is not a number; the whole-row wall does, 140 times in 728, and it does it by manufacturing symmetry.

What none of the three ever produces is a fight. All 728 positions under all three rules have temperature at most zero, so there is never a move worth making, and the sign of the value — or the presence of a star — is the whole of the outcome.

The three row games, side by side #

This site now carries three partizan games played on a row of blue and red pieces, and between them they cover the possible answers.

Hackenbush strings — every position a number, and the number is legible: read the colours from the ground upward and the binary expansion falls out.

Shove and Push — every position a number, and the number is not legible. Push’s board-reading is right about half the time and Shove’s is right about two per cent of the time, and neither is a numeral. The whole-row wall above sits with them and is the only one of the three that ever produces a star.

Toppling Dominoes — hardly any position a number at all: 30 of 510, with a temperature that grows without bound as the row lengthens.

What separates the two halves of that list is a single structural fact: whether a move can ever improve the mover’s position. In the first three games it cannot, so every incentive is negative and every value is a number. In Toppling Dominoes a move can clear the opponent’s whole side of the board, which is an improvement, and the moment that is available the temperature is positive.

So the boundary between a cold game and a hot one is not about the pieces, the board or the shape of the move. It is about whether the rules ever hand the mover something worth having.

What the picture cannot show #

The strip does not say which game it is. Neither does it say where the boundary is: a cliff and a wall are both drawn as a line at the left end, and no drawing convention distinguishes “everything past here is gone” from “nothing goes past here”.

That is the same warning Toppling Dominoes carries against Hackenbush and it is worth repeating because it is the site’s most common trap. A picture of a position is a picture of a position. The ruleset is not in it, and two rulesets on one picture can differ on every value while agreeing on every structural property a reader would think to check.

The second thing the picture cannot show is which coins are stuck, unless the reader traces the runs. A red coin against the wall with three blue coins behind it looks exactly like a red coin with room, and the difference is the difference between a piece and a wall.

The convention, and the honest bound #

Everything above is normal play: a player with no legal move loses. Under misère play a player with no legal move wins, and a game two thirds of whose positions contain a stuck coin is a game in which running out of moves is a thing a player can engineer. Nothing here says what happens to Push under that convention, and there is no reason to expect the numbers to survive — misère play has no negatives and therefore no numbers either.

The sweep is six squares. Six is the size at which the position count is 728 and the evaluation is instant; seven is 2,186 and still cheap; the claims above would survive being re-run at either. What they are is claims about short strips, and “every position is a number” is the kind of claim that would be worth a proof rather than a census, because a census cannot rule out a first exception at eleven squares.

The outcome, read off the sign #

Because every position is a number, the whole outcome theory of both games collapses to one sentence: the sign of the value is the winner. A positive number is a Left win whoever moves, a negative one a Right win, zero is a second-player win, and there are no first-player wins anywhere in either game — which is what having no positive incentives buys.

Shove has a rule a player can apply at a glance on top of that: the winner is the owner of the coin furthest from the cliff, in all 728 positions, whatever stands between it and the edge.

Push almost has the same rule and not quite. The owner of the coin furthest from the wall never loses — the sign is never wrong, over all 728 — but 126 of the positions are worth exactly zero, and in those nobody wins by moving first.

Those 126 are not scattered. They are exactly the fully packed strips: every square from the wall outward occupied, with no gap anywhere. A packed strip has no legal move for either player, because every coin’s run runs straight into the wall, so it is over before it starts and is worth nothing. There are $2 + 4 + 8 + 16 + 32 + 64 = 126$ of them up to six squares, which is the count, and the two lists agree position for position.

So the difference in the outcome rules is the difference between a game whose positions are all decisive and a game with a supply of dead ones. Under the cliff a coin is always spendable and somebody is always ahead; under the wall the board can fill up, and a filled board is a draw in the only sense normal play has one.

Who described them, and together #

Push and Shove are a pair in Winning Ways, introduced side by side precisely because the contrast is the lesson: two games whose rules differ by a clause about the boundary, with different values throughout. Shove is the one that gets the attention, because “every position is a number” is the more quotable fact and because its values have a clean description.

The pairing is a specimen of something the whole subject does. A ruleset is not a picture and it is not a mechanism; it is a complete specification, and the parts of it a designer would call incidental — what happens at the edge, whether a piece is removed or blocked, whether a move takes one neighbour or all of them — are exactly the parts the values depend on. Two games that a player would describe in the same sentence can share nothing.

Where the ladder goes next #

The first rung out is the closed form. Both games have one for a single colour and neither has one written down for two, and the Push reading being right 320 times in 602 is the sort of hit rate that suggests a repairable rule rather than a hopeless one. What the 282 failures have in common is the obvious thing to look at, and they are all positions with adjacent coins of opposite colours.

The second is the stuck coin as an object in its own right. A position with a stuck coin is a position with a piece that cannot participate, which is a kind of zugzwang frozen into the board rather than arising in play, and the count of stuck coins is a number that only goes up. A game with a monotone quantity in it is a game with a termination proof, and Push’s is nicer than Shove’s.

And the third is the sum. Both games are made of numbers, so a sum of strips is an addition rather than a search, and the whole board can be evaluated by adding the parts — which is the one thing a game of numbers is good for and the reason the theory bothers to name them.