Combinatorial Game Theory
who wins, and by how much
Concept

P-position — where it appears

A position the player about to move loses, whatever they do, against best play. Under normal play these are the positions whose value is zero, and under the conjunctive rule they are the ones of even remoteness.

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

a cycle of three: what the backward analysis settles. A position graph in which the moves can lead back to where they started. The labels are the order in which a backward analysis settles each position, starting from the ones where a player has already run out of moves. Positions the analysis never reaches are drawn — and there is no test for that; being unreachable is what a draw is.

An outcome with no value behind it

Retrograde analysis labels positions in rounds, outward from the ones already lost. Whatever is still blank when nothing more can be deduced is a draw — and there is no separate test for a draw, because a draw is exactly the residue the method never reaches.

limits · Loopy Grundy values for subtraction of 1, 3, 4. The Grundy value of every heap size for a take-away game, computed by the mex rule. A period, if the figure marks one, was found by searching the computed sequence rather than assumed — and where no period is marked, none was found in the range drawn, which is not the same as there being none.

Take one, three or four

A heap and a list of legal takes. It is the smallest interesting impartial game there is, and the only family in the subject where eventual periodicity is not observed, not conjectured, but guaranteed — with a bound on when it must appear.

impartial · Subtraction A winning strategy on 3×3, drawn whole. The whole of one player's winning strategy on a small Domineering board: their own move at each of their turns, and every reply the opponent has at each of theirs. The strategy branches only where the loser chooses. Its size is what somebody would have to be handed to check the claim that this player wins, and it is far larger than the claim itself.

"Left wins" has no short proof

A complete solution of Nim on heaps of 7, 11 and 13 is 480 table entries. A winning strategy for the same position — one move of the winner's at each of their turns, and an answer to every reply — has 56,167,022 nodes in it. The answer is smaller than the proof by a factor of a hundred thousand.

complexity · Complexity What the two outcome classes of the parts settle. For each pair of outcome classes, the set of outcomes the sums actually took. A cell with one letter is a pair of classes that decided the answer; a shaded cell with several is a pair that did not. Both conventions have ambiguous cells — the difference is that normal play repairs them with values and misère play has nothing to repair them with.

Two misère outcomes are not enough

Knowing who wins each part does not say who wins the sum. Over 676 sums built from a pool of twenty-six positions, nine of the sixteen pairs of outcome classes settle the answer under normal play and not one of the sixteen settles it under misère — and the nine that work are theorems about a value being zero, which is exactly the thing misère play does not have.

limits · Misère play Mock Turtles on 8 coins: every lost position. The rows a player to move has already lost, drawn in full. A filled disc is a coin showing heads. The set is closed under turning over every coin two of its members disagree about, which is what makes it a linear code, and the count of heads in the sparsest of them is the fewest coin turns that separate two lost positions.

The losing positions are a code

Turn over one, two or three coins, and the rows a player has already lost turn out to be closed under adding two of them together. That makes them a linear code — and on eight coins it is the extended Hamming code exactly, sixteen words with a weight enumerator of 1 + 14x⁴ + x⁸, produced by a move rule that knows nothing about codes.

impartial · Codes Cram on 4 by 4: the pairing strategy. Cram is Domineering with the orientations shared: either player may place a domino either way up, so both players have exactly the same moves and the game is impartial. Every position therefore has a Grundy value, and this board's was computed by the mex rule over its own placements.

Cram

Domineering with one word of the rule changed: both players may place a domino either way up. That makes the game impartial, and the entire partizan apparatus collapses into a single Grundy value — on the 4 × 4 board, Domineering's canonical form runs to 114 characters of nested braces and Cram's answer is the one character 0.

impartial · Cram What the outcome of a loopy sum can be. One row and one column per loopy outcome class, and each cell lists every outcome a sum of two such positions was found to have. Most cells hold several. The cell where both parts are drawn holds one.

The one outcome that adds

Finite outcomes do not add: two first-player wins can sum to anything. Loopy play has seven outcome classes instead of four and adds even less — of the 28 cells in the table, eleven hold several answers. Two do not, and they are the two worth having: a second-player win added to anything leaves the outcome alone, and a draw added to a draw is a draw. A draw added to anything else is not.

limits · Loopy Mock Turtles on 8 coins: finding the move is decoding. Every row of the game, sorted by what it takes to win from it. The lost rows are the codewords; a won row is a codeword with errors, and the winning move is the error pattern that turns them off. The distance column is a fact about the code and the coins column is a fact about the rules, and the two do not quite agree.

The code names the move

If the lost rows of a coin-turning game are a linear code, then a won row is a codeword with errors in it and the winning move is whatever turns the errors off. Over all 256 rows of Mock Turtles on eight coins: 16 codewords, 240 won rows, none more than two coins from a lost one — and 64 of them whose cheapest winning move has to turn three coins anyway.

impartial · Codes Welter positions and what they are worth. Coins on a strip, with the Grundy value the recursion returns and the nim-sum the squares would have if they were independent heaps. The two columns are the essay: they hardly ever agree.

No two heaps alike

Welter's game is Nim with one extra clause — no two heaps may be the same size — and the clause is fatal to the nim-sum, which gives the right answer in none of the 120 three-coin positions. What replaces it is a function of pairs: ⟨a | b⟩ = (a ⊕ b) − 1, exact on all 55 two-coin positions, and nim-added over every pair it is exact on the whole board provided the number of coins is even.

impartial · Welter What a wider pool rescues. The misère outcome table built four times over, on pools of 10, 22, 100, 113 positions. A cell holds the set of outcomes that sums of its row class and column class actually took. Fifteen of the sixteen cells are short of all four outcomes on the smallest pool and none is on the largest, so every near-miss in the original table was a statement about the pool rather than about misère play.

What a wider pool rescues

The misère outcome table has sixteen cells, and over a pool of ten positions fifteen of them hold fewer than four outcomes — which looks like structure and might be a shortage of positions. Thirteen values further on there is nothing left: every pair of outcome classes takes every outcome, so the near-misses were the pool, and the prediction the rung below made was right.

limits · Misère play 7 symmetries, and the one that is a strategy. 4 games and 7 candidate symmetries, each tested by playing the strategy out against every opponent line rather than by argument. A pairing strategy needs a map that fixes the start, is an involution, and carries one player's moves to the other's — and the last condition is where most of these fail.

The strategy that is a symmetry

A pairing strategy is a symmetry of the board that turns one player's moves into the other's, and it wins without computing anything. Tested by playing it out rather than argued, it wins one of seven candidate symmetries across four games — exactly the Cram boards with both sides even, which is exactly where no domino is its own image.

impartial · Pairing A thousand shapes, and twelve pairings. Cram on every connected shape of at most eight squares, with the search for a symmetry that answers each of the opponent’s moves. Every pairing found is a second-player win, most shapes have no involution at all, and the strategy accounts for a sixth of the second-player wins there are.

Looking for the symmetry

Answering every move with its mirror image wins Cram on a board with both sides even, which is the argument everybody meets. Asked of every connected shape of at most eight squares instead of of thirteen rectangles, it wins twelve — and accounts for a sixth of the second-player wins there are, because 852 of the 1,042 shapes have no symmetry to answer with in the first place.

impartial · Pairing Moore’s rule, reversed. Moore’s Nim under the misère convention at three values of k, with the normal-play rule and the same rule plus a clause about heaps of one. The patch is the one Nim takes, with the modulus the normal-play rule already carries, and it is right on every position swept.

The patch that generalised

Misère Nim takes a one-line patch: play the normal-play strategy until every heap holds a single counter, then invert. Moore's Nim, where a move may take from up to k heaps at once, takes exactly the same patch with exactly the same modulus — and the two rules disagree on six positions out of 923.

impartial · Moores-nim Thirty-two words, four of them lost. Every position of five heaps grouped by the parities of its heaps in decreasing order of size. Each word is uniform, and four of the thirty-two are losing.

The parities, in size order

The rung below settled four of six parity classes in bounded Moore's Nim and asked whether the sizes pick out the losing positions in the two it could not. They do — but only through the order they put the parities in. Sort the heaps largest first, read off their parities, and that five-bit word settles the whole game at every width of move, with the losing words forming a subspace.

impartial · Moores-nim Two heaps and a held pass. Every pair of heaps up to 16 with one pass available that may not be the last move. Filled cells are the pairs the player to move loses: the empty board and the pairs one and two, three and four, five and six, and so on. Outlined cells are the equal pairs Nim calls lost, all of which are wins once the pass is there.

Three heaps and a pass

Nim with a single pass that may not end the game is easy on one heap and on two: a heap swaps each odd size with the even one above it, and two heaps lose exactly at (2k − 1, 2k). On three heaps the losses are known only as a list. Fix the smallest heap and each slice of the list settles into a pattern after an irregular start — period 4, 8, 10, then 160 at a smallest heap of ten, and nothing visible from eleven.

limits · Pass

Named alongside it

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

ImpartialExhaustive searchGrundy valueNimNormal playNim-sumXORInvariantStrategyDisjunctive sumEnumerationMex

All concepts