
Algorithmic Combinatorial Game Theory
Erik D. Demaine & Bob Hearn
What
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 complexitytheoretic. 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.
Progress
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 NPcomplete,
and furthermore is deeply inapproximable. (For example, given a sequence
of p pieces, it is hard to approximate to within a factor of
p^{1 −ε} 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 NPhard: 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].
Slidingblock 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 PSPACEcomplete even for 1 × 2
blocks, and when the goal is just to move one piece at all. We also
prove several other puzzles PSPACEcomplete using a general model called
Nondeterministic Constraint Logic.
 Clobber [DDF03] A recently invented twoplayer perfectinformation
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
be removed.
 Geometric games on triangulations [ABD+05]. We give
polynomialtime winning strategies for a wide variety of games involving
the construction, transformation, or marking of the edges of a planar
triangulation.
 Pushing blocks [DDHO03, DHH02]. There are many puzzles
involving a robot walking around in a square grid, pushing squareblock
obstacles subject to various rules, in order to reach a specified goal
position. We have proved essentially all variants to be NPhard, and
a few variants to be even PSPACEcomplete.
 Phutball [DDE02]. A classic twoplayer 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 NPhard 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 NPcomplete
in general, but polynomially solvable for the cases of a single row
or column.
 Moving coins [DDV02]. A wide variety of coinsliding
and coinmoving 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.
Future
The complexity of many games and puzzles remains completely unstudied,
and others remain challenging open problems. See [Dem01] for a survey.
References
 [ABD+05]
 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,
October 2005.
 [BDD+02]
 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.
 [BDH+04]
 Ron Breukelaar, Erik D. Demaine, Susan Hohenberger, Hendrik Jan Hoogeboom,
Walter A. Kosters, and David LibenNowell. Tetris
is hard, even to approximate. International Journal of Computational
Geometry and Applications, 14(1–2):41–68, 2004.
 [Dem01]
 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.
 [DDE02]
 Erik D. Demaine, Martin L. Demaine, and David Eppstein. Phutball
endgames are NPhard. In R. J. Nowakowski, editor, More Games
of No Chance, pp. 351–360, 2002.
 [DDF04]
 Erik D. Demaine, Martin L. Demaine, and Rudolf Fleischer. Solitaire
Clobber. Theoretical Computer Science, 313(3):325–338,
February 2004.
 [DDHO03]
 Erik D. Demaine, Martin L. Demaine, Michael Hoffmann, and Joseph
O'Rourke. Pushing
blocks is hard. Computational Geometry: Theory and Applications,
26(1):21–36, August 2003.
 [DDV02]
 Erik D. Demaine, Martin L. Demaine, and Helena Verrill. Coinmoving
puzzles. In R. J. Nowakowski, editor, More Games of No Chance,
pp. 405–431. 2002.
 [DHH02]
 Erik D. Demaine, Robert A. Hearn, and Michael Hoffmann. Push2F
is PSPACEcomplete. In Proceedings of the 14th Canadian Conference
on Computational Geometry, pp. 31–35, Lethbridge, Canada,
August 2002.
 [HD05]
 Robert A. Hearn and Erik D. Demaine. PSPACEcompleteness
of slidingblock puzzles and other problems through the nondeterministic
constraint logic model of computation. Theoretical Computer
Science, 343(1–2):72–96, October 2005.

