Name
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. 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. |
Year | DOI | Venue |
|---|---|---|
2001 | 10.1007/3-540-44683-4_3 | mathematical foundations of computer science |
Keywords | DocType | Volume |
computational intractability result,algorithmic result,complexity theory,combinatorial game theory,ideal play,perfect-information game,general background,polynomial-time algorithm,clean problem,combinatorial game,algorithmic combinatorial game theory | Conference | cs.CC/0106019 |
ISSN | ISBN | Citations |
0302-9743 | 3-540-42496-2 | 40 |
PageRank | References | Authors |
6.43 | 65 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Erik D. Demaine | 1 | 4624 | 388.59 |
| Robert A. Hearn | 2 | 169 | 20.52 |