1. Introduction

We continue our introduction to combinatorial games with a survey of impartial games. Most of this material can also be found in WW [Berlekamp et al. 1982], particularly pp. 81-116, and in ONAG [Conway 1976], particularly pp. 112-130. An elementary introduction is given in [Guy 1989]; see also [Fraenkel 1996a], pp. 13-42 in this volume.

This is the inductive step that proves the Sprague-Grundy theorem [Sprague 1935-36; Grundy 1939], which states that every position in an impartial game (or, which is the same, every impartial game) is equivalent to a nim-heap (see page 20ff. in Fraenkel's article in this volume).

2. Examples of Impartial Games

We all know that the game of Nim is played with several heaps of beans. A move is to select a heap, and to remove any positive number of beans from it, possibly the whole heap. Any position in Nim is therefore the sum of several one-heap Nim games. The value of a single heap of n beans is *n. It's easy to see how to win a game of Nim if there's only one (nonempty) heap: take the whole heap! But it's worth pausing for a moment to note exactly what your options are. They are to move to any smaller sized heap: they correspond exactly to the options in the definition of *n. It's also fairly easy to play well at two-heap Nim: if the heaps are unequal in size, remove enough beans from the larger to make the heaps equal.