Paper by Erik D. Demaine

Reference:

Erik D. Demaine and Robert A. Hearn, “Playing Games with Algorithms: Algorithmic Combinatorial Game Theory”, in Games of No Chance 3, edited by Michael H. Albert and Richard J. Nowakowski, Mathematical Sciences Research Institute Publications, volume 56, 2009, pages 3–56, Cambridge University Press.

Abstract:

Combinatorial games lead to several interesting, clean problems in algorithms and complexity theory, many of which remain open. The purpose of this paper is to provide an overview of the area to encourage further research. In particular, we begin with general background in Combinatorial Game Theory, which analyzes ideal play in perfect-information games, and Constraint Logic, which provides a framework for showing hardness. Then we survey results about the complexity of determining ideal play in these games, and the related problems of solving puzzles, in terms of both polynomial-time algorithms and computational intractability results. Our review of background and survey of algorithmic results are by no means complete, but should serve as a useful primer.

Comments:

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

Length:

The paper is 42 pages.

Availability:

The paper is available in PostScript (1283k), gzipped PostScript (496k), and PDF (506k).

See information on file formats.

[Google Scholar search]

Related papers:

AlgGameTheory_MFCS2001 (Playing Games with Algorithms: Algorithmic Combinatorial Game Theory)

Related webpages:

Combinatorial Games