computer science


Combinatorial Games

Combinatorial games are two player, alternating play games with perfect information. Some familiar examples (almost) are chess, go, and reversi. With its frontiers touching both theoretical and applied computing, discrete mathematics, and algebra, the field of combinatorial game theory is an ideal one for student projects at all levels from fourth year through PhD research.

There is a broad, deep, and growing theory of combinatorial games whose foundations are laid in the famous book Winning Ways for your Mathematical Plays.

The open source software package CGSuite is an invaluable tool in working with combinatorial games. Its primary author is Aaron Siegel, but I continue to be involved in its development. A completely reworked version (1.0) of CGSuite is due to be released later this year (2011).

Of course, games are for playing, and one of the intriguing problems about combinatorial games in particular is how to develop clever game playing agents in the absence of significant domain knowledge (i.e. history) about the games. One of the most promising innovations in this area in recent years has been the development of Monte Carlo Tree Search. This has been particularly effective in increasing the strength of computer go players.

Coming soon: some game playing agents for you to pit your wits against.

Back to Michael Albert's personal page

Back to CS Home Page

This page is maintained by Michael Albert
Last modified: October 2011.