Combinatorial Game Theory
who wins, and by how much
Series

Push — the series

8 essays on one idea, from the one that introduces it to the one that assumes the rest.
  1. Push and Shove over every strip up to 6 squares. The same strips under both rules. A cliff lets coins fall off and a wall does not, and the census says what that one clause is worth: both games are entirely made of numbers, they never agree on a value, and the obvious board-reading is right far more often under the wall than under the cliff.

    The other way to move a row

    Shove has a cliff and Push has a wall, and that is the whole of the difference. Both games make every one of the 728 strips up to six squares a number, so neither ever has anything worth fighting over — and the two rules do not agree on the value of a single position. The obvious board-reading is exact on 446 strips under the wall and on 140 under the cliff, and 486 strips contain a coin its owner cannot move at all.

    part 1 · positions
  2. When counting the free squares gets Push right. Every Push strip of at most seven squares, split by whether any line of play can bring two coins of opposite colour together. Where none can, the count of free squares in front of each coin is the value, without exception; where one can, the count is right more often than not.

    The reading that survives too much

    Counting the empty squares in front of each coin gets a Push position right half the time, and the rung below said the failures were exactly the positions with two coins of opposite colour side by side. Sixty-six of the 1,072 failures have no such pair, the smallest is five squares long, and the condition that does decide it is not about the board at all — it is about every position the board can reach.

    part 2 · positions
  3. Three strips a criterion cannot tell apart. Three Push strips identical in length, reading, coin counts and run structure, whose readings are wrong by a quarter, a half and a quarter more than one. The order of the colours inside the run is the only thing separating them.

    The criterion that cannot exist

    The rung below asked for a quantitative version of its condition — turn 'the reading survives mixing three quarters of the time' into a statement about the strip. Three strips of four squares settle it. `.LLR`, `.LRL` and `.RLL` have the same length, the same reading, the same coins and the same single run, and their readings are wrong by 1¼, ¼ and ½. The error is a fact about the order of the colours, and 207 of 805 statistical classes carry more than one of them.

    part 3 · positions
  4. A numeral in the empty squares. Runs of coins with one to five empty squares in front, and the value of each. Every row is a binary expansion converging on a fraction the colours determine.

    A numeral in the empty squares

    The rung below ruled out a quantitative criterion for Push and asked for a numeral over the coins combined with a count over the gaps. The two ingredients are the right way round: the colours pick a fraction — −1, −1/3, −1/7, −1/15 — and the empty squares give the binary precision, so a run of k coins before one of the other colour with g gaps is worth exactly (1 − 2^(−kg)) ÷ (2^k − 1). And it does not compose: a strip of two runs is not the sum of them, on any pair tried.

    part 4 · positions
  5. Moving them apart does not make them independent. The value of a two-run Push strip as the gap between the runs widens. Each row converges, and none of them converges to the sum of its two runs.

    The cliff a cut invents

    The rung below asked for a correction term in the gap between two Push runs. There is none, because the gap's contribution vanishes: widen it and the strip's value converges geometrically, at a rate set by the back run's length alone, to a limit that is not the sum. And Shove — whose reading is exact everywhere — fails at the same cut, which says the broken thing is the cut and not the game.

    part 5 · positions
  6. Every gap dies at the last run's rate. Three-run Push strips with each gap widened in turn, and which of four candidate rates the convergence matches. The rearmost run's rate wins every family and the compound rate wins none.

    Read from the back forwards

    The rung below found a two-run Push strip converging at a rate set by the back run and asked what a third run does — whether the rate is still the rearmost run's, or whether the rates compound. It is the rearmost run's, and for every gap: widen the front gap of a three-run strip, two whole runs away, and the value still dies at the last run's rate. Shove, the game one clause away, compounds.

    part 6 · positions
  7. Hold the tail, vary everything in front. The grouping test: every tail against every prefix, asking whether the rate at which a widening gap stops mattering is a function of the tail alone.

    Two strips that end the same way

    If a Push strip's sensitivity is governed by its last run, then two strips agreeing at the far end should behave the same however different their fronts. On 78 of 80 tails they do, exactly. On two of them a single empty square in the prefix reaches across a gap that grows without bound and halves the rate — and the run reading turns out to be sound in one direction only.

    part 7 · positions
  8. The threshold is one whole move. The prefixes grouped by their own value, against the rate they produce behind LRRL. No value class splits, and the boundary falls exactly at one move: three quarters of a move is not enough and one move is, with nothing between them. A fractional advantage does not reach across a gap that grows without bound and a whole move does.

    A fraction does not reach

    Two Push tails read their prefix when every other tail ignores it, and the previous rung guessed the deciding bit was a shape — whether the prefix's last coin stands alone. The full census says it is a number. The rate changes exactly when the prefix is worth a whole move, and three quarters of a move is not enough.

    part 8 · positions

All series