Paper by Erik D. Demaine
- Erik D. Demaine, “Playing Games with Algorithms: Algorithmic Combinatorial Game Theory”, in Proceedings of the 26th Symposium on Mathematical Foundations in Computer Science (MFCS 2001), Lecture Notes in Computer Science, volume 2136, Marianske Lazne, Czech Republic, August 27–31, 2001, pages 18–32.
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. 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
- This paper is also available from the electronic LNCS volume as http://link.springer.de/link/service/series/0558/papers/2136/21360018.pdf.
- The paper is \copyright Springer-Verlag.
- The paper is 15 pages.
- The paper is available in PostScript (272k) and gzipped PostScript (84k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- AlgGameTheory_GONC3 (Playing Games with Algorithms: Algorithmic Combinatorial Game Theory)
- Related webpages:
- Combinatorial Games
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated January 4, 2022 by