Combinatorial Game Theory
who wins, and by how much
Theme

The thread: A theorem that names no move

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.
Which questions are answerable. The theory is exact and much of it is expensive. Values are computable by definition; computing one for a position of any size is a different matter, and deciding the winner of a generalised board game is complete for PSPACE — as hard as anything solvable in polynomial space. What it costs

How hard is it

Every theorem on this site stays true at any size. The answers stop being reachable long before the games get interesting — deciding the winner of a generalised board game is PSPACE-complete, and an exact evaluator gives out after a few dozen moves.

 Backward induction on a game that ends, one round at a time. Zermelo's argument as it actually runs. Round zero is the positions where the player to move has no move at all, which is the only thing the procedure knows without being told; each later round is what those settle. Anything still unlabelled when nothing more can be deduced has no label and never will — and on a game with a cycle in it, that leftover is exactly the set of drawn positions. The theorem is a statement about this procedure terminating, and it names the winner of nothing. How it was found

The first theorem, and the winner it declines to name

Zermelo proved in 1913 that a finite game with no chance and no hidden information is decided before anybody sits down — every position is a win for one side or a draw, and which one is settled already. The proof is a labelling procedure, and watching it run shows exactly how little it says.

 A formula, drawn as a game. A token on a directed graph. A move slides it along an edge to a vertex not yet visited, and a player who cannot move loses. That is the whole game, and deciding who wins it is as hard as anything decidable in polynomial space — which is the strongest hardness claim anybody makes about a combinatorial game. What it costs

Hard, proved

A game is as hard as a logical formula when the formula can be drawn as the game. Here is the drawing — a quantified formula turned into a graph with a token on it — with every formula over three variables played both ways and required to agree.

 Grundy values for subtraction of 1, 2, 3. 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. Impartial games

Grundy sequences, and where they stop being predictable

Computing one Grundy value is a mex. Computing all of them produces a sequence, and the sequences do something nobody has fully explained — most of them eventually repeat, some of them take thousands of terms to start, and for a few nobody knows whether they ever do.

 What it costs to decide the winner. Three families of game, each at several sizes, with the number of distinct positions an exhaustive solver must evaluate beside the work its closed form does. The bars are logarithmic. Hardness is not about the size of the board or the length of the rules — Domineering has the shortest rule here — it is about whether anybody has found the shortcut. What it costs

The game with the shortest rule is the hard one

Deciding a generalised board game is PSPACE-complete, which is a statement about families and encodings rather than about size. Nim in the same subject is settled by one pass over the input at any size, and green Hackenbush by one pass over the edges — while Domineering, whose rules take a single line, has no shortcut anybody has found.

 Move where it is hottest. four independent components of one position, ordered by temperature. The temperature is how much a player loses by moving somewhere else instead, so the hottest component is the one to take — and a component that is already a number has no temperature at all, because nobody gains by moving in it. Temperature

Playing the hottest

Given several independent fights, play in the one with most at stake. The rule is simple, it is what strong Go players do without being told, it is provably close to optimal — and it is provably not optimal, which is the interesting part.

 a loop with a way out: 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. Where it stops

Start at the end and work backwards

When play can return to where it started there is no bottom for the recursion to stand on. What replaces it begins at the positions where somebody has already lost and propagates outwards — and the positions it never reaches are exactly the draws. There is no test for a draw, and there does not need to be.

 A golden ratio in a table that never mentions it. Grundy values for Wythoff's game, computed by the mex rule alone — a queen moving left, down or diagonally toward the corner, and whoever cannot move loses. The circles are Wythoff's 1907 description of the losing positions, which came thirty years before any of this machinery: the pairs formed from the golden ratio. They land on the zeros exactly. Nothing in the computation knows about φ and nothing in Wythoff's argument knows about Grundy values. How it was found

A golden ratio thirty years early

Wythoff described the losing positions of his game in 1907 with an argument about partitions of the integers, and no Grundy value anywhere in it. The theory that arrived thirty years later computes the same positions — and has never produced a closed form for the values, which the older argument had for the zeros from the start.

 One of these is a game. Every length that came out of 40 random games from each starting position. Brussels Sprouts always ends after exactly five crosses less two moves, so whoever is to move at that point was decided before the first curve was drawn. Sprouts ends at different lengths depending on how it is played, which is what makes it worth playing. Particular games

Sprouts, and the game that is not one

Two games played with dots and curves, invented in the same room, all but indistinguishable on paper. One is unsolved past forty spots. The other has no decisions in it at all — the winner is fixed before the first curve is drawn.

 One node per route, one node per position. For each board, the number of nodes in the recursion tree a solver with no memo table would walk, beside the number of distinct positions that tree contains, beside the longest run of moves in it. The first number is the cost of forgetting; the second is the size of the table that avoids it; the third is the stack, and it stays small however the other two grow. What it costs

A position reached eleven ways is one position

A 4×4 Domineering board has 5,700 positions in it and 6,257,129 routes through them. Three heaps of 7, 11 and 13 have 480 positions and 7.6 × 10¹⁶ routes. The gap between those two numbers is not an optimisation — it is the difference between a search that finishes and one that does not.

 Which part to move in. A sum, and every move one player has in it. Each row is a component, the option taken in it, and what the whole position becomes. The values of the parts say who wins; they do not say where to play, and the winning move here is in the component worth the least. Sums and comparison

Which part to move in

The value of a sum is the sum of the values. The move in a sum is not the move in any part, and there is no rule that reads it off the values — in the smallest interesting example, the only winning move is in the component worth nothing.

 Hex on 3 × 3, with every winning opening found. A rhombic Hex board with each cell marked according to whether taking it first wins. Left joins the top edge to the bottom and Right joins left to right; a filled board is always a win for exactly one of them, so the search needs no draw test. Strategy stealing proves that a winning opening exists without exhibiting one — these are the ones exhaustive search finds, on a board small enough for exhaustive search to finish. Out in the world

The theorem that names a winner and no move

Strategy stealing proves that the first player wins Hex and wins Chomp, on every board, in about four lines. It exhibits no move, contains nothing a move could be extracted from, and is not going to. The moves have to come from somewhere else, and where they come from runs out almost immediately.

 a path with every link doubled: the criterion and the game. A Shannon switching graph with the two marked vertices in gold. Short secures links and Cut deletes them; Short wins by joining the two marks. Lehman's criterion says Short wins moving second exactly when some subgraph holding both marks splits into two edge-disjoint spanning trees — drawn here in blue and red where one exists. The verdicts beside the graph come from playing the game out, and the criterion is computed without looking at the game at all. Out in the world

A winning strategy that is a spanning tree

The Shannon switching game was sold in a box in 1960 and solved in 1964, and the solution is not an assertion that somebody wins. It is a property of the graph anybody can check, and the strategy falls straight out of it — whichever link the opponent cuts, take its partner in the other tree.

 Poker Nim from 3, 5, 7, with reserves of 4 and 4. Nim with one extra kind of move: a player may put any number of counters back onto a heap from a private reserve. It looks as though a losing player could stall for ever. They cannot, and the winner is decided by exactly the same nim-sum as ordinary Nim — checked here over every position within a stated range rather than argued. Where it stops

The condition the recursion rests on

Not that the moves run out, and not that the options are few. Poker Nim's heaps can grow without bound and it ends; the game called `on` has one option and never does. What every value on this site needs is that no infinite run of moves exists — and there are three separate ways to fail it.

 6 octal games, and which of them settle. Each row is an octal game: its code, the moves it allows, the first two dozen Grundy values, and whether a period was found in the values computed here. Guy and Smith surveyed these by hand in 1956 and conjectured that every finite octal game is eventually periodic. Seventy years and a great deal more arithmetic later, the rows in magenta are the state of that conjecture — not counterexamples, but sequences in which nothing periodic has yet appeared. How it was found

The sequence nobody has settled

Guy and Smith surveyed the octal games by hand in 1956 and conjectured that every finite one is eventually periodic. Seventy years and a great deal more arithmetic later, some of them have settled and some have not — and the evidence for the conjecture is entirely that nobody has found a counterexample they were looking for.

 Folding a 4×4 board by its symmetries. The size of a Domineering solver's table when positions related by a board symmetry are stored once. The saving rises toward the size of the symmetry group and stops there — it is a constant factor by construction, and no board is large enough to make it anything else. What it costs

What counts as the same position, and what that is worth

Folding a 4×4 Domineering board by its symmetries takes the table from 5,700 entries to 1,522 — a saving of 3.75, against a ceiling of exactly 4. An orbit cannot be larger than the group acting on it, so this is the one saving in the subject that can never change an exponent.

 Every quantifier is a move. A quantified boolean formula with its quantifiers drawn as turns: an existential is a choice by the player to move, a universal a choice by the opponent. The same formula is put through the reduction to Generalized Geography and the two answers are checked against each other, so the prefix of quantifiers and the game beside it are one claim. What it costs

A puzzle asks once, a game asks alternately

Quantifier alternation is the whole difference between a puzzle and a game. One chooser is an existential and its answer is a witness somebody can check; two choosers taking turns is a prefix of alternating quantifiers, and the witness stops being an assignment and becomes a strategy.

 Comparing two positions means playing a third. Pairs of positions with the relation between them, and the game whose solution decided it. There is no way to compare two games by looking at them: the question “is G at least H?” is answered by playing G − H and asking who wins, which is a search, and its cost is counted here beside each answer. Sums and comparison

Comparing two positions means playing a third

There is no way to look at two games and see which is better. The question "is G at least H?" is answered by building G − H and asking who wins it — so the most basic operation in the theory is a decision problem, and every canonical form is built out of them.

 The same position, and two rulers to measure it with. Nim positions with the length of their input under two encodings — the heap sizes in binary, and the counters themselves — beside the work the nim-sum does. The work never changes. Which of the two lengths it is compared against decides whether the same algorithm reads as linear or as exponentially fast, and hardness claims are always made against one particular encoding. What it costs

Nim is easy, in binary

Three heaps of a thousand counters take thirty bits to write down and three thousand counters to lay out. The nim-sum does three exclusive-ors either way. Whether that counts as fast depends entirely on which of the two numbers the work is compared against.

 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. Impartial games

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.

 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. What it costs

"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.

 Classes needed, as the heaps get bigger — Dawson's chess ·137. How many kinds of position there are, against how large a heap the universe allows. Under normal play the answer stops growing as soon as the Grundy values stop growing. Under misère play it does not stop, and every new class is a pair of positions that behave identically under normal play and differently under misère. How it was found

"Hopeless" was a claim about a method

Misère analysis was declared intractable in the 1970s, and the verdict was correct about what was being attempted. Quotients did not refute it thirty years later — they changed the question from a value per position to a monoid per universe, and the computed sizes show why the first question has no good answer.

 One Sprouts game from 3 spots, counted. One randomly played Sprouts game, with the map counted after every move. A move spends two lives and the new spot brings one, so the lives fall by exactly one every time — and unlike the arms of a Brussels cross they are not replaced. Every move either cuts a face in two or joins two separate pieces of the drawing, and how many of each a game contains is up to the players, which is why the length is not fixed. How it was found

A conjecture from hand play

Sprouts was invented over tea and its outcome pattern was guessed from games played with a pencil. Computers have checked it far past where a person could go, and this site's own solver gives out at three spots — so the honest figure states the frontier it reaches rather than the number somebody else published.

 One node per route, one node per position. For each board, the number of nodes in the recursion tree a solver with no memo table would walk, beside the number of distinct positions that tree contains, beside the longest run of moves in it. The first number is the cost of forgetting; the second is the size of the table that avoids it; the third is the stack, and it stays small however the other two grow. What it costs

The class is named after memory, and that is not an accident

A 4×4 Domineering board has 6,257,129 routes through it, 5,700 distinct positions, and a deepest line eight moves long. Those three numbers are three different resources, and the smallest of them is the one that gives games their complexity class.

All themes