Playing Games with Algorithms: Algorithmic Combinatorial Game Theory

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.