Erik Demaine's Combinatorial Games Page

Recently I have become quite interested in combinatorial game theory, particularly algorithmic combinatorial game theory. In both settings, the object of interest is a combinatorial game, which usually involves complete information, with no hidden cards and no randomness--a pure strategy game. In general, combinatorial game theory is a suite of techniques for analyzing such games. The algorithmic side asks for efficient algorithms for playing games optimally, or for computational intractability results suggesting that no such efficient algorithms exist.

Survey Paper

I recently completed a survey paper about results in algorithmic combinatorial game theory, plus a short introduction to combinatorial game theory. Two versions of ``Playing Games with Algorithms: Algorithmic Combinatorial Game Theory'' are available: the full draft (recommended), and a shorter version appearing in the 26th Symposium on Mathematical Foundations in Computer Science.

How Many Players?

One main categorization of combinatorial games is how many players are involved in play. There is a large body of work on two-player games. In particular, the book Winning Ways by Berlekamp, Conway, and Guy, builds a beautiful theory for classifying games.

Another type of combinatorial game is a one-player game, also called a puzzle. Many games in real life are essentially one-player. One-player games also arise naturally when examing a portion of a two-player game.

The final main type of combinatorial game is a zero-player game. The main example of such a game is a cellular automaton such as John H. Conway's Game of Life.

My Research

I am particularly excited by one-player combinatorial games, and would like to advocate their study. Here are some combinatorial puzzles we have analyzed (more information to come soon): You may also be interested in some puzzles we have designed for fun.

References

(See also the survey paper mentioned at the top of this page.)

There are several other webpages on the topic of combinatorial games:

Off the web, the classic and most complete reference on combinatorial game theory is Winning Ways, by Elwyn R. Berlekamp, John H. Conway, and Richard K. Guy. The two-volume book was published by Academic Press (London) in 1982. Unfortunately, it is currently out-of-print, but work is underway to publish a second edition. Another excellent reference on combinatorial game theory, with a more formal mathematical slant, is On Numbers and Games by John H. Conway, also published by Academic Press (London), 1976.

Last updated November 28, 2010 by Erik Demaine.