Misère games and misere quotients
Aaron N. Siegel · 2019
These notes are based on a short course offered at the Weizmann Institute of Science in Rehovot, Israel, in November 2006. The notes include an introduction to impartial games, starting from the beginning; the basic misère quotient construction; a proof of the periodicity theorem; and statements of some recent results and open problems in the subject. Introduction This course is concerned with impartial combinatorial games , and in particular with misere play of such games. Loosely speaking, a combinatorial game is a two-player game with no hidden information and no chance elements. We usually impose one of two winning conditions on a combinatorial game: under normal play , the player who makes the last move wins, and under misère play , the player who makes the last move loses. We will shortly give more precise definitions. The study of combinatorial games began in 1902, with C. L. Bouton's published solution to the game of NIM [2]. Further progress was sporadic until the 1930s, when R. P. Sprague [17; 18] and P. M. Grundy [6] independently generalized Bouton's result to obtain a complete theory for normal-play impartial games. In a seminal 1956 paper [8], R. K. Guy and C. A. B. Smith introduced a wide class of impartial games known as octal games , together with some general techniques for analyzing them in normal play. Guy and Smith's techniques proved to be enormously powerful in finding normal-play solutions for such games, and they are still in active use today [4]. At exactly the same time (and, in fact, in exactly the same issue of the Proceedings of the Cambridge Philosophical Society ), Grundy and Smith published a paper on misere games [7]. They noted that misère play appears to be quite difficult, in sharp contrast to the great success of the Guy–Smith techniques. Despite these complications, Grundy remained optimistic that the Sprague– Grundy theory could be generalized in a meaningful way to misère play. These hopes were dashed in the 1970s, when Conway [3] showed that the Grundy–Smith complications are intrinsic. Conway's result shows that the most natural misereplay generalization of the Sprague–Grundy theory is hopelessly complicated, and is therefore essentially useless in all but a few simple cases.