Combinatorial game theory

Branch of game theory about two-player sequential games with perfect information

This article is about the theory of combinatorial games. For the theory that includes games of chance and games of imperfect knowledge, see Game theory.

Mathematicians playing Kōnane at a combinatorial game theory workshop

Combinatorial game theory is a branch of mathematics and theoretical computer science that typically studies sequential games with perfect information. Research in this field has primarily focused on two-player games in which a position evolves through alternating moves, each governed by well-defined rules, with the aim of achieving a specific winning condition. Unlike economic game theory, combinatorial game theory generally avoids the study of games of chance or games involving imperfect information, preferring instead games in which the current state and the full set of available moves are always known to both players.[1] However, as mathematical techniques develop, the scope of analyzable games expands, and the boundaries of the field continue to evolve.[2] Authors typically define the term "game" at the outset of academic papers, with definitions tailored to the specific game under analysis rather than reflecting the field’s full scope.

Combinatorial games include well-known examples such as chess, checkers, and Go, which are considered complex and non-trivial, as well as simpler, "solved" games like tic-tac-toe. Some combinatorial games, such as infinite chess, may feature an unbounded playing area. In the context of combinatorial game theory, the structure of such games is typically modeled using a game tree. The field also encompasses single-player puzzles like Sudoku, and zero-player automata such as Conway's Game of Life—although these are sometimes more accurately categorized as mathematical puzzles or automata, given that the strictest definitions of "game" imply the involvement of multiple participants.[3]

A key concept in combinatorial game theory is that of the solved game. For instance, tic-tac-toe is solved in that optimal play by both participants always results in a draw. Determining such outcomes for more complex games is significantly more difficult. Notably, in 2007, checkers was announced to be weakly solved, with perfect play by both sides leading to a draw; however, this result required a computer-assisted proof.[4] Many real-world games remain too complex for complete analysis, though combinatorial methods have shown some success in the study of Go endgames. Analyzing a position using combinatorial game theory involves identifying the optimal sequence of moves for both players until the game's conclusion, but this process becomes prohibitively difficult for anything beyond simple games.

It is useful to distinguish between combinatorial "mathgames"—games of primary interest to mathematicians and scientists for theoretical exploration—and "playgames," which are more widely played for entertainment and competition.[5] Some games, such as Nim, straddle both categories. Nim played a foundational role in the development of combinatorial game theory and was among the earliest games to be programmed on a computer.[6] Tic-tac-toe continues to be used in teaching fundamental concepts of game AI design to computer science students.[7]

## Difference with traditional game theory

[edit]

Combinatorial game theory contrasts with "traditional" or "economic" game theory, which, although it can address sequential play, often incorporates elements of probability and incomplete information. While economic game theory employs utility theory and equilibrium concepts, combinatorial game theory is primarily concerned with two-player perfect-information games and has pioneered novel techniques for analyzing game trees, such as through the use of surreal numbers, which represent a subset of all two-player perfect-information games. The types of games studied in this field are of particular interest in areas such as artificial intelligence, especially for tasks in automated planning and scheduling. However, there is a distinction in emphasis: while economic game theory tends to focus on practical algorithms—such as the alpha–beta pruning strategy commonly taught in AI courses—combinatorial game theory places greater weight on theoretical results, including the analysis of game complexity and the existence of optimal strategies through methods like the strategy-stealing argument.

## History

[edit]

Combinatorial game theory arose in relation to the theory of impartial games, in which any play available to one player must be available to the other as well. One such game is Nim, which can be solved completely. Nim is an impartial game for two players, and subject to the normal play condition, which means that a player who cannot move loses. In the 1930s, the Sprague–Grundy theorem showed that all impartial games are equivalent to heaps in Nim, thus showing that major unifications are possible in games considered at a combinatorial level, in which detailed strategies matter, not just pay-offs.

In the 1960s, Elwyn R. Berlekamp, John H. Conway and Richard K. Guy jointly introduced the theory of a partisan game, in which the requirement that a play available to one player be available to both is relaxed. Their results were published in their book Winning Ways for your Mathematical Plays in 1982. However, the first work published on the subject was Conway's 1976 book On Numbers and Games, also known as ONAG, which introduced the concept of surreal numbers and the generalization to games. On Numbers and Games was also a fruit of the collaboration between Berlekamp, Conway, and Guy.

Combinatorial games are generally, by convention, put into a form where one player wins when the other has no moves remaining. It is easy to convert any finite game with only two possible results into an equivalent one where this convention applies. One of the most important concepts in the theory of combinatorial games is that of the sum of two games, which is a game where each player may choose to move either in one game or the other at any point in the game, and a player wins when his opponent has no move in either game. This way of combining games leads to a rich and powerful mathematical structure.

Conway stated in On Numbers and Games that the inspiration for the theory of partisan games was based on his observation of the play in Go endgames, which can often be decomposed into sums of simpler endgames isolated from each other in different parts of the board.

## Examples

[edit]

The introductory text Winning Ways introduced a large number of games, but the following were used as motivating examples for the introductory theory:

* Blue–Red Hackenbush \- At the finite level, this partisan combinatorial game allows constructions of games whose values are dyadic rational numbers. At the infinite level, it allows one to construct all real values, as well as many infinite ones that fall within the class of surreal numbers.
* Blue–Red–Green Hackenbush - Allows for additional game values that are not numbers in the traditional sense, for example, star.
* Toads and Frogs \- Allows various game values. Unlike most other games, a position is easily represented by a short string of characters.
* Domineering \- Various interesting games, such as hot games, appear as positions in Domineering, because there is sometimes an incentive to move, and sometimes not. This allows discussion of a game's temperature.
* Nim \- An impartial game. This allows for the construction of the nimbers. (It can also be seen as a green-only special case of Blue-Red-Green Hackenbush.)

The classic game Go was influential on the early combinatorial game theory, and Berlekamp and Wolfe subsequently developed an endgame and temperature theory for it (see references). Armed with this they were able to construct plausible Go endgame positions from which they could give expert Go players a choice of sides and then defeat them either way.

Another game studied in the context of combinatorial game theory is chess. In 1953 Alan Turing wrote of the game, "If one can explain quite unambiguously in English, with the aid of mathematical symbols if required, how a calculation is to be done, then it is always possible to programme any digital computer to do that calculation, provided the storage capacity is adequate."[8] In a 1950 paper, Claude Shannon estimated the lower bound of the game-tree complexity of chess to be 10120, and today this is referred to as the Shannon number.[9] Chess remains unsolved, although extensive study, including work involving the use of supercomputers has created chess endgame tablebases, which shows the result of perfect play for all end-games with seven pieces or less. Infinite chess has an even greater combinatorial complexity than chess (unless only limited end-games, or composed positions with a small number of pieces are being studied).

## Overview

[edit]

A game, in its simplest terms, is a list of possible "moves" that two players, called left and right, can make. The game position resulting from any move can be considered to be another game. This idea of viewing games in terms of their possible moves to other games leads to a recursive mathematical definition of games that is standard in combinatorial game theory. In this definition, each game has the notation {L|R}. L is the set of game positions that the left player can move to, and R is the set of game positions that the right player can move to; each position in L and R is defined as a game using the same notation.

Using Domineering as an example, label each of the sixteen boxes of the four-by-four board by A1 for the upper leftmost square, C2 for the third box from the left on the second row from the top, and so on. We use e.g. (D3, D4) to stand for the game position in which a vertical domino has been placed in the bottom right corner. Then, the initial position can be described in combinatorial game theory notation as

{ ( A 1 , A 2 ) , ( B 1 , B 2 ) , … | ( A 1 , B 1 ) , ( A 2 , B 2 ) , … } . {\displaystyle \\{(\mathrm {A} 1,\mathrm {A} 2),(\mathrm {B} 1,\mathrm {B} 2),\dots |(\mathrm {A} 1,\mathrm {B} 1),(\mathrm {A} 2,\mathrm {B} 2),\dots \\}.}

In standard Cross-Cram play, the players alternate turns, but this alternation is handled implicitly by the definitions of combinatorial game theory rather than being encoded within the game states.

{ ( A 1 , A 2 ) | ( A 1 , B 1 ) } = { { | } | { | } } . {\displaystyle \\{(\mathrm {A} 1,\mathrm {A} 2)|(\mathrm {A} 1,\mathrm {B} 1)\\}=\\{\\{|\\}|\\{|\\}\\}.}

The above game describes a scenario in which there is only one move left for either player, and if either player makes that move, that player wins. (An irrelevant open square at C3 has been omitted from the diagram.) The {|} in each player's move list (corresponding to the single leftover square after the move) is called the zero game, and can actually be abbreviated 0. In the zero game, neither player has any valid moves; thus, the player whose turn it is when the zero game comes up automatically loses.

The type of game in the diagram above also has a simple name; it is called the star game, which can also be abbreviated ∗. In the star game, the only valid move leads to the zero game, which means that whoever's turn comes up during the star game automatically wins.

An additional type of game, not found in Domineering, is a loopy game, in which a valid move of either left or right is a game that can then lead back to the first game. Checkers, for example, becomes loopy when one of the pieces promotes, as then it can cycle endlessly between two or more squares. A game that does not possess such moves is called loopfree.

There are also transfinite games, which have infinitely many positions—that is, left and right have lists of moves that are infinite rather than finite.

## Game abbreviations

[edit]

### Numbers

[edit]

Numbers represent the number of free moves, or the move advantage of a particular player. By convention positive numbers represent an advantage for Left, while negative numbers represent an advantage for Right. They are defined recursively with 0 being the base case.

0 = {|}
1 = {0|}, 2 = {1|}, 3 = {2|}
−1 = {|0}, −2 = {|−1}, −3 = {|−2}

The zero game is a loss for the first player.

The sum of number games behaves like the integers, for example 3 + −2 = 1.

Any game number is in the class of the surreal numbers.

### Star

[edit]

Main article: Star (game theory)

Star, written as ∗ or {0|0}, is a first-player win since either player must (if first to move in the game) move to a zero game, and therefore win.

∗ + ∗ = 0, because the first player must turn one copy of ∗ to a 0, and then the other player will have to turn the other copy of ∗ to a 0 as well; at this point, the first player would lose, since 0 + 0 admits no moves.

The game ∗ is neither positive nor negative; it and all other games in which the first player wins (regardless of which side the player is on) are said to be fuzzy or confused with 0; symbolically, we write ∗ || 0.

The game ∗n is notation for {0, ∗, …, ∗(n−1)| 0, ∗, …, ∗(n−1)}, which is also representative of normal-play Nim with a single heap of n objects. (Note that ∗0 = 0 and ∗1 = ∗.)

### Up and down

[edit]

Up, written as ↑, is a position in combinatorial game theory.[10] In standard notation, ↑ = {0|∗}. Its negative is called down.

−↑ = ↓ (down)

Up is strictly positive (↑ > 0), and down is strictly negative (↓ < 0), but both are infinitesimal. Up and down are defined in Winning Ways for your Mathematical Plays.

### "Hot" games

[edit]

Main article: hot game

Consider the game {1|−1}. Both moves in this game are an advantage for the player who makes them; so the game is said to be "hot;" it is greater than any number less than −1, less than any number greater than 1, and fuzzy with any number in between. It is written as ±1. Note that a subclass of hot games, referred to as ±n for some numerical game n is a switch game. Switch games can be added to numbers, or multiplied by positive ones, in the expected fashion; for example, 4 ± 1 = {5|3}.

## Nimbers

[edit]

An impartial game is one where, at every position of the game, the same moves are available to both players. For instance, Nim is impartial, as any set of objects that can be removed by one player can be removed by the other. However, domineering is not impartial, because one player places horizontal dominoes and the other places vertical ones. Likewise Checkers is not impartial, since the players own different colored pieces. For any ordinal number, one can define an impartial game generalizing Nim in which, on each move, either player may replace the number with any smaller ordinal number; the games defined in this way are known as nimbers. The Sprague–Grundy theorem states that every impartial game under the normal play convention is equivalent to a nimber.

The "smallest" nimbers – the simplest and least under the usual ordering of the ordinals – are 0 and ∗.

## See also

[edit]

* Alpha–beta pruning, an optimised algorithm for searching the game tree
* Backward induction, reasoning backwards from a final situation
* Cooling and heating (combinatorial game theory), various transformations of games making them more amenable to the theory
* Connection game, a type of game where players attempt to establish connections
* Endgame tablebase, a database saying how to play endgames
* Expectiminimax tree, an adaptation of a minimax game tree to games with an element of chance
* Extensive-form game, a game tree enriched with payoffs and information available to players
* Game classification, an article discussing ways of classifying games
* Game complexity, an article describing ways of measuring the complexity of games
* Grundy's game, a mathematical game in which heaps of objects are split
* Multi-agent system, a type of computer system for tackling complex problems
* Positional game, a type of game where players claim previously-unclaimed positions
* Solving chess
* Sylver coinage, a mathematical game of choosing positive integers that are not the sum of non-negative multiples of previously chosen integers
* Wythoff's game, a mathematical game of taking objects from one or two piles
* Topological game, a type of mathematical game played in a topological space
* Zugzwang, being obliged to play when this is disadvantageous

## Notes

[edit]

1. ^ Lessons in Play, p. 3
2. ^ Thomas S. Fergusson's analysis of poker is an example of combinatorial game theory expanding into games that include elements of chance. Research into Three Player Nim is an example of study expanding beyond two player games. Conway, Guy and Berlekamp's analysis of partisan games is perhaps the most famous expansion of the scope of combinatorial game theory, taking the field beyond the study of impartial games.
3. ^ Demaine, Erik D.; Hearn, Robert A. (2009). "Playing games with algorithms: algorithmic combinatorial game theory". In Albert, Michael H.; Nowakowski, Richard J. (eds.). Games of No Chance 3. Mathematical Sciences Research Institute Publications. Vol. 56\. Cambridge University Press. pp. 3–56\. arXiv:cs.CC/0106019.
4. ^ Schaeffer, J.; Burch, N.; Bjornsson, Y.; Kishimoto, A.; Muller, M.; Lake, R.; Lu, P.; Sutphen, S. (2007). "Checkers is solved". Science. 317 (5844): 1518–1522\. Bibcode:2007Sci...317.1518S. CiteSeerX 10.1.1.95.5393. doi:10.1126/science.1144079. PMID 17641166. S2CID 10274228.
5. ^ Fraenkel, Aviezri (2009). "Combinatorial Games: selected bibliography with a succinct gourmet introduction". Games of No Chance 3. 56: 492.
6. ^ Grant, Eugene F.; Lardner, Rex (2 August 1952). "The Talk of the Town - It". The New Yorker.
7. ^ Russell, Stuart; Norvig, Peter (2021). "Chapter 5: Adversarial search and games". Artificial Intelligence: A Modern Approach. Pearson series in artificial intelligence (4th ed.). Pearson Education, Inc. pp. 146–179\. ISBN 978-0-13-461099-3.
8. ^ Alan Turing. "Digital computers applied to games". University of Southampton and King's College Cambridge. p. 2.
9. ^ Claude Shannon (1950). "Programming a Computer for Playing Chess" (PDF). Philosophical Magazine. 41 (314): 4. Archived from the original (PDF) on 2010-07-06.
10. ^ E. Berlekamp; J. H. Conway; R. Guy (1982). Winning Ways for your Mathematical Plays. Vol. I. Academic Press. ISBN 0-12-091101-9.
E. Berlekamp; J. H. Conway; R. Guy (1982). Winning Ways for your Mathematical Plays. Vol. II. Academic Press. ISBN 0-12-091102-7.

## References

[edit]

* Albert, Michael H.; Nowakowski, Richard J.; Wolfe, David (2007). Lessons in Play: An Introduction to Combinatorial Game Theory. A K Peters Ltd. ISBN 978-1-56881-277-9.
* Beck, József (2008). Combinatorial games: tic-tac-toe theory. Cambridge University Press. ISBN 978-0-521-46100-9.
* Berlekamp, E.; Conway, J. H.; Guy, R. (1982). Winning Ways for your Mathematical Plays: Games in general. Academic Press. ISBN 0-12-091101-9. 2nd ed., A K Peters Ltd (2001–2004), ISBN 1-56881-130-6, ISBN 1-56881-142-X
* Berlekamp, E.; Conway, J. H.; Guy, R. (1982). Winning Ways for your Mathematical Plays: Games in particular. Academic Press. ISBN 0-12-091102-7. 2nd ed., A K Peters Ltd (2001–2004), ISBN 1-56881-143-8, ISBN 1-56881-144-6.
* Berlekamp, Elwyn; Wolfe, David (1997). Mathematical Go: Chilling Gets the Last Point. A K Peters Ltd. ISBN 1-56881-032-6.
* Bewersdorff, Jörg (2021). Luck, Logic and White Lies: The Mathematics of Games (2nd ed.). A K Peters/CRC Press. doi:10.1201/9781003092872. ISBN 978-1-003-09287-2. See especially sections 21–26.
* Conway, John Horton (1976). On Numbers and Games. Academic Press. ISBN 0-12-186350-6. 2nd ed., A K Peters Ltd (2001), ISBN 1-56881-127-6.
* Robert A. Hearn; Erik D. Demaine (2009). Games, Puzzles, and Computation. A K Peters, Ltd. ISBN 978-1-56881-322-6.

## External links

[edit]

* List of combinatorial game theory links at the homepage of David Eppstein
* An Introduction to Conway's games and numbers by Dierk Schleicher and Michael Stoll
* Combinational Game Theory terms summary by Bill Spight
* Combinatorial Game Theory Workshop, Banff International Research Station, June 2005

* v
* t
* e

Game theory

* Glossary
* Game theorists
* Games

Traditional game theory

| Definitions|

* Asynchrony
* Bayesian regret
* Best response
* Bounded rationality
* Cheap talk
* Coalition
* Complete contract
* Complete information
* Complete mixing
* Confrontation analysis
* Conjectural variation
* Contingent cooperator
* Coopetition
* Cooperative game theory
* Dynamic inconsistency
* Escalation of commitment
* Farsightedness
* Game semantics
* Hierarchy of beliefs
* Imperfect information
* Incomplete information
* Information set
* Move by nature
* Mutual knowledge
* Non-cooperative game theory
* Non-credible threat
* Outcome
* Perfect information
* Perfect recall
* Ply
* Preference
* Rationality
* Sequential game
* Simultaneous action selection
* Spite
* Strategic complements
* Strategic dominance
* Strategic form
* Strategic interaction
* Strategic move
* Strategy
* Subgame
* Succinct game
* Topological game
* Tragedy of the commons
* Uncorrelated asymmetry

|

Equilibrium
concepts|

* Backward induction
* Bayes correlated equilibrium
* Bayesian efficiency
* Bayesian game
* Bayesian Nash equilibrium
* Berge equilibrium
* Bertrand–Edgeworth model
* Coalition-proof Nash equilibrium
* Core
* Correlated equilibrium
* Cursed equilibrium
* Edgeworth price cycle
* Epsilon-equilibrium
* Gibbs equilibrium
* Incomplete contracts
* Inequity aversion
* Individual rationality
* Iterated elimination of dominated strategies
* Markov perfect equilibrium
* Mertens-stable equilibrium
* Nash equilibrium
* Open-loop model
* Pareto efficiency
* Payoff dominance
* Perfect Bayesian equilibrium
* Price of anarchy
* Program equilibrium
* Proper equilibrium
* Quantal response equilibrium
* Quasi-perfect equilibrium
* Rational agent
* Rationalizability
* Rationalizable strategy
* Satisfaction equilibrium
* Self-confirming equilibrium
* Sequential equilibrium
* Shapley value
* Strong Nash equilibrium
* Subgame perfect equilibrium
* Trembling hand equilibrium

Strategies|

* Appeasement
* Bid shading
* Cheap talk
* Collusion
* Commitment device
* De-escalation
* Deterrence
* Escalation
* Fictitious play
* Focal point
* Grim trigger
* Hobbesian trap
* Markov strategy
* Max-dominated strategy
* Mixed strategy
* Pure strategy
* Tit for tat
* Win–stay, lose–switch

Games|

* All-pay auction
* Battle of the sexes
* Nash bargaining game
* Bertrand competition
* Blotto game
* Centipede game
* Coordination game
* Cournot competition
* Deadlock
* Dictator game
* Trust game
* Diner's dilemma
* Dollar auction
* El Farol Bar problem
* Electronic mail game
* Gift-exchange game
* Guess 2/3 of the average
* Keynesian beauty contest
* Kuhn poker
* Lewis signaling game
* Matching pennies
* Obligationes
* Optional prisoner's dilemma
* Pirate game
* Prisoner's dilemma
* Public goods game
* Rendezvous problem
* Rock paper scissors
* Stackelberg competition
* Stag hunt
* Traveler's dilemma
* Ultimatum game
* Volunteer's dilemma
* War of attrition

Theorems|

* Arrow's impossibility theorem
* Aumann's agreement theorem
* Brouwer fixed-point theorem
* Competitive altruism
* Folk theorem
* Gibbard–Satterthwaite theorem
* Gibbs lemma
* Glicksberg's theorem
* Kakutani fixed-point theorem
* Kuhn's theorem
* One-shot deviation principle
* Prim–Read theory
* Rational ignorance
* Rational irrationality
* Sperner's lemma
* Zermelo's theorem

Subfields|

* Algorithmic game theory
* Behavioral game theory
* Behavioral strategy
* Compositional game theory
* Contract theory
* Drama theory
* Graphical game theory
* Heresthetic
* Mean-field game theory
* Negotiation theory
* Quantum game theory
* Social software

Key people|

* Albert W. Tucker
* Alvin E. Roth
* Amos Tversky
* Antoine Augustin Cournot
* Ariel Rubinstein
* David Gale
* David K. Levine
* David M. Kreps
* Donald B. Gillies
* Drew Fudenberg
* Eric Maskin
* Harold W. Kuhn
* Herbert Simon
* Herbert Scarf
* Hervé Moulin
* Jean Tirole
* Jean-François Mertens
* Jennifer Tour Chayes
* Ken Binmore
* Kenneth Arrow
* Leonid Hurwicz
* Lloyd Shapley
* Martin Shubik
* Melvin Dresher
* Merrill M. Flood
* Olga Bondareva
* Oskar Morgenstern
* Paul Milgrom
* Peyton Young
* Reinhard Selten
* Robert Aumann
* Robert Axelrod
* Robert B. Wilson
* Roger Myerson
* Samuel Bowles
* Suzanne Scotchmer
* Thomas Schelling
* William Vickrey

Combinatorial game theory

| Core
concepts|

* Combinatorial explosion
* Determinacy
* Disjunctive sum
* First-player and second-player win
* Game complexity
* Game tree
* Impartial game
* Misère
* Partisan game
* Solved game
* Sprague–Grundy theorem
* Strategy-stealing argument
* Zugzwang

|

Games|

* Chess
* Chomp
* Clobber
* Cram
* Domineering
* Hackenbush
* Nim
* Notakto
* Subtract a square
* Sylver coinage
* Toads and Frogs

Mathematical
tools|

* Mex
* Nimber
* On Numbers and Games
* Star
* Surreal number
* Winning Ways for Your Mathematical Plays

Search
algorithms|

* Alpha–beta pruning
* Expectiminimax
* Minimax
* Monte Carlo tree search
* Negamax
* Paranoid algorithm
* Principal variation search

Key people|

* Claude Shannon
* John Conway
* John von Neumann

Evolutionary game theory

| Core
concepts|

* Bishop–Cannings theorem
* Evolution and the Theory of Games
* Evolutionarily stable set
* Evolutionarily stable state
* Evolutionarily stable strategy
* Replicator equation
* Risk dominance
* Stochastically stable equilibrium
* Weak evolutionarily stable strategy

|

Games|

* Chicken
* Stag hunt

Applications|

* Cultural group selection
* Fisher's principle
* Mobbing
* Terminal investment hypothesis

Key people|

* John Maynard Smith
* Robert Axelrod

Mechanism design

| Core
concepts|

* Algorithmic mechanism design
* Bayesian-optimal mechanism
* Incentive compatibility
* Market design
* Monotonicity
* Participation constraint
* Revelation principle
* Strategyproofness
* Vickrey–Clarke–Groves mechanism

|

Theorems|

* Myerson–Satterthwaite theorem
* Revenue equivalence

Applications|

* Digital goods auction
* Knapsack auction
* Truthful cake-cutting

Other topics

* Bertrand paradox
* Chainstore paradox
* Computational complexity of games
* Helly metric
* Multi-agent system
* PPAD-complete

* Mathematics portal
* Commons
* WikiProject
* Category

Authority control databases: National |

* Germany

|

*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template