Combinatorial Game Theory
who wins, and by how much
Theme

The thread: A theorem that names no move — page 6

Knowing who wins and knowing what to play are different achievements, and the subject is full of results that supply the first and refuse the second. A bound is sometimes all there is.
Three certificates and the truth. The drawn m,n,k boards up to twenty cells, with whether a pairing exists, the Erdős–Selfridge potential, the exhaustive Maker–Breaker result, and whether a greedy rule based on the potential holds against every line of play. Out in the world

Three ways to know a draw

A draw on a board too large to search has to be certified, and there are two standard certificates: a pairing of cells and the Erdős–Selfridge sum over lines. Set against exhaustive search, both miss 4 × 4, and a rule taken from the sum holds there anyway. The sum looks far stronger until pairs are allowed to serve several lines at once. Then across 440 boards up to 12 × 12, the sum certifies no draw that a pairing does not, and a pairing certifies 36 that the sum cannot.

 A price in stones per turn. Small boards with the exact number of stones Breaker needs per turn to stop a Maker placing one, the rate the biased Erdős–Selfridge potential guarantees, and the number Maker needs per turn to beat a Breaker placing one. Out in the world

A win priced in stones

Change the rate of play and a yes-or-no question becomes a number. Against a Maker placing one stone a turn, Breaker needs two stones to stop three in a row on every board up to 4 × 4 and six by three, and three on 5 × 4. Against a Breaker placing one, a Maker needs two stones on most boards drawn at one, and three to make four in a row on 4 × 3. The extra stone is enough to erase noughts and crosses altogether, and the biased sum is exact there and high everywhere else.

All themes