Combinatorial Game Theory
who wins, and by how much
Theme

The thread: The sum is the object

Real positions break into independent parts that are played at once. Adding games up is not a technique within the theory; it is what the theory is for.
301151017111nim-sum001= 1some column does notthe player to move winstake 1 from the heap of 3outcome N Impartial games

Nim, and the nim-sum

Three heaps of counters, take as many as you like from one of them, and the player who takes the last counter wins. The winning condition is not a search, not a table, and not a heuristic — it is the bitwise exclusive-or of the heap sizes, and it was found in 1901.

 2+-1+1/4+∗={5/4 | 5/4}outcome Leach sprig is a separate game; a move is a move in one of themthe total was computed by adding the games, not the labels Sums and comparison

The sum is the object

Real positions come apart into independent regions, and a move happens in exactly one of them. That operation — the disjunctive sum — is what the whole theory is built to survive, and it is the reason values exist at all.

 normal playmisère playevery impartial position is a Nim heapno such reduction existsequal games can be swapped in any sumonly within a restricted universethe value is a single small integeran element of a quotient monoida canonical form exists and is uniquecanonical forms are enormousthe game is what mattersthe game is what mattersmisère quotients recover some of it, one game at a timeand there is no general theory, which after fifty years is a real result rather than a gap Where it stops

Misère play

Change one word — the player who cannot move wins — and the games are identical, the strategies are not, and almost every theorem on this site stops being true. It is the cheapest possible modification and the most expensive.

 a heap of 10, taking 1, 3, 4options lead to heaps of 9, 7, 6whose values are 0, 0, 2mex of those is 1plays exactly likea Nim heap of 1= ∗the value is the heap size — nothing else about the position survives Impartial games

Every impartial game is a Nim heap

Sprague and Grundy proved, independently and four years apart, that any position in any impartial game is equivalent to a single heap of counters. Not similar to one — equal to one, interchangeable with it inside any larger game.

 ↑ − 0= ↑outcome L↑ > 0∗ − 0= ∗outcome N∗ ‖ 0⇑ − ↑= ↑outcome L⇑ > ↑1/2 − 1/4= 1/4outcome L1/2 > 1/4↑∗ − ∗= ↑outcome L↑∗ > ∗the differencethe verdict‖ means confused: neither greater, nor smaller, nor equal — and no amount of care removes it Sums and comparison

Comparing positions

One position is worth at least another when the second player wins their difference. That is the only definition there is, it is a computation rather than a judgement, and it produces an order in which some pairs are simply not comparable.

 the boardworth 2 | −1/2outcome N{2 | −1/2}Left plays verticallyRight plays horizontally Particular games

Domineering

One player places dominoes vertically, the other horizontally, on a shared grid. The rules take one line, the values are a mess, and that mess is the point — this is what the theory looks like applied to a game nobody designed for it.

 as it arises1/201{0 | 1}dominatedoption removedcanonical1/201{0 | 1}both are worth 1/2and every game has exactly one canonical form, which is why values can be compared at all Values

Canonical form

Two positions are worth the same when neither player can tell them apart inside any larger game. Deciding that could be an infinite search. Instead there is a normal form — delete what nobody would play, bypass what backfires — and equality becomes a comparison of two small trees.

 ∗ + ∗N + N0outcome P∗ + ∗2N + N∗3outcome N↑∗ + ↑∗N + N⇑outcome Leach part is a first-player winthe sumsame outcome classes going in, different outcomes coming outso a position has to be given a value, not merely a winner Sums and comparison

Outcomes do not add

Knowing who wins each part of a position tells almost nothing about who wins the whole. Two first-player wins can sum to a second-player win, or to another first-player win, and no rule distinguishes the cases from the outcomes alone.

 {6 | 0}t = 3a big fight{2 | 0}t = 1a smaller one{1 | 0}t = 1/2small change{0 | 1}no temperaturesettled — a numbercomponenthow much is at stakethe whole position is worth {{{19/2 | 17/2} | {15/2 | 13/2}} | {{7/2 | 5/2} | {3/2 | 1/2}}}and the first move goes in the hottest part, which is a theorem up to a small error rather than a rule of thumb 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.

 the value of a Nim positioninstantthe Grundy value of a small subtraction gamelinearthe canonical form of a moderate positionexponential in theorywho wins a general Domineering boardno efficient methodwho wins a generalised board gamePSPACE-completecostthe definitions are constructive, so everything here is computable in principleand the practical range of an exact evaluator is a few dozen moves, which is the working constraint Where it stops

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.

All themes