Editing Combinatorial game theory (section)

{{Short description|Branch of game theory about two-player sequential games with perfect information}}
{{about|the theory of combinatorial games|the theory that includes games of chance and games of imperfect knowledge|Game theory}}
[[Image:Mathematicians playing Konane.jpg|thumb|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 game]]s with [[perfect information]]. Research in this field has primarily focused on two-player [[game]]s in which a ''position'' evolves through alternating ''moves'', each governed by well-defined rules, with the aim of achieving a specific winning condition. Unlike [[game theory|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.<ref>Lessons in Play, p. 3</ref> However, as mathematical techniques develop, the scope of analyzable games expands, and the boundaries of the field continue to evolve.<ref>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.</ref> 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.

[[Combinatorics|Combinatorial]] games include well-known examples such as [[chess]], [[draughts|checkers]], and [[Go (game)|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 set|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 puzzle]]s or [[cellular automaton|automata]], given that the strictest definitions of "game" imply the involvement of multiple participants.<ref name="AlgGameTheory">{{cite book
 | last1 = Demaine | first1 = Erik D. | author1-link = Erik Demaine
 | last2 = Hearn | first2 = Robert A. | author2-link = Bob Hearn
 | editor1-last = Albert | editor1-first = Michael H.
 | editor2-last = Nowakowski | editor2-first = Richard J.
 | arxiv = cs.CC/0106019
 | contribution = Playing games with algorithms: algorithmic combinatorial game theory
 | contribution-url = https://erikdemaine.org/papers/AlgGameTheory_GONC3/

 | pages = 3–56
 | publisher = Cambridge University Press
 | series = Mathematical Sciences Research Institute Publications
 | title = Games of No Chance 3
 | volume = 56
 | year = 2009}}</ref>

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 [[Solved game#Overview|weakly solved]], with perfect play by both sides leading to a draw; however, this result required a [[computer-assisted proof]].<ref>{{Cite journal| last1 = Schaeffer | first1 = J.| last2 = Burch | first2 = N.| last3 = Bjornsson | first3 = Y.| last4 = Kishimoto | first4 = A.| last5 = Muller | first5 = M.| last6 = Lake | first6 = R.| last7 = Lu | first7 = P.| last8 = Sutphen | first8 = S.| title = Checkers is solved| journal = [[Science (journal)|Science]]| volume = 317| issue = 5844| pages = 1518–1522| year = 2007| pmid = 17641166| doi = 10.1126/science.1144079| citeseerx = 10.1.1.95.5393| bibcode = 2007Sci...317.1518S| s2cid = 10274228}}</ref> Many real-world games remain too complex for complete analysis, though combinatorial methods have shown some success in the study of [[Go endgame]]s. 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.<ref>{{Cite journal |last1=Fraenkel |first1=Aviezri |title=Combinatorial Games: selected bibliography with a succinct gourmet introduction |journal=Games of No Chance 3 |volume=56 |pages=492 |year=2009}}</ref> 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.<ref>{{Cite news |url=http://www.newyorker.com/archive/1952/08/02/1952_08_02_018_TNY_CARDS_000236053
|title=The Talk of the Town - It |first1=Eugene F. |last1=Grant |first2=Rex |last2=Lardner |date=2 August 1952 |newspaper=[[The New Yorker]]}}</ref> [[Tic-tac-toe]] continues to be used in teaching fundamental concepts of [[game AI]] design to [[computer science]] students.<ref>{{cite book | last1 = Russell | first1 = Stuart | author1-link = Stuart J. Russell | last2 = Norvig | first2 = Peter | author2-link = Peter Norvig | contribution = Chapter 5: Adversarial search and games | edition = 4th | isbn = 978-0-13-461099-3 | pages = 146–179 | publisher = Pearson Education, Inc. | series = Pearson series in artificial intelligence | title = Artificial Intelligence: A Modern Approach | title-link = Artificial Intelligence: A Modern Approach | year = 2021}}</ref>