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):
- Triangulation
games: A variety of geometric games involving the construction,
transformation, or marking of the edges of a planar triangulation.
We give polynomial-time winning strategies in several cases.
- Tetris:
The classic computer game in which tetrominoes (pieces made up of
4 unit squares) fall one at a time into a rectangular board, the player
can slide the piece left or right during the fall, and any completely
filled rows are erased.
We prove that the offline (perfect-information) version with a
generalized board is NP-complete under many variations on the rules
and goal of the game.
- Clobber:
A recently invented two-player perfect-information game in which
players alternate capturing an opponent's stone with a horizontally or
vertically adjacent stone of theirs, and the goal is to move last.
We analyze the solitaire version of Clobber where one player controls
both sides, and the goal is to remove as many stones as possible.
- Sliding blocks
and NCL: Sliding-block puzzles consist of a collection of
rectangular blocks in a rectangular box, and the goal is to move one
piece to a particular location. We prove that these puzzles are
PSPACE-complete even for 1-by-2 blocks, and when the goal is just to
move one piece at all. We also prove several other puzzles
PSPACE-complete using a general model called Nondeterministic Constraint
Logic.
- Pushing blocks:
Puzzles involving a robot walking around in a square
grid, pushing square-block obstacles subject to various rules, in order
to reach a specified goal position.
- Clickomania:
A puzzle game in which the player clicks on a connected group of two
or more blocks of a common color, and blocks above fall down to take
their place. The goal is to remove as many blocks as possible.
- Phutball:
A two-player game by Conway involving one black stone (the ball)
and several white stones placed on a grid. In each turn, a player can
drop a white stone on an empty grid point, or "kick" the black stone
multiple times over sequences of white stones (horizontally,
vertically, or diagonally) and remove those white stones.
We analyze the complexity of deciding "mate in 1",
which is a combinatorial puzzle.
- Moving coins:
A wide variety of coin-sliding and coin-moving puzzles can be solved
in polynomial time, leading to several new puzzles that are difficult
for humans to solve but are guaranteed to be solvable by algorithmic
methods.
- Black box
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.