About

Hi, I’m Thane Plambeck. I’m using this blog to report (and archive) information about my (and other people’s) research into commutative monoid presentations for misere combinatorial games.

Things were getting a bit messy with misere game results getting mixed into my usual blog, so I decided to create this new blog specifically related to misere games.

If you’re interested in this subject, I recommend visiting miseregames.org, too.

Some prehistory

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. 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.

In misere play, the usual normal-play impartial game simplification rules (in which every game ultimately reduces to a nim heap *k) are replaced by their misère versions (in which more general misère games such as the “adder” a[4] = *2 + *2 = {*3,*2} occur). My original toolkit had enough in it to verify many of the computations contained in Chapter 13 (“Survival in Lost World”) of Winning Ways, and it knew most of the theory contained in that chapter, as well as some of the theory in Allemang’s work.

After many twists and turns, in the summer of 2004, I realized that commutative monoids and something I called the indistinguishability quotient were full-fledged local misere analogues of the normal-play Sprague Grundy theory (which itself had been around for over 70 years). Moreover, it became increasingly clear that there was some intriguing commutative algebra underlying the solutions of particular games. This blog records some of the many amazing consequences and further results on misere game research—research that is still continuing today. In particular, the toolkits I had developed were rapidly supplanted in 2005 by fantastic software by Aaron N. Siegel called MisereSolver. There’s quite a bit on results found by Aaron using MisereSolver on this web site. Such analyses have been notoriously difficult to come by over the years, and many games, such as (from the year 1935) are still unsolved. So there is much to be done.

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 at the references [4, Chapter 13] and [5, Chapter 12, “How to Lose When You Must”], below, first.

There’s much more at miseregames.org.
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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: