papers ·· software ·· solutions archive ·· email list ·· blog ·· related material
Welcome! We're mathematicians and computer scientists studying commutative monoids arising as solutions of misere-play combinatorial games.
What to read first?In November 2006, Aaron Siegel gave five two-hour lectures on misere games at the Weizmann Institute. There's no better introduction to our subject.
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 misere quotient construction; a proof of the Guy–Smith–Plambeck Periodicity Theorem; and statements of some recent results and open problems in the subject.
PapersAlternatively, dive into the nitty-gritty. Here are some papers on our subject that have been already published or are available in the arXiv as preprints:
Abstract: We announce misere-play solutions to several previously-unsolved combinatorial games. The solutions are described in terms of misere quotients—commutative monoids that encode the additive structure of specific misere-play games. We also introduce several advances in the structure theory of misere quotients, including a connection between the combinatorial structure of normal and misere play.
Abstract: We provide supplementary appendices to the paper Misere quotients for impartial games. These include detailed solutions to many of the octal games discussed in the paper, and descriptions of the algorithms used to compute most of our solutions.
Abstract: A bipartite monoid is a commutative monoid Q together with an identified subset P of Q. In this paper we study a class of bipartite monoids, known as misere quotients, that are naturally associated to impartial combinatorial games. We introduce a structure theory for misere quotients with |P| = 2, and give a complete classification of all such quotients up to isomorphism. One consequence is that if |P| = 2 and Q is finite, then |Q| = 2n+2 or 2n+4. We then develop computational techniques for enumerating misere quotients of small order, and apply them to count the number of non-isomorphic quotients of order at most 18. We also include a manual proof that there is exactly one quotient of order 8.
Abstract: We survey recent developments in the theory of impartial combinatorial games in misere play, focusing on how the Sprague-Grundy theory of normal-play impartial games generalizes to misere play via the indistinguishability quotient construction. This paper is based on a lecture given on 21 June 2005 at the Combinatorial Game Theory Workshop at the Banff International Research Station. It has been extended to include a survey of results on misere games, a list of open problems involving them, and a summary of MisereSolver [AS2005], the excellent Java-language program for misere indistinguishability quotient construction recently developed by Aaron Siegel. Many wild misere games that have long appeared intractible may now lie within the grasp of assiduous losers and their faithful computer assistants, particularly those researchers and computers equipped with MisereSolver.
Abstract: We introduce a misere quotient semigroup construction in impartial combinatorial game theory, and argue that it is the long-sought natural generalization of the normal-play Sprague-Grundy theory to misere play. Along the way, we illustrate how to use the theory to describe complete analyses of two wild taking and breaking games.
The previous papers all treat impartial misere games.Abstract: We show that partizan games admit canonical forms in misere play. The proof is a synthesis of the canonical form theorems for normal-play partizan games and misere-play impartial games. It is fully constructive, and algorithms readily emerge for comparing misere games and calculating their canonical forms. We use these techniques to show that there are precisely 256 games born by day 2, and to obtain a bound on the number of games born by day 3.
Software
MisereSolver written in Java. Its author is Aaron N. Siegel, who has integrated MisereSolver with version 0.7 of ...
Solutions archive
The email listYou're invited to join the misere games mailing list.
The blog
Related materialBooks (combinatorial games)
Books (commutative monoids)