(NOTE: Check out the other posts in The Secrets of Nim series.)
At this point, you should have learned and practiced about standard and Misère single-pile Nim, as well as standard multi-pile Nim. Now, we move onto multi-pile Misère Nim.
Trying It Out
Instead of starting with an explanation, I'm going to take a different tack here, and have you try out multi-pile Misère Nim first. Go over to Archimedes' Lab's Nim game. Remember here that, in Misère Nim, the loser is the person who removes the last object.
If you're comfortable analyzing standard multi-pile Nim, as taught in the previous post, try applying those same analytical skills to the Misère version. Ask yourself, what changes in the analysis might be needed to accommodate the new goal?
Winning Moves
Thankfully, Scam School covered multi-pile Misère Nim back in episode 37. You'll notice that this version uses piles of 3, 5, and 7 coins, just like the game analyzed in part 2 of this series, so you'll have an basis for comparison to the standard Nim strategy.
In this video, you'll learn the winning moves, and then I'll go on to explain WHY these are winning moves.
Did you notice anything familiar about the list of winning moves that was shown in this video?
When analyzing safe moves for standard multi-pile Nim, we were able to determine that you wanted to leave the board with the safe positions of 2/4/6, 1/4/5, 1/2/3, or 2 equal rows. Strangely enough, these are also given on the video as safe positions for Misère Nim! What's going on? And what's with the addition of that 1/1/1 arrangement?
The Endgame
The method of working out safe arrangements using binary aren't simply safe because they will always allow you to take the last piece. They're safe because they allow you to keep control of the board for ANY objective.
This is good news, as it means you don't have to learn a whole new system for analyzing multi-pile Misère Nim. Once you've analyzed safe positions for a given standard Nim layout, you can also use that list of positions for the same layout in Misère Nim.
There are differences, of course, but you only have to worry about the differences in the endgame. But what are those differences?
Let's try a very trivial version of multi-pile Misère Nim: There's only one match on the table, the player who takes the last match loses, and it's your turn. Naturally, you lose!
What about the same situation, except with 2 piles, each containing a single match? Well, you take 1 match from 1 pile, I'm left with the other one, and so I lose. 3 single-match piles? You take 1 match, I take 1 match, and you're left with the remaining match, and you lose!
It's not hard to see that, when you're left with an odd number of piles, each consisting of a single match, that you're going to lose the game. This is why the new 1/1/1 arrangement appears on the safe positions list for multi-pile Misère Nim, but not on the one for multi-pile standard Nim.
Technically, 1 match in 1 pile should be mentioned on the list from the Scam School video above, but it's not because, being the object of the game, it's assumed you're already going to remember it.
In a nutshell, there's the approach for multi-pile Misère Nim: Perform an analysis of a given layout to find the possible safe positions for standard Nim (and memorize them!), then add odd single-match piles (1, 1/1/1, 1/1/1/1/1, and so on) as appropriate for the particular layout (for example, if you're starting with 4 piles, obviously only 1 and 1/1/1 are going to apply).
As always, don't forget that if the game starts in an already-safe arrangement, you want the other person to go first. Removing coins from any safe arrangement can only make it unsafe, just as discussed in part 2 of this series.
With this new knowledge, go back to Archimedes' Lab's Nim game and try analyzing the game with this new knowledge. With a little practice, you'll find that you'll start winning every time.
Archimedes' Lab also has a briefer look at the binary analysis of multi-pile Misère Nim that you might enjoy.
If you're using a browser that run Flash, try going back to Nim Master, and playing their Reverse game: Leave last stone to win, using your new-found skills. This is a different layout every time, so you'll mostly be looking for safe positions in binary.
Conclusion
If you've practiced the techniques discussed over this series, you should both be able to win any version of Nim that has been discussed here. You should also be able to create your own customized versions of Nim, such as the Douglas Adams 42 version discussed in part 2.
If you enjoyed this series on Nim, and would like to show your appreciation to Grey Matters while learning more about Nim, there are two books I would like to recommend from Amazon. The first is Nim: Serious Math With a Simple Game, by Christopher M. Freeman. The other is Creating NIM Games, by Sherron Pfeiffer.
Just because these versions of Nim have been analyzed, and are winnable, doesn't mean that there's nothing left to learn about Nim-type games. There's a game called Chomp, which is basically Nim in 2 dimensions simultaneously. It's been around since the early 1970s (the original article mentioned on this page was reprinted as Chapter 9 of Martin Gardner's Knotted Doughnuts and Other Mathematical Amusements), but to this day, remains only partially solved.
Back around 1980, B. M. Rothbart proposed another 2-dimensional version of Nim, in which various numbers of objects are arranged in rows and columns. You can remove as many objects as you like, as long as they only come from the same single column OR the same single row.
Who knows? You may be the one to solve these or similar problems.
I hope you've enjoyed this look at Nim, and found it useful. Please let me hear about anything you've learned, as well as your questions and/or results, in the comments.
Posts
1 Response to The Secrets of Nim (Part 3)
Thank you very much!!! It was really really useful!! =)
Post a Comment