Published online by Cambridge University Press: 30 May 2025
We show that partizan games admit canonical forms in misère play. The proof is a synthesis of Conway’s simplest form theorems for normal-play partizan games and misère-play impartial games. As an immediate application, we show that there are precisely 256 games born by day 2, and obtain a bound on the number of games born by day 3.
Disjunctive compounds of short combinatorial games have been studied for many years under a variety of assumptions. A structure theory for normal-play impartial games was established in the 1930s by the Sprague–Grundy theorem [Grundy 1939; Sprague 1935; 1937]. Every such game G is equivalent to a Nim-heap, and the size of this heap, known as the nim value of G, completely describes the behavior of G in disjunctive sums. The Sprague–Grundy theorem underpins virtually all subsequent work on impartial combinatorial games.
Decades later, Conway generalized the Sprague–Grundy theorem in two directions [Berlekamp et al. 2003; Conway 2001]. First, he showed that every partizan game G can be assigned a value that exactly captures its disjunctive behavior, and this value is represented by a unique simplest form for G. Conway’s game values are partizan analogues of nim values, and his simplest form theorem directly generalizes the Sprague–Grundy theorem.
Conway also introduced a misère-play analogue of the Sprague–Grundy theorem. He showed that every impartial game G is represented by a unique misère simplest form [Conway 2001]. Unfortunately, in misère play such simplifications tend to be weak, and as a result the canonical theory of misère games is less useful in practice than its normal-play counterparts.
In each case—normal-play impartial, normal-play partizan, and misère-play impartial—the identification of simplest forms proved to be a key result, at once establishing a structure theory and opening the door to further investigations. In this paper, we prove an analogous simplest form theorem for the misère-play partizan case. The proof integrates techniques drawn from each of Conway’s advances, together with a crucial lemma from [Mesdal and Ottaway 2007].
To save this book to your Kindle, first ensure no-reply@cambridge-org.demo.remotlog.com is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.
Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.
Find out more about the Kindle Personal Document Service.
To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.
To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.