erikdemaine.org Open in urlscan Pro
128.52.131.233  Public Scan

Form analysis
0 forms found in the DOM

Text Content

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:

 * David Eppstein has an excellent page on combinatorial game theory.
 * Jeff Erickson has another excellent page on mathematical games, toys, and
   puzzles.
 * David Wolfe's page on combinatorial game theory includes his software,
   Gamesman's Toolkit, which implements the mathematics of two-player games in
   Winning Ways. The page also includes Richard K. Guy's paper, ``Unsolved
   Problems in Combinatorial Game Theory''

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.



Last updated July 19, 2021 by Erik Demaine. — Accessibility