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.

Introduction

Many classic games are known to be computationally intractable (assuming P ≠ NP): one-player puzzles are often NP-complete (for instance Minesweeper) or PSPACE-complete (Rush Hour), and two-player games are often PSPACE-complete (Othello) or EXPTIME-complete (Checkers, Chess, and Go). Surprisingly, many seemingly simple puzzles and games are also hard. Other results are positive, proving that some games can be played optimally in polynomial time. In some cases, particularly with one-player puzzles, the computationally tractable games are still interesting for humans to play.

We begin by reviewing some basics of Combinatorial Game Theory in Section 2, which gives tools for designing algorithms, followed by reviewing the relatively new theory of Constraint Logic in Section 3, which gives tools for proving hardness.