Combinatorial game theory

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. However, as mathematical techniques develop, the scope of analyzable games expands, and the boundaries of the field continue to evolve. 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.

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. Many real-world games remain too complex for complete analysis, though combinatorial methods have shown some success in the study of Go endgames. In combinatorial game theory, analyzing a position means finding the best sequence of moves for both players until the game ends, but this becomes extremely difficult for anything more complex than 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. 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. Tic-tac-toe continues to be used in teaching fundamental concepts of game AI design to computer science students.

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.

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.