Combinatorial game theory

Defining features

In practice, a game studied by CGT typically satisfies:

• Two players alternate moves with no chance elements, so outcomes are deterministic and not influenced by luck.
• All information about the current position is available to both players (perfect information).
• Every position has a finite set of legal moves and the play is guaranteed to terminate in a finite number of steps.
• Victory is decided by the ability (or inability) to move: when a player has no legal move they normally lose, defining a clear winner and loser.

Core concepts and classifications

Games in CGT split into two broad types: impartial games, where both players have the same moves from each position (examples: Nim, Grundy games), and partizan games, where the two players have different options (examples: Hackenbush, Domineering). For impartial games the Sprague–Grundy theorem assigns each position a nimber or Grundy number; positions behave like piles of Nim under the disjunctive sum, and the nimber addition rule determines outcomes. Partizan games require a richer algebra of values, introduced and developed through Conway's theory of surreal numbers and more general game values such as infinitesimals and hot/cold games.

Mathematical structure and operations

A central operation in CGT is the disjunctive sum: playing two games in parallel where a move consists of moving in exactly one component. This leads to an additive theory of games and to value assignments that can be combined algebraically. Researchers classify positions by outcome classes (next-player win, previous-player win, etc.) and study canonical forms, equivalence under play, and thermography to understand how the urgency of moves changes the effective value of positions.

History and notable contributors

The modern systematic study of combinatorial games was shaped in the late 20th century by several mathematicians. Elwyn Berlekamp, John Conway and Richard Guy were key figures who collaborated on foundational texts; see Berlekamp, Conway, and Guy. Their joint work in the 1960s and later culminated in the influential book Winning Ways for Your Mathematical Plays, which brought many ideas and examples to a broad audience and helped establish CGT as a distinct field.

Applications, examples, and complexity

CGT methods are used to analyze and sometimes fully solve abstract games and concrete board-game endgames. Famous applications include computing Grundy values for impartial octal games, analyzing endgame components in Go, and solving specific instances of partizan games such as Hackenbush or domineering. From a computational standpoint, many natural decision problems derived from combinatorial games are computationally hard: determining the winning status of arbitrary positions is often PSPACE-hard or PSPACE-complete, which motivates heuristics, decomposition techniques, and exact search methods for small instances.

Remarks and distinctions

While CGT provides a rigorous algebraic and algorithmic toolkit, its scope is intentionally narrow: it excludes games with chance, hidden information, or multi-player coalitional settings that define other branches of game theory. Within its domain, CGT continues to evolve, blending algebraic insight, enumerative methods, and computer-assisted search to classify games, discover surprising equivalences, and extend the range of solvable examples.

For introductions and further reading, textbooks and survey articles provide accessible entry points; specialist research papers discuss advanced topics such as partizan value theory, temperature and thermography, and algorithmic complexity of game decision problems.