Two-Player Games

In this chapter we present the definitions and complexity proofs for TwoPlayer Constraint Logic, both the bounded and unbounded varieties.

Complexity Background. With two-player games, we are finally in territory familiar to classical game theory and combinatorial game theory. Twoplayer, perfect-information games are also the richest source of existing hardness results for games. In a two-player game, players alternate making moves, each trying to achieve some particular objective. The standard decision question is “does player X have a forced win from this position?”