Research Abstracts - 2007

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 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.

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 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 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 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 be removed.
• 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 triangulation.
• 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 or column.
• 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.

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 Liben-Nowell. 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 NP-hard. 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. Coin-moving 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. Push-2-F is PSPACE-complete. 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. 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.