Higher Nimbers in Pawn Endgames on Large Chessboards
Noam D. Elkies · 2002
. We answer a question posed in [Elkies 1996] by constructing a class of pawn endgames onmXn boards that show the Nimbers *k for many large k. We do this by modifying and generalizing T.R. Dawson's “pawns game” [Berlekamp et al. 1982]. Our construction works for and n sufficiently large; on the basis of computational evidence we conjecture, but cannot yet prove, that the construction yields *k for all integers k. 1. Introduction In [Elkies 1996] we showed that certain chess endgames can be analyzed by the techniques of combinatorial game theory (CGT). We exhibited such endgames whose components show a variety of CGT values, including integers, fractions, and some infinite and infinitesimal values. Conspicuously absent were the values * k of Nim-heaps of size k > 1. Towards the end of [Elkies 1996] we asked whether any chess endgames, whether on the standard 8 x 8 chessboard or on larger rectangular boards, have components equivalent to *2, *4 and higher Nimbers. In the present paper we answer this question affirmatively by constructing a new class of pawn endgames on large boards that include * k for many large k , and conjecture — though we cannot yet prove — that all * k arise in this class. Our construction begins with a variation of a pawns game called “Dawson's Chess” in [Berlekamp et al. 1982]. In §3 we introduce this variation and show that, perhaps surprisingly, all quiescent (non-entailing) components of the modified game are equivalent to Nim-heaps (Theorem 1). We then determine the value of each such component, and characterize non-loony moves (Theorem 2). In § 4 we construct pawn endgames on large chessboards that incorporate those components. These endgames do not yet attain our aim, because the values determined in Theorem 2 are all 0 or *1. In §5 we modify one of our components to obtain *2. In §6 we further study components modified in this way, showing that they, too, are equivalent to Nim-heaps (Theorem 3). We conclude with the numerical evidence suggesting that all Nim-heaps can be simulated by components of pawn endgames on large rectangular chessboards.