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| = 2^{n}+2 or 2^{n}+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.

For a canonical theory of

*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*is a software tool for misere quotient monoid calculation. Using MisereSolver, you can- Compute monoid presentations for finite misere quotients:
- given an octal or hexadecimal game code as input
- given a canonical form (or general impartial game tree) as input
- Compare normal-play and misere-play pretending functions (ie, quotient maps)
- Obtain the outcome partition of a misere quotient (ie, its N- and P-position types)
- Study the algebraic structure of misere quotients
- Idempotents and their natural partial ordering
- Maximal subgroups and archimedean components

MisereSolver written in Java. Its author is Aaron N. Siegel, who has integrated MisereSolver with version 0.7 of ...

*Combinatorial Game Suite*(CGSuite), which is general-purpose software for combinatorial game theory research. Here's a link for that. MisereSolver is a plug-in for CGSuite (but no extra download is needed to access it).

You're invited to join the misere games mailing list.

- 2013-Mar-17: When You Want to Lose: A Semigroup Approach to Misere Games. Sarah Behrens, Coe College (April 2010).
- 2010-Aug-24: An Investigation of Partizan Misere Games. (arXiv) Meghan Rose Allen, PhD thesis, Dalhousie Univ.
- 2007-Aug-07: On infinite indistinguishability quotient monoids in Misere impartial combinatorial games (Google books) Michael Paul Robert Weimerskirch, PhD thesis, Univ of Minnesota.
- 2006-Oct-29: An invitation to combinatorial games (Part II). (slides) Aaron Siegel, Institute for Advanced Study, Princeton NJ.
- 2006-Oct-13: An invitation to combinatorial games (Part I). (slides) Aaron Siegel, Institute for Advanced Study, Princeton NJ.
- 2006-Oct-10: (and 2006-Oct-17): An invitation to combinatorial games. (abstract only) Aaron Siegel, Institute for Advanced Study, Princeton NJ.
- 2006-Sep-09: Impartial Combinatorial Misere Games. (PDF) Meghan Rose Allen, MSc thesis, Dalhousie University, 141 pages.
- 2006-Aug-25: Working Notes: Games at Dal 4. (PDF) Notes prepared by Angela Siegel, 41 pages.
- 2006-May-21: The Misere Mex Mystery (PDF) Aaron Siegel, Canadian Math Society meeting, 55 pages
- 2006-May-21: Miserable Monoids: How to Lose when You Must (PDF) Aaron Siegel, UC Berkeley Commutative Algebra Seminar, 112p.
- 2006-Mar-05: Advances in Losing (PDF), Thane Plambeck, Slides from G4G7 (Gathering for Gardner 7), Atlanta, GA
- 2005-Jun-21: Taming the Wild in Misere Games (PDF) Thane Plambeck, Slides from Banff BIRS conference on combinatorial games, 64 pages.
- 1990 [approx]: A note on Dawson's chess (PDF) Thomas S. Ferguson, UCLA, 3 pages.
- 1984-Sep-07: Machine Computation with Finite Games (PDF) Dean Allemang, MSc thesis, Cambridge University.

Books (combinatorial games)

- Combinatorial Game Theory [Aaron N. Siegel]. AMS Graduate Studies in Mathematics, American Mathematical Society (July 14, 2013).
- Lessons in Play: An introduction to the combinatorial theory of games, Michael Albert, Richard Nowakowski, and David Wolfe. Expected release: February 2007. AK Peters.
- Winning Ways for your Mathematical Plays, Elwyn Berlekamp, John H. Conway, and Richard K. Guy (four volumes). AK Peters.
- On Numbers and Games, John H. Conway. AK Peters.

Books (commutative monoids)

- Commutative Semigroups, P. A. Grillet (Advances in Mathematics), Kluwer, 2001.
- Commutative Semigroup Rings, Robert Gilmer (Chicago Lectures in Mathematics), Univ of Chicago Press, 1984.
- Finitely Generated Commutative Monoids, J. C. Rosales and P. A. Garcia-Sanchez, Nova Science Publishers, Commack, NY. 1999.
- Introduction to Semigroups, Mario Petrich, Charles E. Merrill Publishing Company, Columbus, Ohio, 1973.

These pages were last modified by Thane Plambeck (tplambeck@gmail.com)

Last updated 8:16am Pacific time, Tue 8 Oct 2013