Mathematics Atlas

How Proof Is Made
Sign In
Text size
100%
Theme
Branches of Mathematic

Combinatorial Game Theory

Also Known As CGT
Combinatorics and Graph Theory

Combinatorial game theory is the branch of mathematics that analyzes perfect information games with no chance element, in which two players alternate moves and the game ends in finitely many moves. John Conway developed its foundations, together with the surreal numbers, while studying the endgames of Go at Cambridge in the early 1970s, publishing the theory as On Numbers and Games in 1976, and later, with Elwyn Berlekamp and Richard Guy, as the two volume Winning Ways for Your Mathematical Plays in 1982.

Facts
Central Question
How can a perfect information game with no chance element be assigned a well defined value, so that games can be added, compared and analyzed as a single algebraic system? 2
Key Debate
Whether combinatorial game theory, by design, restricts itself to perfect information games with no chance element, so results like the Sprague-Grundy theorem and the surreal numbers that hold there do not obviously extend to the games (poker, most video games, most real economic competition) that involve hidden information or chance, a limitation some regard as making the field a beautiful special case rather than a general theory of games, and others regard as the necessary price of getting exact, provable answers instead of the approximate equilibrium concepts classical game theory settles for. 2
Classification
Pure or Applied
Both / Interdisciplinary 1
Learn More
How a Board Game Produced a New Kind of Number

This article records tradition as it has been passed down and reported. Its sources are not yet part of the atlas's verified catalogue.

In the early 1970s, the mathematician John Conway spent a lot of time at Cambridge watching strong Go players finish their games. He was not trying to get better at Go. He was trying to understand something odd about how those endgames worked: late in a game of Go, the board effectively splits into several small, separate local fights, and a player has to decide which fight to play in next. Conway noticed that each of these local positions could be compared to the others in a way that looked exactly like comparing numbers, even though nothing about a Go endgame looks like arithmetic on the surface.

He followed the idea all the way down. If a game position could be treated as a kind of number, what happens if you define numbers themselves as game positions, built recursively from earlier, simpler positions? The answer turned out to be a genuinely new number system. Conway's construction did not just reproduce the ordinary integers and fractions. It also generated infinite numbers, infinitesimal numbers smaller than any positive real number yet still greater than zero, and vast further reaches beyond both. Donald Knuth later gave this construction a name, the surreal numbers, in a short 1974 book written as a dialogue between two students discovering the idea for themselves.

Conway published the full theory himself in 1976, in a book called On Numbers and Games, and the broader framework it introduced, treating games as mathematical objects with their own values, sums and comparisons, became known as combinatorial game theory. It is a different kind of game theory from the one John von Neumann and John Nash had built decades earlier for economics and strategic decision making. Von Neumann and Nash studied games with hidden information or simultaneous choices, where the interesting question is what a rational opponent will do. Conway's games have no hidden information and no element of chance at all, Go, checkers, Nim, and the interesting question is instead what a position is worth, treated as a strange kind of arithmetic in its own right.

Conway went on to a career that touched an unusual number of separate fields, from finite group theory to the invention of the cellular automaton called the Game of Life, but he described On Numbers and Games as the work that gave him a system, not just a scattering of results, and its origin remained the same throughout: a mathematician watching a board game closely enough to see the numbers hiding inside it.

Connections

In Branch

Combinatorial game theory grew out of, and remains a distinct part of, the wider study of game theory that von Neumann and Nash founded; it does not itself originate the whole game-theory branch.

Source MacTutor History of Mathematics Archive

Includes

Source Conway, On Numbers and Games (1976)John H. Conway
Source Mathematical Game
Source Wikipedia: Patrick Michael Grundy
Source Wikipedia: Roland Sprague
Source Conway, On Numbers and Games (1976)John H. Conway

Long-Form Articles

In the Other Atlases

Originated In

Also in Sport and Games Atlas: where this subject originated.

Source Conway, On Numbers and Games (1976)John H. Conwaytier 1
Sources
1. Wikipedia: Combinatorial Game Theory
Wikimedia Foundation
  • Lead section
    typically studies sequential games with perfect information
  • Lead section, pure or applied classification
    Combinatorial game theory is a branch of mathematics and theoretical computer science that typically studies sequential games with perfect information.
View the Source
2. Conway, On Numbers and Games (1976)
John H. Conway, Academic Press, 1976
MacTutor History of Mathematics Archive
University of St Andrews, School of Mathematics and StatisticsIn Branch: Game Theory, https://mathshistory.st-andrews.ac.uk/Biographies/Conway/View the Source
Wikipedia: Roland Sprague
Includes: Roland Sprague, Lead
Quote, Includes: Roland Sprague, Lead
Sprague is known for his contributions to recreational mathematics, especially the Sprague-Grundy function and its application to combinatorial games, which Sprague and Patrick Michael Grundy discovered independently in 1935 and 1939 respectively.
View the Source
Wikipedia: Patrick Michael Grundy
Includes: Patrick Michael Grundy, Lead
Quote, Includes: Patrick Michael Grundy, Lead
He was one of the eponymous co-discoverers of the Sprague-Grundy function and its application to the analysis of a wide class of combinatorial games. == Biography == Grundy received his secondary education from Malvern College, to which he had obtained a Major Scholarship in 1931, and from which he
View the Source
Mathematical Game
Includes: Mathematical Game, Lead paragraph
Quote, Includes: Mathematical Game, Lead paragraph
For example, even though the rules of Mancala are relatively basic, the game can be rigorously analyzed through the lens of combinatorial game theory.
View the Source
Comments (0)
No comments yet. Be the first to share a thought.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.