Combinatorial Game Theory
who wins, and by how much
Concept

Push — where it appears

A strip game in which a coin shoves the whole run of coins in front of it, so a move needs an empty square ahead of the run rather than ahead of the coin. Every value is a number, a single run has an exact numeral whose digits live in the empty squares, and a strip of several runs is not the sum of them.

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

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.

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

EnumerationValueInvariantPartizanShoveApproximationNumberBinaryCounterexampleDisjunctive sumDecompositionHackenbush

All concepts