Playing Games with Algorithms: Algorithmic Combinatorial Game Theory

Erik D. Demaine

LCS MIT

October 12,
4:15pm
refreshments at 3:45pm
2-338

ABSTRACT 

Combinatorial games lead to several interesting, clean problems in mathematics, algorithms, and complexity theory. A combinatorial game typically involves two players; other interesting cases include combinatorial puzzles, in which there is only one player, and cellular automata such as Conway's Game of Life, in which there are zero players. In a perfect-information combinatorial game, no randomness (e.g., dice) or privacy (e.g., hidden cards) is allowed: all players know all information about gameplay. The problem is thus purely strategic: how to best play the game against an ideal opponent.

A beautiful mathematical theory has been developed for analyzing such games, but many algorithmic problems remain open. Many classic games and puzzles, such as Minesweeper, Go, and Chess, are known to be computationally intractable, as well as several seemingly simple games. I will mention several such results I have been involved in: robot pushing-block puzzles such as Sokoban, a block-removal puzzle Clickomania, and Conway's game Philosopher's Football. More exciting results are positive, proving that some games can be played optimally by efficient (polynomial-time) algorithms. I will describe one main result in this area, a wide class of coin-sliding puzzles. Other still-open problems I will discuss include Conway's angel-devil problem, and a cat-and-mouse game whose computational reduction (in a particular sense) would prove that P does not equal NP.


Speaker's Contact Info: edemaine(at-sign)mit.edu


Return to seminar home page

Combinatorics Seminar, Mathematics Department, MIT, sara(at-sign)math.mit.edu

Page loaded on September 18, 2001 at 05:31 PM. Copyright © 1998-99, Sara C. Billey. All rights reserved.