Combinatorial Game Theory
who wins, and by how much
Concept

Integer — where it appears

A whole number as a game value, which is a supply of free moves for one player and nothing else. It is written as a chain, so an integer of size n costs n + 1 symbols and is the cheapest value of its day to write down.

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

Every strip, without the hop. Toads and Frogs with the jump deleted, over every strip up to eight squares. The fourth column is the argument: whenever the value is a number it is a whole number, without exception, so the fractions the ordinary game produces are made by the hop and by nothing else.

The strip where every number is a whole one

Delete the hop from Toads and Frogs and the halves, quarters and ups vanish completely: over 9,801 strips, every value that is a number is an integer, without a single exception. The guess that the hopless game therefore has a formula reading the gaps is half right and exactly wrong — 1,460 strips of eight squares are switches, and three strips with the same counts of toads, frogs and empty squares are worth 1, {2 | 1} and 2.

positions · Toads and Frogs What a value costs to write down. Every one of the 1,474 values born by day three, grouped by the width of its canonical form, with the number of symbols the form takes when it is written out. Each count was obtained by walking the canonical form and counting its nodes, so a subposition appearing twice is counted twice — which is what writing it out does. The widest values of the day are not the longest to write.

What a value costs to write down

The canonical form is the smallest form of its value, and it is smallest in the one currency the reduction happens to spend: options. Counted in symbols it is nothing of the kind — the widest value born by day three is not the longest, the longest has six options rather than seven, and every canonical form on the day except the seven integers writes some position out twice.

values · Reversibility How hot a day gets. The hottest value born by each of the first three days, with every temperature that occurs on it. Day one tops out at nought, day two at one, day three at two — a day buys exactly one degree — and the value attaining the maximum is unique each time. Each temperature was computed as the height at which that value's two thermograph walls meet. The temperatures of day three are exactly the half-gaps between the numbers born by day two, which is what puts a hole in the scale at 7/4.

How hot a day gets

A day of construction buys exactly one degree of temperature — nought, then one, then two — and the value attaining the maximum is unique on every day: ∗, then {1 | −1}, then {2 | −2}. The distribution underneath is not tidy at all: it peaks at a half, leans to the right of the peak, and has a hole in it at one and three quarters where nothing is born.

temperature · Cold What a day of canonical forms costs, written out and written once. Three costs for the values born by each of the first three days: every node written every time it occurs, every distinct subposition of a single form, and every distinct subposition of any form of the day. The last is one node per value, and the gap between the first and the last widens as the construction goes on.

The same position, written once

Writing out the canonical forms of day three takes 24,940 nodes. Naming each distinct subposition once inside each form takes 10,102, and naming each distinct subposition once across the whole day takes exactly 1,474 — one per value, because nothing appears inside a canonical form that is not itself a value of the day.

values · Reversibility What a Domineering region is worth, by size. Every connected shape of at most six free squares, sorted by whether its value is a number, an infinitesimal distance from a number, or hot. Hot shapes do not appear at all until four squares, and the hottest shape of six is the two-by-three rectangle.

Which shapes are worth fighting over

Forty-four of the 104 Domineering regions of at most six squares are worth numbers and the rest are not, and the rung below said no visible property of a shape predicts which. Half of that is wrong: a region only one orientation fits in is a whole number, on all eleven of them, for a reason a reader can supply in a sentence. The other half stands, and thirty-three shapes are what makes it stand.

positions · Domineering 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 Seven, ten, thirteen and sixteen. The four values the rung below named, each read off the prime factorisation: one plus the largest prime plus the product of the two largest.

The size of a cake

Ω gives the sign of a Maundy Cake and says nothing about the size, and the rung below left four values — 7, 10, 13 and 16 — unaccounted for. For a one-row cake they are a formula: write the prime factors largest first and add up their running products. The rule behind it is greedy — cut by the largest prime — and it is exact on every one-row cake to two hundred and wrong on a fifth of the two-sided ones.

positions · Cutcake Still a count of squares. One-sided Amazons regions on two-dimensional boards, swept exhaustively. Every one is worth exactly the number of free squares in it.

A region one player owns

On a strip, a region containing only one player's amazons is worth exactly its free-square count, on all 45,057 positions of the rung below's sweep — and it predicted the exactness would fail in two dimensions, where an amazon can be short of room in one direction and not another. It does not fail. Over 2,412 two-dimensional regions there is no exception, and the reason is one clause: an amazon may shoot back at the square it has just left.

positions · Amazons Cut small unless you are behind. The complete rule for the best cut in a Maundy Cake, in three cases decided by the two sides' counts of prime factors. It is exact on every cake in a sixty by sixty grid.

Cut small unless you are behind

The rung below found the greedy rule — cut at the largest prime — wrong on 104 of 552 Maundy Cakes and asked for a description of them. On all 104 the best cut is at the smallest prime, the exact opposite. A middle divisor is never needed on any cake in a sixty by sixty grid, and which of the two extremes wins is decided by Ω alone: cut small when Ω(m) + 1 ≥ Ω(n), large otherwise, and that is exact on all 3,540.

positions · Cutcake Running products, and where to stop. Six Maundy Cakes with the prime factors of the longer side, the running products those primes make, and the value the sum of them gives.

The short side only says how many

The rung below settled which cut to make in a Maundy Cake and left the value open. With the cut settled the recursion is a walk, the walk unrolls, and what it unrolls into is the running products of the long side's prime factors, largest first. The short side never enters the products at all — it decides how many of them there are and nothing else, so sixty-two different short sides give one value.

positions · Cutcake Term by term. Every cut of one long side, with its value written as running products beside the terms of the largest-prime cut.

The short side is not in the lemma

The closed form for a two-sided Maundy Cake rested on one unproved statement: that no divisor beats the largest prime. Written out, that statement never mentions the short side — it is an inequality between a multiset of primes and a term count — and once it is stated that way it has a two-line proof, term by term. The ladder ends in a theorem rather than a grid.

positions · Cutcake The two proofs, beside each other. Maundy Cake's rule was proved by restating its lemma so the short side vanished into a multiset of primes and a term count. Cutcake's rule takes the same five steps, with the multiset replaced by a binary length — one integer instead of a multiset — and the closing argument correspondingly shorter. The one line where they differ is which cut a reader would guess.

The obvious cut is the wrong one

Maundy Cake's rule was proved by restating its lemma so the short side vanished. Cutcake's collapses the same way — into a binary length instead of a multiset of primes — but the cut the argument needs is not the one the ladder predicted. Halving is wrong on a third of all cakes, and the smallest counterexample is six squares by two.

positions · Cutcake Five kinds of empty square. Every empty square in a hopless Toads and Frogs strip falls into one of five kinds, and the value follows from which. Three of them are free moves for one player or the other, one of them is where a position stops being a number, and one is a wall that splits the strip into independent pieces.

The square that cannot be halved

Every number in hopless Toads and Frogs is a whole number, which the rung below measured on seven thousand strips and could not explain. The reason is that every empty square is either one player's alone or split evenly between them — except one, and that one is where the numbers stop.

positions · Toads and Frogs Which clause of the rules produces which kind of value. Every combination of pawn-file clause in range, sorted by the kind of value it produces. Files where both pawns can advance are all-small and their values are nimbers and infinitesimals. A file where one pawn is stuck behind a friendly piece gives the other side free moves and is worth an integer. A file whose middle square can be held stops the other pawn the moment somebody reaches it, and is worth a switch — a position both players want to move in. The dictionary is read off the evaluation rather than asserted.

What has to break before a pawn is worth a number

Every value the blocked-file model can hold is an infinitesimal, and the reason is one sentence about the move rule rather than anything about pawns. Break that sentence — a pawn stuck behind a friend, a square only one side can hold — and integers, switches and positions worth fighting over arrive at once.

applied · Chess The only two moves in Kōnane that are not captures. A filled Kōnane board with every opening Black may play marked on it, and the value of the position White's best reply leaves. The opening is the one place in the game where a player removes a stone rather than capturing with one, so it is played under a different rule from everything after it — and the choice is worth a computed amount rather than nothing.

The two moves that are not captures

Kōnane begins from a full board and the first two moves lift stones rather than take them, which is the only time in the whole game anybody does. Nothing on this site applies to them, and the choice is not free — on a 3 × 5 board two of Black's eight openings leave a position a whole move worse than the other six, and on a 3 × 3 board none of the five does.

applied · Kōnane

Named alongside it

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

EnumerationPartizanValueNumberCounterexampleCutcakeExhaustive searchInvariantMaundy cakeSimplicity ruleSwitchBirthday

All concepts