Paper by Martin L. Demaine

Reference:

Erik D. Demaine, Martin L. Demaine, and David Eppstein, “Phutball Endgames are Hard”, in More Games of No Chance, edited by R. J. Nowakowski, 2002, pages 351–360, Cambridge University Press. Collection of papers from the MSRI Combinatorial Game Theory Research Workshop, Berkeley, California, July 24–28, 2000.

Abstract:

We show that, in John Conway's board game Phutball (or Philosopher's Football), it is NP-complete to determine whether the current player has a move that immediately wins the game. In contrast, the similar problems of determining whether there is an immediately winning move in checkers, or a move that kings a man, are both solvable in polynomial time.

Comments:

This paper is also available as arXiv:cs.CC/0008025 of the Computing Research Repository (CoRR).

The paper is also available from the book's website as http://www.msri.org/publications/books/Book42/files/dephut.ps.gz.

Length:

The paper is 9 pages.

Availability:

The paper is available in PostScript (180k) and gzipped PostScript (31k).

See information on file formats.

[Google Scholar search]