Why some games are solved while others remain mathematically unreachable
In short: In the world of mathematics, a game is more than entertainment; it is a recursive structure of moves. While we can prove that perfect play in tic-tac-toe always ends in a draw, the sheer complexity of other games creates a frontier where human and computer logic still struggle to find the ultimate truth.
Combinatorial game theory (CGT) focuses on sequential games with perfect information, where every move and state is visible to both players. Unlike economic game theory, which incorporates probability and utility, CGT seeks to determine the existence of optimal strategies through rigorous mathematical structures. A core concept is the 'solved' game, where the outcome is known from the start. For example, tic-tac-toe is solved as a draw, and checkers was announced as weakly solved in 2007—a result requiring a computer-assisted proof showing that perfect play leads to a draw.
The field distinguishes between 'mathgames,' studied for theoretical exploration, and 'playgames,' played for competition. A foundational discovery in the 1930s was the Sprague–Grundy theorem, which proved that all impartial games (where both players have the same available moves, like Nim) are equivalent to 'nimbers.' This allows for massive unifications of different games into a single mathematical framework. During the 1960s and 1970s, Elwyn R. investigated partisan games, such as Blue–Red Hackenbush or Checkers, where move options differ between opponents. John H. Berlekamp, Richard K. Conway, and Guy pioneered the creation of surreal numbers for expressing game values.
Complexity remains a massive barrier. While CGT has successfully analyzed Go endgames, the full game of Go remains too complex for complete analysis. Chess is similarly daunting; Claude Shannon estimated its game-tree complexity at 10^120 (the Shannon number). While supercomputers have created 'tablebases' for endgames with seven pieces or fewer, the full game remains unsolved. CGT provides the tools to decompose these complexities—such as viewing Go endgames as sums of simpler, isolated positions—but the sheer scale of the game trees often exceeds current computational limits.
Opens the Intellect+ feed with this card first. Swipe up for the next one.
Sources
- Summary by Intellect · source: Combinatorial game theory
To cite this card, link to https://intellectplus.co.uk/app/science-combinatorial-game-theory.
How we source, check and correct cards: Editorial standards.
General information, not professional advice. Spotted an error? Flag the card or see corrections and complaints.
Intellect Plus is a visual educational discovery platform for exploring fascinating facts and ideas. Brain Food, Not Brain Rot. What is Intellect Plus?
Related
More in Social scientists · More in Science · Latest · A–Z · All topics
