(NOTE: Check out the other posts in The Secrets of Nim series.)
Thought we were done with Nim? Not by a long shot! Today, I have a single-pile standard Nim game for you (as defined in Part 1 of the Secrets of Nim series), but with a twist!
The New Rules
Just as with most standard single-pile Nim games, this version has the following rules:
• There are two players.
• The players alternate taking turns.
• The game starts out with a set number of objects.
• Neither player is allowed to remove 0 objects.
• The last person to make a move is the winner.
The twist comes from two new rules:
• The player who moves first can remove as many objects as they like from the pile, as long as they leave 1 or more objects for the other player. (e.g., In a game with 26 objects, the first player can remove up to 25 objects.)
• After the first move, each player may remove, at most, twice the number of counters his opponent took on the previous move.
Let's start with 26 objects, which has become a standard starting amount for this version of Nim. Try playing this online Javascript version (To keep trying with 26, reload the page instead of clicking the newgame button).
Did you have any luck? Or did your computer keep winning?
Basic Strategy
Well, it's Nim, and we know there are ways to guarantee a win. Perhaps we could use the Single-Pile Nim Strategy Calculator. Hmmmm...nope, there's no way to account for the variable amounts you're allowed to take.
There's a bit of a hint in the sub-heading of this post, Fibonacci Nim. Let's jump back a few posts, and check out the first video from Fun with Phi again:
Before you get too scared, the method does not involving performing any sort of arithmetic with Phi.
What we need here is the original Fibonacci numbers themselves. Since we should probably keep our games under 100 objects, we'll just focus on the Fibonacci numbers that are less than 100: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, and 89.
If you're going to play Fibonacci Nim regularly, you should probably commit these to memory. Playing the game online is probably the best way to reinforce these numbers.
Let's take a look at two people playing Fibonacci Nim, and pay particular attention to the explanation of the winning strategy at the end:
So, the strategy, as mentioned, is simply to leave a Fibonacci number of objects at the end of your turn.
Is it really that simple? No. It works well enough with certain starting positions, including the standard 26, but when you start varying the numbers, this strategy isn't enough.
For example, what happens if you start with 33 objects? The nearest Fibonacci number is 21, so you might decide to remove 12 objects, and leave 21. Great, except that this means the other person can take up to 24 objects, and with only 21 objects in play, that gives the win to the second player!
Complete Strategy
So what went wrong in our game of 33 objects?
To analyze the game for any given number of objects, you need to first break it down into a series consisting solely of Fibonacci numbers.
Going back to the 26-object version, what's the highest Fibonacci number less than or equal to 26? 21, of course! What does that leave? 5! This happens to be another Fibonacci number. Thinking of 26 as 21 + 5 makes the next play easy to see. Take away 5, and leave 21.
Now, let's apply the same approach to 33. What's the highest Fibonacci number less than or equal to 33? Again, it happens to be 21. Subtracting 21 from 33 leaves 12, which isn't a Fibonacci number.
What do we do in this case? Break the number down again, and again, until all we're dealing with is Fibonacci numbers. What's the highest Fibonacci number less than or equal to 12? 8, and 12 - 8 = 4. 4 isn't a Fibonacci number, but 3 is, and 4 - 3 = 1. 1, of course, is a Fibonacci number, so we're all set!
All this means that 33 breaks down into 21 + 8 + 3 + 1. When you've broken down the number of objects down into its component Fibonacci numbers, your best play is to remove a number of objects equal to the smallest of the Fibonacci numbers in the problem. In the case of 21 + 8 + 3 + 1, that means your play should be to remove 1 object.
Playing the smallest number of objects is best strategy here because it gets you closer to your goal while also minimizing the options for your opponent.
I just went over to the Javascript version of this game, clicked on the newgame button, and it started with 48 objects. Let's see how this goes with this strayegy.
48 breaks down into 34 + 13 + 1, so:
Me: I remove 1, leaving 47. The computer can remove up to 2 objects.
Computer: The computer removed 2, leaving 45. I can remove up to 4 objects.
Me: 45 = 34 + 8 + 3, so I remove 3 objects, leaving 42. The computer can remove up to 6 objects.
Computer: The computer removed 6, leaving 36. I can remove up to 12 objects.
Me: 36 = 34 + 2, so I remove 2 objects, leaving 34. The computer can remove up to 4 objects.
Computer: The computer removed 4, leaving 30. I can remove up to 8 objects.
Me: 30 = 21 + 8 + 1, so I remove 1 object, leaving 29. The computer can remove up to 2 objects.
Computer: The computer removed 2, leaving 27. I can remove up to 4 objects.
Me: 27 = 21 + 5 + 1, so I remove 1 object, leaving 26. The computer can remove up to 2 objects.
Computer: The computer removed 2, leaving 24. I can remove up to 4 objects.
Me: 24 = 21 + 3, so I remove 3 objects, leaving 21. The computer can remove up to 6 objects.
Computer: The computer removed 6, leaving 15. I can remove up to 12 objects.
Me: 15 = 13 + 2, so I remove 2 objects, leaving 13. The computer can remove up to 4 objects.
Computer: The computer removed 4, leaving 9. I can remove up to 8 objects.
Me: 9 = 8 + 1, so I remove 1 object, leaving 8. The computer can remove up to 2 objects.
Computer: The computer removed 2, leaving 6. I can remove up to 4 objects.
Me: 6 = 5 + 1, so I remove 1 object, leaving 5. The computer can remove up to 2 objects.
Computer: The computer removed 1, leaving 4. I can remove up to 2 objects.
Me: 4 = 3 + 1, so I remove 1 object, leaving 3. The computer can remove up to 2 objects.
Computer: The computer removed 1, leaving 2. I can remove up to 2 objects.
Me: I remove both remaining objects, so I win!
To help you practice this strategy, try out this version of the game from cut-the-knot.org (Java required).
Set the Java version up by clicking the No more than twice radio button, and make sure the Hint checkbox is checked. This way, the computer will display the equation breakdown for you at each step. To play, you simply click the button with the number you wish to remove.
Once you get used to thinking of each number as a sum of Fibonacci numbers, and playing the smallest number, uncheck the Hint box, and try doing it without the equation being displayed. When you can win every time with no hints showing, you're almost ready to play the game against another player!
One Last Important Point
Wait, ALMOST?!? There is one last important thing to remember. If the number of starting objects is already a Fibonacci number, you must have the other player go first! Why?
Take 21 objects, for example. The first player must leave at least 1 object for the second player, so you can't remove all 21.
What if we think of 21 as the sum of 13 + 8? In that case, we removed 8 objects, leaving 13. Since 8 objects were removed, the other player can remove double that, or 16. Their move is a no-brainer – remove all 13 objects!
This is true for any Fibonacci number. Starting with 89, removing 34 to leave 55 means the other player can remove anything up to 68.
The reason for this comes back to Phi. If you start with a given Fibonacci number, multiply it by Phi, and round to the nearest whole number, you'll get the next Fibonacci number in the sequence. Since Phi is approximately 1.6180339887, multiplying by that, or anything more than that, such as the 2 in our doubling rule, makes Fibonacci numbers themselves a losing proposition.
Practice this version, play it against your friends, and let me know about your experiences!
Posts
No Response to "The Secrets of Nim (Fibonacci Nim)"
Post a Comment