misere games

Wild misere game confronts Redei's theorem & Knuth-Bendix rewriting
or
Taming the Wild in Impartial Combinatorial Games

We've spent a lot of time teaching you how to win games by being the last to move. But suppose you are baby-sitting little Jimmy and want, at least occasionally, to make sure you lose? This means that instead of playing the normal play rule in which whoever can't move is the loser, you've switched to misère play rule when he's the winner. Will this make much difference? Not always...
From Winning Ways, in the Introduction to Chapter 13, "Survival in the Lost World"

Note added 4 Oct 2006
These pages on misere games are now somewhat obsolete.

There's a new website at miseregames.org that you might consider visiting instead. It contains all the information that's here, on this web site, in a more organized form.

There's also a blog on misere games.

Please consider joining the misere games & commutative algebra mailing list.

Hope to see you there!

Thane
Note added 5 August 2006
Dan Hoey sent me this interesting page he's put together on the game of Nim in the screenplay of the movie Last Year at Marienbad.

Note added 31 July 2006
I spent some time thinking about partisan misere games (blog entries #1 and #2).
Note added 1 March 2006
I just put a paper into the arXiv called Advances in Losing. It's actually been done for awhile; I just got around to doing it. Now I'm working on a paper with Aaron Siegel called "The Phi-values of various games," and I needed to have a reference to this other paper, so I put it into the arXiv. "Advances in Losing" is eventually going to be in a Cambridge Univ Press book being edited by Richard Nowakowski and Michael Albert called Games of No Chance 3.
Note added 25 February 2006
A new version of the game to be played on the logo of the 2006 Gathering for Gardner (G4G7) meeting invitation, fixing errors pointed out by Dan Hoey [thanks, Dan!]
Note added 6 February 2006
A cribsheet handout (PDF) for misere play of a game to be played on the logo of the 2006 Gathering for Gardner (G4G7) meeting invitation.
Note added 5 February 2006
(1) I've finished a new paper on misere games to be called "Advances in Losing." I'll eventually put into in the arXiV, but haven't yet. It's also going to be in a Cambridge Univ Press book.

(2) Aaron Siegel and I are working on another paper with title "The Phi-values of Various Games." It probably won't be ready for a month or two.

(3) The 1961 movie Last Year at Marienbad contains some highly amusing scenes involving play of Misere Nim. Here are some notes on it.
Note added 28 August 2005
Aaron Siegel has found many more wild misere game solutions amongst the four-digit octals, including this amazing one, for 0.4107.

Download complete solution description (6 kB)
Another note added 29 July 2005
Aaron Siegel has found a complete analysis of the misere play of Guiles (Guy and Smith octal code 0.15) by using his recently developed standalone java program, MisereSolver.

The misere quotient semigroup of Guiles has 42 elements, and its pretending function has period 10.

There will be a paper coming out in the next year or so that gives more information. If you want to wade through the details now, before it's cleaned up for publication, here's the solution file that gives its misere indistinguishability quotient semigroups to heap 160. That's more than long enough to guarantee that the periodicity continues indefinitely. And here's an even bigger log file documenting the same computation, also to heap 160.
Notes added 29 July 2005 Solutions to wild quaternary games PDF (Aaron Siegel).

Aaron has also found a solution for the wild octal game 0.144.

More information here (background paper) and here (my original problem statement, presented at the Banff CGT conference problem session last month).

More tidbits from Aaron:

0.01222 has period 8 and quotient order 370
0.10322 has period 8 and quotient order 214

Notes added 19 July 2005
Aaron Siegel has already whipped together an amazing Java program for everything in my misere CGT paper, while also incorporating his own insights into algorithms for misere quotient semigroup computation. Given an octal game code as input, his program directly computes a presentation of its misere quotient semigroup to heap size n=1, 2, 3, in turn, together with the associated pretending functions and outcome partitions at each heap size n. He's solved .15 (Guiles), .115, .114, and a bunch of wild quaternary games using this software.

Eventually his software will make into cgsuite, I hope.
Notes added 15 July 2005
My paper "Taming the Wild in Impartial Games" has been accepted by INTEGERS. Aaron Siegel and Dan Hoey helped me by pointing out some mistakes in section 11.5 that I've corrected in this new and (hopefully) final version that I just put into the arXiv.

Notes added 12 July 2005
Aaron Siegel has claimed 17 of the 21 quaternary bounties. Still open are .3102, .3122, .3123, and .3312. That's $425 in bounties for Aaron, but there's still $100 on the table...
Notes added 24 June 2005
Quaternary Bounties (PDF, 2 pages)

I'm hoping to contribute some software for misere games for incorporation into cgsuite.

Slides (PDF, 60+ pages) that I presented (and some that I did not present) at the BIRS Workshop on Combinatorial Games.

Note added 11 February 2005
Misere Dawson's Chess analyzed to heap size 30. (PDF, 9 pages). This won't be intelligible unless you've had a look at the paper "Taming the Wild in Impartial Combinatorial Games,'' first (see the next paragraph for how to get that paper).

Note added 21 January 2005
I've corrected some errata and improved the exposition in section 9 of my paper, "Taming the Wild in Impartial Combinatorial Games." This is the paper you should start with if you're interested in how the Sprague-Grundy theory of impartial combinatorial games generalizes to misere play via classical commutative semigroup theory and the indistinguishability quotient construction. The paper is available at the arXiv via this link.

Note added 4 December 2004
I just submitted a paper on misere games to INTEGERS called "Taming the Wild in Impartial Combinatorial Games." Almost everything else on this web site is stuff I wrote before realizing that the misere indistinguishability quotient is the fundamental object of interest in misere play.
Note added 17 August 2004
A short note on the quotient semigroup viewpoint for misere games. I wrote this note two days after discovering the quotient semigroup construction.
Note added April 2004
I gave a talk called ``Pretending in Misere Combinatorial Games'' at the (first inaugural) Experimental Mathematics Workshop, organized by David Bailey and Jonathan Borwein. Here are my slides (PDF). This talk is missing the idea of the misere quotient, but might still be of interest.
Notes added early 2004
(1) Pretending in Misère Combinatorial Games (PDF, 70 pages) These otherwise unpublished "working notes" contain almost all the information about misère impartial games that I knew about in 2003. Like everything I did prior to 15 August 2004, it lacks the idea of the misere quotient semigroup. There are quite a few completely solved games in this paper, though, and some corrections to other solutions in the literature. The information in this paper needs to be recast into the quotient semigroup framework. I'm working on that now (December 2004). So if you want to read the whole story, be my guest...

(2) Gérard Michon's web site has a good introduction to impartial game theory in normal play.

Misère Games (even older history, 2002 and prior)

In the early 1990s I wrote a paper called "Daisies, Kayles, and Sibert-Conway Decomposition in Misère Octal Games" [PDF] that was published in the journal Theoretical Computer Science.

More recently (2002), I learned that Dean Allemang had already published a misère play solution of the octal game 4.7 (which I called "Daisies," and he calls "Knots") in his M.Sc. thesis at Cambridge University in the mid-1980s.

Allemang has a web site [I guess not anymore, that link is dead] that collects together his results on misère octal games. You can also play many misère octal games using his web-based interfaces.

After learning about Allemang's results, I got interested in this subject again. I started to develop some Mathematica programs to search for (and verify) misère play solutions of octal games.

Here's an HTML preview of a Mathematica toolkit I'm developing for impartial misère games. It's similar in spirit to David Wolfe's Gamesman's Toolkit, but with the usual normal-play impartial game simplification rules (in which every game ultimately reduces to a nim heap *k) replaced by their misère versions (in which more general misère games such as the "adder" a[4] = *2 + *2 = {*3,*2} occur). This toolkit has enough in it to verify many of the computations contained in Chapter 13 ("Survival in Lost World") of Winning Ways, and it knows most of the theory contained in that chapter, as well as some of the theory in Allemang's work. In particular, the results on two-digit misère octal games in Table 5 at the end of Chapter 15 of Winning Ways (page 425) are partially verified and also extended in places. Since I'm still actively working on this toolkit, there's probably a much better version available than the one I've archived here as a hedge against my laptop exploding. If you're interested in obtaining this Mathematica notebook as a *.nb file, let me know.

In the normal play of an impartial game, every position H satisfies the identity H + H = 0. Although the general situation in misère play is much more complicated, often one can pretend that weaker identities such as H + H + H = H are valid. In certain cases, such pretending equations can even lead to a complete analyses of the outcome classes of a wild (ie nontame) octal game. Such analyses have been notoriously difficult to come by over the years, and many games, such as Dawson's Chess (from the year 1935) are still unsolved. So there is much to be done. I've put a draft of a paper called "Pretending in Misère Combinatorial Games" [PDF] here on this web site, wherein you'll find the latest (most recent update: 9 September 2003) information on this intriguing subject.

I've added information about particular game solutions and some notes on genus theory using the links on the left hand side of this page. There's more information on exact game values in the Mathematica notebook.

All this stuff is targeted at experts, but it's not hard to become one. If you're just diving into this subject, you might be better off taking a look my paper (PDF link at top of this page), Allemang's web site, or (even better) references [4, Chapter 13] and [5, Chapter 12, "How to Lose When You Must"], below, first.

References

[1] D.T. Allemang, "Machine Computation with Finite Games", MSc Thesis, Cambridge University, 1984.

[2] Dean Allemang, Solving misere games quickly without search, unpublished (2002)

[3] Dean Allemang, Generalized genus sequences for misere octal games, International Journal of Game Theory 30 (2002) 4, 539-556.

[4] E.R. Berlekamp, J.H. Conway and R.K. Guy, Winning Ways for Your Mathematical Plays (Academic Press, London, 1982).

[5] J.H. Conway, On Numbers and Games (Academic Press, London and New York, 1976).

[6] R.K. Guy, Unsolved Problems in Combinatorial Games, in R.J. Nowakowski (ed.), Games of No Chance, Cambridge University Press, 1994.

[7] T.E. Plambeck, Daisies, Kayles and the Sibert-Conway decomposition in misere octal games, Theoret. Comput. Sci (Math Games) (1992) 96 361-388.

[8] Thane E Plambeck, Taming the Wild in Impartial Combinatorial Games, INTEGERS: Electronic Journal of Combinatorial Number Theory 5 (2005) #G05.

[9] W.L. Sibert and J.H. Conway, Mathematical Kayles, Int. J. Game Theory (1992) 20:237-246.

[10] Thomas S Ferguson, A Note on Dawson's Chess, unpublished research note, http://www.math.ucla.edu/~tom/papers/unpublished