Combinatorial Game Theory

Combinatorial game theory (CGT) is a mathematical theory that can solve "sums of games", including difficult Go endgame problems. CGT deals with exact counting and determining the values of moves, which can be much more complicated than one might think. This theory has a branch called thermography, which is useful for playing endgames well with only a moderate amount of analysis. It also clarifies the meaning of sente and gote.

My Group's Research related to Combinatorial Game Theory

Our research interest is in efficient algorithms for combinatorial games. Some highlights: solving 5x5 Amazons and 6x5 Amazons; developing Decomposition Search and solving Go endgame puzzles as in the Berlekamp/Wolfe book; the first implementation of generalized thermography; developing Temperature Discovery Search (TDS) and TDS+, the first general forward search algorithms to compute or approximate the temperature of complex subgames.

• Generalized Thermography
• Decomposition Search
• Sums of Hot Games
• Temperature Discovery Search and TDS+
• Also see:
  • Some of our talks on CGT topics
  • Amazons
  • Computer Go
  • NoGo

Books on CGT

• Combinatorial Game Theory, Aaron Siegel, AMS 2013.
• Lessons in Play, AK Peters 2006.
• On Numbers and Games, Conway 1976.
• Winning Ways, Berlekamp, Conway and Guy, 1982.
• Mathematical Go: Chilling Gets the Last Point, Berlekamp and Wolfe, AK Peters 1994.
• Games of No Chance, Cambridge University Press 1996.
• More Games of No Chance, Cambridge University Press 2002.
• Games of no Chance 3, Cambridge University Press 2009.
• Games of No Chance 4, Cambridge University Press 2015.
• Games of No Chance 5, Cambridge University Press 2019.

CGT on the Internet

• People:
  • Berlekamp, Conway and Guy, the founders of Combinatorial Game Theory and authors of Winning Ways:
    • Richard Guy wikipedia article, homepage, turned 100 in 2016.
    • Elwyn Berlekamp homepage, wikipedia article.
    • John Conway wikipedia article.
  • Aviezri Fraenkel homepage and wikipedia article
  • Richard Nowakowski homepage and interview
• Wikipedia CGT introduction, references, etc.
• Kyle Burke's blog on CGT
• CGT group on Facebook
• Aaron Siegel's CGSuite is a very powerful open-source program for research in combinatorial game theory.
• David Wolfe has written a C library for combinatorial games and late Go endgames, which is used in our program Explorer to solve Go endgames. David's combinatorial game theory page has more good links.
• The combinatorial game theory page of David Eppstein features an overview on combinatorial game theory and many good links.