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.
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.
Alternatively, dive into the nitty-gritty. Here are some books and papers on our subject that have been already published or are available in the arXiv as preprints:
Webmaster comment: This is Aaron Siegel's 527-page magnum opus on Combinatorial Game Theory. It includes not only a full development of the history and the latest research on impartial misere quotients, but also a new exposition of the partizan misere theory, and much more. Highly recommended!
Abstract: The impartial combinatorial game Kayles is played on a row of pins, with players taking turns removing either a single pin or two adjacent pins. A natural partizan variation is to allow one player to remove only a single pin and the other only a pair of pins. This paper develops a complete solution for "Partizan Kayles" under misere play, including the misere monoid all possible sums of positions, and discusses its significance in the context of misere invertibility: the universe of Partizan Kayles contains a position whose additive inverse is not its negative, and, moreover, this position is an example of a right-win game whose inverse is previous-win.
Abstract: We analyze misere play of impartial tic-tac-toe---a game suggested by Bob Koca in which both players make X's on the board, and the first player to complete three-in-a-row loses. This game was recently discussed on mathoverflow.net in a thread created by Timothy Y. Chow.
Abstract: We show that the lattice games of Guo and Miller support universal computation, disproving their conjecture that all lattice games have rational strategies. We also state an explicit counterexample to that conjecture: a three dimensional lattice game whose set of winning positions does not have a rational generating function.
Webmaster comment: Lattice point methods, affine stratifications, and other techniques from commutative algebra, brought to bear on the algebraic structure of normal & misere games with both finite and infinite quotients. This is the coolest, latest stuff, so go see!
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.
MisereSolver written in Java. Its author is Aaron N. Siegel, who has integrated MisereSolver with version 0.7 of ...
You're invited to join the misere games mailing list.
Books (combinatorial games)
Books (commutative monoids)