Misere Games

Hi Everyone,

In this post, I will be going over the ins and outs of Combinatorial Games that are played under Misere Rules. I will give a little background on recent discoveries in the Misere world, explain what makes misere games so interesting and excruciating, and then show a couple of examples of what really happens when you play with misere rules.

What Does Misere Mean?

As we all know by this point in class, misere refers to a game play option in which the rules are tinkered to change the outcome of the game. Under normal-play rules in an impartial combinatorial game, the last person to take his or her turn is the winner. This is flipped under misere-play, so you don't want to be the person with the last cookie, and this turns 0 into an N-position but more on that later.

Breaking Ground on Misere Games

It is pretty fair to say that the two names we've heard the most regarding combinatorial games are Sprague and Grundy, so it makes sense that we start here when discussing Misere discoveries. As we heard recently, Sprague and Grundy both essentially solved combinatorial games such as Nim in the 1930s. Through the Sprague-Grundy Theoerem, values, and function we can now analyze any position in the game to figure out the optimal play and who should win.This is because this theorem is the key to understanding the structure of the equivalence classes of games modulo equality. The issue regarding Misere play was described well by Thomas Plambeck and Aaron Siegel,

 "The Sprague–Grundy Theorem yields a remarkably simple structure for the normal-play equivalence classes of impartial games. In misere play, however, the situation is vastly more complex. For example, consider just those impartial games born by day 6. In normal play, there are precisely seven of them, up to equivalence: 0, ∗, ∗2, . . . , ∗6. By contrast, Conway has shown that in misere play there are more than 2^4171779"

Since misere games can be a bit of a black hole when it comes to solving the strategy, experts have been working to organize them by difficulty. Since misere nim has been solved, a misere game is known as tame if it can be explained in terms of misere nim, as in it is tame enough to explain quickly(ish). If not, the set of games is wild.



Misere Quotients

Misere Quotients are the essential part to understanding and solving the only  Misere games we can, and thus are fairly complicated. Misere quotients are described as commutative monoids that encode the additive structure of specific misere-play games. Basically what this means is that every situation in some game can be localized to the set of all positions that arise in the play of a particular, associating a game with one commutative monoid, which is the misere quotient. This monoid is essentially the key to the map and once the monoid is found, you can get a perfect strategy. Below is a misere quotient for a random octal game done by Thomas Plambeck:

As you can see, it analyzes every heap size until it can find a pattern, once it calculates the period then it creates the misere quotient (Q,P) as shown above. 

I wrote above about misere games that were classified as either tame or wild, and now that I have explained misere quotients a bit, we can see below these monoids are standard for a tame game: if a misere quotient is isomorphic to these, then it is tame. Fun fact, T₂  is actually the quotient for games 0.23 0.31 and 0.52 

Let's Solve One

0.123

To understand how to solve this game, we will follow the steps of the Electronic Journal of Combinatorial Number Theory 5. 

This is the game we will try to analyze playing with misere-play. 0.123 is an octal game (take away with two players and is impartial) where there is heaps of coins, tokens, etc. The basic rules are as follows:
1. Three counters may be removed from any heap;
2. Two counters may be removed from a heap, but only if it has more than two counters; and
3. One counter may be removed only if it is the only counter in that heap.

So we first analyze the size of the heaps, and we see the period is of length 5.

Clearly, the first row is showing simple integers, and thus at those positions the game behaves identical to a misere nim heap of the same size. So this figure works for us to show outcome classes for single heap misere 0.123 positions but we need to expand this to get info about the best play of all misere 0.123 positions (arbitrary sum of arbitrarily-sized heaps). So we take the picture above and make it abstract, to this below:

To make very long proof short, the paper then proves the theorem that the misere quotient of 0.123 is isomorphic to the following 20-element commutative semigroup

The 20 elements (second line) can then be broken up into 15 N-positions and 5 P-Positions

So now that we have these positions, wherever we are in the game, we take whatever values we have in the heaps and convert them into the correct terminology. Then we multiply these together, reduce where we can, and then line up our result in the final table to find out what position we have.
These steps are all in the image below with an example:

So thus we have beaten 0.123!!

That's a wrap on this blog post, I will hopefully go over everything in a little more detail tomorrow, but this is one example of a misere game being solved!

-Harry Copeland

Sources:

http://www.emis.ams.org/journals/INTEGERS/papers/fg5/fg5.pdf
http://web.mit.edu/sp.268/www/nim.pdf
gameshttps://www.jstage.jst.go.jp/article/jmath1948/32/3/32_3_461/_pdf
http://arxiv.org/pdf/math/0609825v5.pdf
http://web.mit.edu/sp.268/www/nim.pdf