Variants of Nim - Lasker's and Misère

Variants of Nim - Lasker's and Misère

As we have seen for a few blog posts now, the Sprague Grundy theorem is fundamental to understanding combinatorial game theory. This will hold to be true for Lasker’s Nim as well.

Let's get right into it, who is Lasker and why do we care about his Nim?

https://en.wikipedia.org/wiki/Emanuel_Lasker#/media/File:Bundesarchiv_Bild_102-00457,_Emanuel_Lasker.jpg

Emanuel Lasker was a German mathematician, philosopher, and chess champion. He was the world chess champion for 27 years (1894 - 1921).

·      We can compare this to Tom Brady; only Tom would need to win 23 22 more super bowls.

·      Michael Jordan would need 21 more NBA Championships.

·      Jack Nicklaus would need to win 9 more golf majors.

·      Roger Federer would need to win 9 more tennis grand slams. 

He must have been a great chess player right? Right.

Lasker’s Nim:

Lasker’s Nim is a type of Take and Break Game.

http://i.imgur.com/C4IzVgB.gif

No no, not Shake and Bake, Take and Break!

“What’s a Take and Break Game Riley?” The class shouted in unison.

Well class, Take and Break Games are games where the rules say you can take and/or split (break) one pile into two or more parts depending on the conditions of the game, which inherently increases the number of piles in the game.

In Lasker’s Nim there are one or more piles of coins, chips, stones, paperclips, etc. Each player at her turn has two choices:

1.     A player can remove any number of things from a pile (exact same as Nim).

2.     A player can choose to break a single pile into two smaller piles (no coins removed).

Now in order to break a pile there obviously needs to be at minimum 2 coins in the pile. This eliminates the possibility of a player claiming to “break” a pile with one coin in it into two piles, one of size one, and the other containing zero coins.

Where Sprague and Grundy come in:

Let’s say we are playing a game of Lasker’s Nim, which begins with a single pile. We begin with the almost trivial cases of the Sprague-Grundy Function where g (0) = 0, moving up from there we arrive at g (1) = 1, and now we are on to the more interesting cases, a pile with two coins!

At this point there are some choices we can make: A player can remove either one or two coins or they can choose to split the pile of two coins into two piles of coin size one. This gives us Sprague-Grundy values of 0, 1 and 1 ⊕ 1 = 0. Thus, g (2) = 2. Ferguson calls them "followers" for some reason when I read about it. He goes on to explain, the followers of 3 are 0, 1, 2, and (1,2), with Sprague-Grundy values 0,1,2, and 1 ⊕ 2 = 3. Thus, g (3) = 4. 

What do you think g (4) is given what we know? What about g (5)? Can you see a trend appearing? Is this function periodic? Leave some answers in the comments before you take a look at the table for the function!

       

http://giphy.com/gifs/stilltheking-cmt-still-the-king-3o6gDWvntdm16XezUA

The Sprague-Grundy Function Table

       x 0 1 2 3 4 5 6 7 8 9 10 11 12 ... 

 g(x) 0 1 2 4 3 5 6 8 7 9 10 12 11 ...

From this table we can conjecture the following:

g (4k + 1) = 4k + 1, g (4k + 2) = 4k + 2, g (4k + 3) = 4k + 4, and g (4k + 4) = 4k + 3, for all k ≥ 0.

http://giphy.com/gifs/reaction-prove-it-eLXShXXa8AMso

Alright, let's prove it via induction:

Think back to Bridge and keep in mind the definitions of even and odd for this proof.

The followers of 4k + 1 that have a single pile have Sprague-Grundy values from 0 to 4k. Those that have two piles, (4k, 1), (4k − 1,2), . . . , (2k + 1, 2k), have even Sprague-Grundy values, and therefore g(4k + 1) = 4k + 1.

The followers of 4k + 2 that have a single pile have Sprague-Grundy values from 0 to 4k + 1. Those that have two piles, (4k + 1, 1),(4k, 2), . . . ,(2k + 1, 2k + 1), have Sprague-Grundy values alternately divisible by 4 and odd, thus g(4k + 2) = 4k + 2.

The followers of 4k + 3 that have a single pile have Sprague-Grundy values from 0 to 4k + 2. Those that have two piles, (4k + 2, 1),(4k + 1, 2), . . . ,(2k + 2, 2k + 1), have odd Sprague-Grundy values, and in particular g(4k + 2, 1) = 4k + 3. Hence g(4k + 3) = 4k + 4.

Finally, the followers of 4k + 4 that have a single pile have Sprague-Grundy values from 0 to 4k + 2, and 4k + 4. Those that have two piles, (4k + 3, 1)(4k + 2, 2), . . . ,(2k + 2, 2k +2), have Sprague-Grundy values alternately equal to 1 (mod 4) and even. Hence, g(4k + 4) = 4k + 3.

DONE!

Misère Nim:

In Misère Nim the player who removes the last coin in the game loses. This means that your goal in the game is to leave the last coin for your opponent to take.

It turns out that the winning strategy for this misère game is to play exactly how you would in normal play (regular old Nim) until your opponent leaves one pile of size greater than one. When this happens, reduce that pile size to zero or one, whichever leaves an odd number of piles with only one coin.

Can anyone figure out why this works? Comment some ideas and I will go over the answer to this in class!

In the sake of staying sharp it may be useful to go over a few things we have learned before class on Tuesday! Some may say that one will stay NIMBLE if they compute these:

1)   What is the nim-sum of 27 and 17?

2)   The nim-sum of 38 and x is 25. Find x.

3)   Find all the winning moves in a game of nim,

a)   With three piles of 12, 19, and 27 chips.

b)   With four piles of 13, 17, 19 and 23 chips.

c)    What is the answer to (a) and (b) if the misère version of nim is being played?

Don’t forget to leave your answers in the comments!

Conclusion:

Lasker's Nim has provided a nice introduction to take and break games as we are all very comfortable with the idea of Nim, and are beginning to gain our footing with Sprague-Grundy values and functions. This game also adds another component to Nim which can impact play styles and outcomes which is a lot of fun!

Normally Misère games add so much complexity to a game that it becomes impossible or extremely difficult to analyze, Nim is certainly an outlier in this regard as we can analyze the game fairly easily. Because this area in combinatorial game theory is so complex there are still many opportunities for new insightful discoveries. Misère play could be a great topic for a final project for the boldest of students. 

Citations:

Ferguson, Thomas S. "Game Theory." Ferguson, T. S. (n.d.). Game Theory. Retrieved from http://myslu.stlawu.edu/~nkomarov/450/comb.pdf.

"Emanuel Lasker." Wikipedia. https://en.wikipedia.org/wiki/Emanuel_Lasker.