Combinatorial Game Theory
who wins, and by how much
Generator

A bound that holds, and the hypothesis it needs to

A bound that holds, and the hypothesis it needs to
A bound that holds, and the hypothesis it needs to. Milnor's mean-value bound for scoring games, checked on every pair of coin rows in range. On the left, rows satisfying his hypothesis — there is always a non-negative incentive to move — where the bound holds on every pair. On the right, rows where a player can be forced to take a coin nobody wants, so the hypothesis fails and the bound goes with it. The counts come from playing each sum out exactly.

Milnor's mean-value bound for scoring games, checked on every pair of coin rows in range. On the left, rows satisfying his hypothesis — there is always a non-negative incentive to move — where the bound holds on every pair. On the right, rows where a player can be forced to take a coin nobody wants, so the hypothesis fails and the bound goes with it. The counts come from playing each sum out exactly.

2 essays call milnor-bound. The drawing above is what it returns with no arguments at all; every call below passes it something, because a placement that passes nothing draws whichever member of the family the generator happens to default to rather than the one its essay argues about.

Where it is called

Changing this generator changes every one of these figures.

A game where the last move decides nothing. Rows of coins taken from either end, with the exact score for each side moving first. Under the normal-play convention this family is settled entirely by the parity of the row — nobody is ever without a move until the coins run out — so normal-play theory returns the same answer for every row and it is not the answer anybody wants. The scoring answer depends on nothing but the numbers. Out in the world

Counting at the end changes everything

Go is scored. So are Dots and Boxes, chess and almost everything anybody plays for money — and none of them is the kind of game this site's whole apparatus is built for. The simplest scoring game there is shows what that costs — the normal-play theory gives every position of it the same answer, and the answer is useless.

 The condition has to hold underneath, not on top. Pairs of coin rows sorted by where the incentive condition holds, with Milnor's bound checked on each pair. Rows that satisfy the condition at every subposition never break the bound. Rows that satisfy it only at the top break it on a counted fraction — and a reader who tested the row rather than the row's insides would have called those safe. The distinction is invisible from the position and decides whether the theorem applies to it. Out in the world

A hypothesis has to hold all the way down

Milnor's bound is proved by induction over the play, so the condition it needs has to hold at every position the play can reach. Checked on the row instead, ninety-two pairs pass the test and twenty-four of them break the bound. Checked at every subposition, twenty-eight pairs pass and none breaks it.

The whole library · The position index · The figures that play back