Combinatorial Game Theory
who wins, and by how much
Field

Where it stops

Misère play, loopy games and computational hardness — three ways the theory runs out, and what survives each.
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

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.

 ABCthe moves lead back to where they startedno base case, so the recursion never bottoms outa third outcome appears: neither player can force a winloopy game theory is a separate subject with separate machinery

Loopy games

The whole theory assumes play stops. Allow a position to recur and the induction that every value rests on has nothing to stand on — and a fifth outcome appears that normal-play theory has no name for.

 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

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 essays