Scenic Trails Ascending from Sea-Level Nim to Alpine Chess
Aviezri S. Fraenkel · 1997
Aim: To present a systematic development of part of the theory of combinatorial games from the ground up. Approach: Computational complexity. Combinatorial games are completely determined; the questions of interest are efficiencies of strategies. Methodology: Divide and conquer. Ascend from Nim to chess in small strides at a gradient that's not too steep. Presentation: Informal; examples of games sampled from various strategic viewing points along scenic mountain trails illustrate the theory. 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]?)