Combinatorial Game Theory
who wins, and by how much
Concept

Retrograde analysis — where it appears

Labelling a position graph backwards from the positions where somebody has already lost, which replaces the recursion when play may not end. It answers a smaller question than the recursion did: who wins, with no value behind the answer.

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

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.

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.

history · Determinacy 1 ko point, no ko rule. A ko fight drawn as a position graph and labelled by retrograde analysis: blue edges are Black's captures, red are White's, and each position carries the verdict for whichever side is to move. Positions the propagation never reaches are drawn — neither player can force a win and the game does not end — and they appear only where the rules permit a repetition.

The rule that makes Go a finite game

A ko is a point in Go where a capture can be recaptured for ever, and every set of rules forbids it. That prohibition is not etiquette or tidiness — it is the hypothesis that puts Go inside the class of games every theorem on this site is about, and removing it removes the values.

applied · Go 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 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.

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.

limits · Termination on + off: 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.

One part that never ends

The game called `on` has one move and it is back to itself. Add anything to it — a star, a point, its own mirror image — and the whole board is drawn. So `off` is exactly the negative of `on` and their sum is not zero, which is the group law failing for a reason that has nothing to do with who is winning.

limits · Loopy 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.

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.

complexity · Complexity Three things the word “solved” is used for. The three standard senses of a solved game, priced on positions this solver can settle completely. Ultra-weak names the winner; weak supplies a strategy from the opening; strong supplies one from every position. They differ by orders of magnitude, and a claim that a game is solved is nearly useless until it says which of the three it means.

Three different claims are all called solved

Hex is solved in the sense that the first player provably wins, by an argument that names no move whatever. Nim is solved in the sense that a formula gives the right move from any position at any size. Between them sit strategies for one opening, and databases of a few billion positions. The word covers all four.

complexity · Complexity a loop with a way out under three rules for never ending. One graph, one labelling, and three ways of reading the residue the labelling never reaches. A draw is not a computed outcome here — it is what is left over — so declaring infinite play a win for one side is a legal alternative that costs no extra search and changes who wins.

When never ending is a win

Retrograde analysis labels a position a win when somebody can force the opponent to be stuck, and leaves everything else blank. Calling the blanks draws is a rule from outside the game — and two other rules are available. The labelling does not change under any of them; only the residue does, and on a three-cycle that residue is every position on the board.

limits · Loopy 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 A fortress, and the counter that gives it a label. A pawn ending where the defender's king shuffles for ever and the attacker needs time. Down the rows, how many moves of preparation the breakthrough needs; across the columns, how many moves the rule allows before declaring a draw. With no breakthrough the position is drawn whatever the rule says, and drawn as a residue the backward induction never reaches. With a breakthrough and no rule the attacker wins despite the cycle. Where the march is longer than the counter allows, the rule turns a won position into a drawn one.

A position with no value, and the rule that gives it one

A fortress is a cycle in the position graph, so the recursion defining a value has nowhere to bottom out and the propagation never reaches it. Chess has a rule for that — count fifty moves and call it drawn — and the rule does not merely tidy the theory up. On eleven cells of the sweep it takes away a win.

applied · Chess A ko fight decided somewhere else on the board. A ko fight against the number of ko threats each side holds. A threat is a play elsewhere that the opponent must answer, and it lifts the prohibition on recapturing, so a player short of threats runs out of ways to come back. Every cell is a full retrograde labelling and the pattern in them is read off afterwards: the fight goes to whoever is ahead on a quantity that is not on this part of the board at all. Where the labelling never settles, the fight is a no-result whatever anybody holds.

A ko is won somewhere else

The rung below shows the ko rule buying finiteness by deleting one edge. What it buys with the same edge is a fight nobody can settle by looking at it — the prohibition forces a player to spend a threat, threats are counted on the rest of the board, and every decided cell of the sweep goes to whoever is ahead on a quantity that is not in the picture.

applied · Go A shuttle and a loop, judged by what the play returns to. A three-node loopy game drawn as a graph, with Left's moves in blue, Right's in red and position a marked. Beside it, each position-and-mover pair under the backward labelling and under the rule that a never-ending play goes to Left when it returns to a infinitely often. Four pairs are drawn by the labelling; the new rule gives two to Left and two to Right and leaves the decided pairs as they were.

What the play keeps coming back to

A draw is what the backward labelling never reaches, and handing every never-ending play to one player turns the draws into wins wholesale. Judge an infinite play instead by what it keeps returning to, and every draw gets a winner of its own: over the 262,144 three-node games, 15,432 send some of their draws to one player and some to the other, which no wholesale rule can do. Finding those winners takes a fixed point inside a fixed point.

history · Determinacy Four positions, sampled. Three samples of three thousand loopy regions on four positions, drawn with each possible move present at a chance of one half, about a third and a quarter. For each: how many regions have both sides named by the thirty-five names two-position regions use, by those together with the thirteen invented for three positions, and how many need a new name.

Four positions, sampled

Ten names write both sides of every loopy region of two positions, and forty-eight every region of three. Four positions are over four billion graphs and cannot be counted, but they can be drawn. Three thousand regions at each of three densities: the forty-eight names cover between 95.9 and 99.5 per cent, the thirteen names invented for three positions come back at four almost all of them, and the sparsest sample meets thirty-five sides nothing earlier reproduces — a floor of eighty-three names, and a curve that grows by accretion rather than collapse.

history · Notation

Named alongside it

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

LoopyDrawOutcome classPosition graphTerminationExhaustive searchDeterminacyKo (Go)NimOn, the game that never stopsStrategyBackward induction

All concepts