Algorithmic Combinatorial Game Theory
Erik D. Demaine & Bob Hearn
People have wiled away their spare time with puzzles and games for centuries.
From the lightning games of chess played in sidewalk cafes to hours of
twisting and turning of Rubik's Cubes, many have struggled to ``solve''
these games and puzzles well. In the field of algorithmic combinatorial
game theory [Dem01], we are interested in a fundamental, systematic
understanding of solutions to these games and puzzles. We are motivated
by the inherent appeal of the games themselves, and aim to apply techniques
from theoretical computer science to unlock their mysteries. Our approach
is combinatorial, algorithmic, and complexity-theoretic. We seek to find
efficient algorithms for these games, or proofs of fundamental computational
hardness that help to explain the reason that these games can be so difficult.
In various collaborations, we have analyzed the computational complexity
of several combinatorial games and puzzles:
- Tetris [BDH+04]. One of the flagship products of
the Nintendo game system, Tetris is one of the most popular computer
games that has ever been invented. We have formalized the offline
Tetris problem, in which the player is presented (in advance) with
a sequence of Tetris pieces, and an initial gameboard, and attempts
to place the pieces within the gameboard to clear as many rows as possible
while playing the sequence. We have shown that this problem is NP-complete,
and furthermore is deeply inapproximable. (For example, given a sequence
of p pieces, it is hard to approximate to within a factor of
p1 −ε the number of rows that can
be cleared using the given sequence.) We have also proved that a number
of other natural Tetris objectives are NP-hard: maximizing the number
of pieces placed without losing, minimizing the height of the highest
filled square in the gameboard, or maximizing the number of Tetrises
(i.e., the number of times that four rows are simultaneously cleared).
- Sliding blocks and Nondeterministic Constraint Logic [HD05].
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 × 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.
- Clobber [DDF03] 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. Specifically, we give exact bounds on the minimum number
of stones that can be reached for an arbitrary m × n
rectangular checkerboard. Surprisingly, for m, n > 1,
all but one or two of the stones can be removed, whereas for m = 1
or n = 1, only about three quarters of the stones can
- Geometric games on triangulations [ABD+05]. We give
polynomial-time winning strategies for a wide variety of games involving
the construction, transformation, or marking of the edges of a planar
- Pushing blocks [DDHO03, DHH02]. There are many 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. We have proved essentially all variants to be NP-hard, and
a few variants to be even PSPACE-complete.
- Phutball [DDE02]. A classic 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 prove that it is NP-hard to decide ``mate in
1'', which is a combinatorial puzzle.
- Clickomania [BDD+02]. A computer 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. We prove that this puzzle is NP-complete
in general, but polynomially solvable for the cases of a single row
- Moving coins [DDV02]. 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.
The complexity of many games and puzzles remains completely unstudied,
and others remain challenging open problems. See [Dem01] for a survey.
- Oswin Aichholzer, David Bremner, Erik D. Demaine, Ferran Hurtado,
Evangelos Kranakis, Hannes Krasser, Suneeta Ramaswami, Saurabh Sethia,
and Jorge Urrutia. Games
on triangulations. Theoretical Computer Science, 343(1–2):42–71,
- Therese C. Biedl, Erik D. Demaine, Martin L. Demaine, Rudolf Fleischer,
Lars Jacobsen, and J. Ian Munro. The
complexity of Clickomania. In R. J. Nowakowski, editor, More
Games of No Chance, pp. 389–404, 2002.
- Ron Breukelaar, Erik D. Demaine, Susan Hohenberger, Hendrik Jan Hoogeboom,
Walter A. Kosters, and David Liben-Nowell. Tetris
is hard, even to approximate. International Journal of Computational
Geometry and Applications, 14(1–2):41–68, 2004.
- Erik D. Demaine. Playing
games with algorithms: Algorithmic combinatorial game theory. In
Proceedings of the 26th Symposium on Mathematical Foundations in
Computer Science, LNCS 2136, pp. 18–32, Marianske Lazne,
Czech Republic, August 2001. Full paper available as arXiv:cc.CC/0106019.
- Erik D. Demaine, Martin L. Demaine, and David Eppstein. Phutball
endgames are NP-hard. In R. J. Nowakowski, editor, More Games
of No Chance, pp. 351–360, 2002.
- Erik D. Demaine, Martin L. Demaine, and Rudolf Fleischer. Solitaire
Clobber. Theoretical Computer Science, 313(3):325–338,
- Erik D. Demaine, Martin L. Demaine, Michael Hoffmann, and Joseph
blocks is hard. Computational Geometry: Theory and Applications,
26(1):21–36, August 2003.
- Erik D. Demaine, Martin L. Demaine, and Helena Verrill. Coin-moving
puzzles. In R. J. Nowakowski, editor, More Games of No Chance,
pp. 405–431. 2002.
- Erik D. Demaine, Robert A. Hearn, and Michael Hoffmann. Push-2-F
is PSPACE-complete. In Proceedings of the 14th Canadian Conference
on Computational Geometry, pp. 31–35, Lethbridge, Canada,
- Robert A. Hearn and Erik D. Demaine. PSPACE-completeness
of sliding-block puzzles and other problems through the nondeterministic
constraint logic model of computation. Theoretical Computer
Science, 343(1–2):72–96, October 2005.