1. Introduction

All our games are two-player perfect-information games (no hidden information) without chance moves (no dice). Outcome is (lose, win) or (draw, draw) for the two players, who play alternately. We assume throughout normal play, i.e., the player making the last move wins and his opponent loses, unless misere play is specified, where the outcome is reversed. A draw is a dynamic tie, that is, a position from which neither player can force a win, but each has a nonlosing next move.

As we progress from the easy games to the more complex ones, we will develop some understanding of the poset of tractabilities and efficiencies of game strategies: whereas, in the realm of existential questions, tractabilities and efficiencies are by and large linearly ordered, from polynomial to exponential, for problems with an unbounded number of alternating quantifiers, such as games, the notion of a "tractable" or "efficient" computation is much more complex. (Which is more tractable: a game that ends after four moves, but it's undecidable who wins [Rabin 1957], or a game that takes an Ackermann number of moves to finish but the winner can play randomly, having to pay attention only near the end [Fraenkel, Loebl and Nesetfil 1988]?)