(NOTE: Check out the other posts in The Secrets of Nim series.)
Up to this point, we've been assuming that you're playing Nim against someone who is unfamiliar with the sure-fire strategies for winning Nim. What do you do when you run into someone who knows the strategies behind the game? It's time for you to learn Wise-Guy Nim!
Terminology
For the first time since Part 1, we're going to add new terminology: Wise-Guy Nim. This will refer to any version of Nim in which both players are aware of the strategies for winning Nim.
If both players are familiar with the same strategies, how is it possible for one of them to beat the other? Even those who talk about knowing the strategies often really only understand the moves needed to win a particular version of Nim.
For example, you might come across someone who knows how to win single-pile Misère Nim with 21 objects might not understand how to adapt to other amounts of objects. Alternatively, they might not understand what to do if the game is switched to single-pile standard Nim. Even if the person can handle any version of single-pile Nim, you might be able to beat them by switching to multi-pile Nim!
Strangely enough, even with a set type of Nim, such as the single-pile versions on which we'll be focusing in this post, and a set number of matches, it's still possible to beat a knowledgeable player. How? There are two basic ways: quick hands or a quick mind.
The Physical Approach
In this version, your hands give you the advantage. Let's go back to the video originally featured at the end of Part 1 of this series:
See? One match made a difference. The division by 4 principle seemed simple enough, but if you've read event just the first post in this series, you'll know that's not enough knowledge to win when the game changes! I love that the marks here are beaten twice. It's an ingenious approach.
You may worry about being caught red-handed while trying to cheat in this manner. If so, there is an alternative.
The Mental Approach
If you really take the time to analyze a given game of Nim, you begin to see more and more opportunities. One wonderful example of such insight is shown in the Scam School episode where the game of “31” is taught:
When I discussed this video in Part 1, I wrote:
This is why the number 31 was so specifically chosen for this version of the game. It works in the first game, which is really “modulo 7”. When teaching the game, the game is effectively changed to “modulo 4”, which works until all the 3s and 4s are gone, at which point the game suddenly changes to “modulo 3” without warning! This is very sneaky.If you analyze a single-pile Nim game in at least two different ways, you realize that it is possible to change the game without physically changing the amount of objects!
Werner Miller, one of my favorite recreational mathematicians, realized this over 30 years ago, and came up with a way to win on a given number, regardless of who started!
To explain Werner Miller's idea, let's play a game of single-pile Misère Nim (Misère means the last player to take an object is the loser), using 16 objects. Since you're already familiar with Nim, I ask you to decide who will go first.
Let's say you decide to go first. I remind you that we can only take anywhere from 1 to 4 objects at each turn, and then you make your opening move. You take 3 objects, and I take 2. You take 4 objects, and I take 1. You take 1 object, and I take 4. You're left with the last object at this point.
If you've been keeping up with my Nim series, this approach shouldn't surprise anybody. So what's Werner Miller's great addition?
Let say, instead, that you decide that I should go first (We still have 16 objects, and it's still Misère Nim). In this case, I mention that we can only take from 1 to 3 objects (instead of 1 to 4, as in the previous case) each turn, and I start by removing 3 objects. From that point, you might take 3 objects, so I take 1. You take 2 objects, so I take 2. You take 1 object, I take 3, and you're left with the last object, so you lose again.
Werner Miller's sneaky idea boils down to asking who goes first before you state how many objects can be taken on each turn. This allows the game to be changed at a moment's notice. Of course, you do want to practice this well, so that you're using the proper strategy for the given situation!
This approach works with either standard or Misère Nim, and works with many numbers (although not with every number). If you'd like to experiment with other numbers, check out the new Wise-Guy Nim tab over at the Nim Strategy Calculator. All you need to enter is whether the person who removes the last object is a winner or loser, and how many objects are being used. Click on the Calculate Nim Strategy button, and it will explain how to use this approach, assuming it doesn't tell you that the number won't work.
If you want to understand the math behind how this works, I'll let Werner Miller explain it to you in the same words in which he explained it to me:
More than 30 years ago, I worked out a strategy how to win a single-pile Nim against someone who knows the standard strategy no matter which player starts removing objects: The number of objects (a) in the pile has to match both the term (n1 x m1) + 1 and the term (n2 x m2) + k + 1 (where 0 < k < m2), and I lay down the maximum number of objects to be removed (m1 - 1 or m2 - 1) not until knowing which player will do the first move.
This will work, e.g., with a = 16 = 3x5 + 1 = 3x4 + 3 + 1
or a = 17 = 4x4 + 1 = 5x3 + 1 + 1
or a = 19 = 6x3 + 1 = 4x4 + 2 + 1
Ask your opponent if he wants to move first or not.
If he wants to move first, instruct him that the maximum number he can remove each time is m1 - 1. If he wants that you do the first move, instruct him that the maximum number he can remove each time is m2 - 1.
If your oppontent does the first move and removes p object(s),
remove m1 - p objects, and so on.
If you do the first move, remove k objects. Then your opponent removes p objects, you remove m2 - p objects, and so on.The description above applies to Misère Nim. It's quite simple to adjust for standard Nim (where the player who takes the last object wins). All you have to do is eliminate the final + 1 in both equations.
The mathematical explanation may sound confusing, but if you run various numbers through the Wise-Guy Nim tab in various ways, study the results, and compare them to the above explanation, it quickly becomes clear.
Great thanks go out to Werner Miller for his work on this incredible variation. Thanks should also go out to Brian Brushwood and the Scam School crew, for the incredible work they put into their videos. Also, thanks should go out to Devon Govett, John Resig and The Javascript Source, for their contributions which helped make the Wise-Guy Nim tab functional.
Posts
No Response to "The Secrets of Nim (Wise-Guy Nim)"
Post a Comment