Combinatorial Game Theory
who wins, and by how much
Concept

Shove — where it appears

A strip game in which a coin slides one square along, over any coins in its way, so every coin always has a move while there is room. All its values are cold and readable straight off the board, which makes it the control that Push is measured against.

Named by 7 essays across 2 fields — each of them below, with the objects they name alongside it.

How old a value is, against how big a board it takes to show it. For each birthday, the range of sizes of the smallest position exhibiting a value of that age. The bars do not march rightwards: values born on the last day of the sweep are shown by six-piece positions, and values born on the fourth need up to fifteen.

The cheapest way to show a value

Eleven thousand positions from fifteen rulesets reach 1,193 values, and for each of them there is a smallest board that shows it. Set against the birthday the two measures agree hardly at all — until the numbers are taken out, at which point they agree rather well, and the whole apparent independence turns out to be a fact about integers.

values · Realisability 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.

positions · Push 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.

positions · Push 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.

positions · Push Two orders of magnitude. The share of positions of a size whose value is one no smaller position exhibits. Every Hackenbush string is a new value and fewer than one Clobber row in a hundred is.

The rate was the alphabet

The rung below asked for a quantity a size cap cannot censor and proposed the rate: how many new values a ruleset produces per extra square. The rate is honest and it measures the notation — every ruleset grows at close to the number of symbols its positions are written in, and the seven span less than a factor of two. What separates them is the yield, which spans a hundred and nineteen.

values · Realisability 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.

positions · Push 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.

positions · Push

Named alongside it

The objects these essays reach for when they reach for this one.

EnumerationValuePushInvariantNumberPartizanApproximationCounterexampleDecompositionDisjunctive sumBinaryHackenbush

All concepts