Editing Game theory (section)

=== Combinatorial games ===
<!-- visible anchor to link to, for example at "Solving chess" -->

Games in which the difficulty of finding an optimal strategy stems from the multiplicity of possible moves are called combinatorial games. Examples include chess and [[Go (game)|Go]]. Games that involve [[Perfect information|imperfect information]] may also have a strong combinatorial character, for instance [[backgammon]]. There is no unified theory addressing combinatorial elements in games. There are, however, mathematical tools that can solve some particular problems and answer some general questions.<ref name="Bewersdorff2005" />

Games of perfect information have been studied in [[combinatorial game theory]], which has developed novel representations, e.g. [[surreal numbers]], as well as [[Combinatorics|combinatorial]] and [[Abstract algebra|algebraic]] (and [[Strategy stealing argument|sometimes non-constructive]]) proof methods to [[Solved game|solve games]] of certain types, including "loopy" games that may result in infinitely long sequences of moves. These methods address games with higher combinatorial complexity than those usually considered in traditional (or "economic") game theory.<ref>{{citation |last1=Albert |first1=Michael H. |author1-link=Michael H. Albert |last2=Nowakowski |first2=Richard J. |last3=Wolfe |first3=David |isbn=978-1-56881-277-9 |publisher=A K Peters Ltd |title=Lessons in Play: In Introduction to Combinatorial Game Theory |year=2007 |pages=3–4}}</ref><ref>{{cite book |last=Beck |first=József |author-link=József Beck |isbn=978-0-521-46100-9 |publisher=Cambridge University Press |title=Combinatorial Games: Tic-Tac-Toe Theory |title-link=Combinatorial Games: Tic-Tac-Toe Theory |year=2008 |pages=[https://archive.org/details/combinatorialgam00jbec/page/n15 1]–3}}</ref> A typical game that has been solved this way is [[Hex (board game)|Hex]]. A related field of study, drawing from [[computational complexity theory]], is [[game complexity]], which is concerned with estimating the computational difficulty of finding optimal strategies.<ref>{{citation |first1=Robert A. |last1=Hearn|author1-link=Bob Hearn |first2=Erik D. |last2=Demaine |title=Games, Puzzles, and Computation |title-link= Games, Puzzles, and Computation |year=2009 |publisher=A K Peters, Ltd. |isbn=978-1-56881-322-6}}</ref>

Research in [[artificial intelligence]] has addressed both perfect and imperfect information games that have very complex combinatorial structures (like chess, go, or backgammon) for which no provable optimal strategies have been found. The practical solutions involve computational heuristics, like [[alpha–beta pruning]] or use of [[artificial neural network]]s trained by [[reinforcement learning]], which make games more tractable in computing practice.<ref name="Bewersdorff2005">{{cite book |author=Jörg Bewersdorff |title=Luck, logic, and white lies: the mathematics of games |year=2005 |publisher=A K Peters, Ltd. |isbn=978-1-56881-210-6 |pages=ix–xii |chapter=31 |author-link=Jörg Bewersdorff }}</ref><ref name="Jones2008">{{cite book |first=M. Tim |last=Jones |title=Artificial Intelligence: A Systems Approach |year=2008 |publisher=Jones & Bartlett Learning |isbn=978-0-7637-7337-3 |pages=106–118}}</ref>