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