(NOTE: Check out the other posts in The Secrets of Nim series.)
My previous post discussed the math and logic behind single-pile nim, including several variations. Make sure you read and understand that post before reading this post.
Review and Practice
Obviously, with all the math involved, it's probably not surprising that, as soon as computer started appearing in universities in the 1970s, versions of Nim were right along there.
In the 1978 book BASIC Computer Games by David H. Ahl, several variations of Nim were included.
There was 23 Matches, which is the standard Misère Nim with 23 matches. Very close to this older version is the online version called Nim Skulls (Java required), which uses 15 skulls instead of 23 matches. Try getting the hang of this version, before moving on.
The next version up was usually Batnum, which allowed you to set more options, such as the number of objects, who went first, and whether the person who takes the last object was the winner or the loser. Rediware Software offers an online Nim version very similar to this, except that the computer chooses the number of objects, and it's always Misère Nim (Player who takes the last object loses).
If you practice these versions using what you've learned in my previous post, it shouldn't be too long before you master both of them.
Multi-Pile Nim
Another version in the same book is quite different, however. Simply called Nim, this version deals with multiple rows of objects, and you can take as many objects as you want from any single row (and ONLY one single row) on each turn.
In the late 1970s, one of the most popular versions of multi-pile Nim was a 1978 TRS-80 program called Android Nim. In 1979, it was translated for the Commodore PET computer, and it is this version which is shown below:
Leo Christopherson, who wrote the original TRS-80 version, later wrote an updated version for Windows computers.
If you want to try out Android Nim for yourself, you can either use the version, or one of the older versions with an emulator. If you download a TRS-80 Model 1/III/4/4P emulator from here, you can get the TRS-80 version of Android Nim here.
For the Commodore versions, you can get the VICE Emulator here, and then download the PET version here (Click on "Commodore PET Games" - it's on the very first "disk"), or download the Commodore 64 version here.
But how do you analyze this game in order to win it?
Binary Math
Yes, for multi-pile Nim, we have to use binary numbers (1s and 0s). Don't worry, though, as about 95% of the binary math you'll need can be explained to you in 60 seconds:
To get a clear head about binary, BetterExplained's article on number systems and bases is a great help.
Now, we will need to translate between decimal (our everyday 10-based counting system) and binary. Instead of working it out yourself, the easiest thing will probably be just to use these binary/decimal converters.
Binary Analysis of Nim
Let's look at a game of multi-pile standard Nim that's extremely easy to win. This version involves two piles of the same amount, say 5 objects. If the other person starts by taking all 5 objects from one of the piles, you win by taking the other 5 objects.
What if the other person takes less? If they took, say, 3 objects from one of the piles, leaving 2 objects in that pile, you would simply take 3 objects from the other pile, leaving 2 objects in the other pile. As you can quickly see, all the second player has to do is mirror the first, and he'll be able to take the last object every time.
Let's model this example game in binary:
Row A = 5 = 101
Row B = 5 = 101
When the board starts out, it looks this way in binary coding:
A: 101
B: 101
If the first player takes 3 from row A, he would be leaving 2 in that row. Since 2 = 010 in binary (0s on the left don't mean anything in binary, just as in decimal. Just as 12 and 012 have the same value, so do 10 and 010 in binary), the board would now look like this:
A: 010
B: 101
The 2nd player then does the same thing, so the board looks like this:
A: 010
B: 010
It's not tough to see that mimicking the other player in this particular case will always result in a win for the second player. This isn't always possible with more piles and varying numbers of objects in each pile, however.
Notice something else, though? Every time after the 2nd player made his move, the binary representation was such that there was an even number of 1s in each column (column - as in reading up and down, not across). The board began with row A being 101 (in binary), and row B being 101.
When the first player made their move by removing 3 and leaving 2 on the board, the columns became:
A: 010
B: 101
Now there's an odd number of 1s in each column! Each column has a single 1.
Regardless of the number of piles, when all columns have an even number of 1s in them, that position is considered “safe” for someone who is trying to take the last object. Ultimately, this is the trick to solving any size board of multi-pile standard Nim.
One other handy aspect to note: When a pattern has been made “safe” in this way by one player (or by being the starting pattern), the only possible remaining moves for the other player can only result in the pattern being unsafe. This means that a smart player can always keep the board safe for himself, and dangerous for the other player. Of course, if the board starts in an already-“safe” arrangement, you want the other player to go first.
Let's try using this to solve the Android Nim example above. In this case, row A has 7 objects, row B has 5 objects, and row C has 3 objects. Let's see that same situation in binary:
A: 111 (7)
B: 101 (5)
C: 011 (3)
Analysis becomes easier by making sure that all binary numbers have the same number of digits (since we're looking at columns), which is why I used “011” instead of just “11” for row C.
We start by looking at the columns. There's two 1s in the leftmost column, two 1s in the middle column, but three 1s in the rightmost column. Since there's at least a single column with an odd number of 1s, this opening layout is “unsafe” as is, and an opportunity for a smart player to go first and change it to a safe layout.
Obviously, if the opening layout is safe, then it would be to your advantage to let the other person go first.
How would we do this? Well, since only the rightmost column needs changing, changing from 111(7 in binary) to 110(6) would do it, as would changing 101(5) to 100(4), or 011(3) to 010(2). In this particular case, all we have to do is remove 1 object from any row, and we've made it safe!
Let's say we opt to go first, and take 1 object from row B, so the board now looks like this:
A: 111 (7)
B: 100 (4)
C: 011 (3)
So, let's say the other player removes 5 objects from row A (I'm using an actual game for this example), leaving 2 objects. What does the board look like in binary now?
A: 010 (2)
B: 100 (4)
C: 011 (3)
As stated earlier, the status of the board has been changed from safe to unsafe again. Notice that both the rightmost and leftmost columns have an odd number of 1s (one in both columns, as it happens)? To win, we need to make the board safe again. There aren't that many ways to do this, so it seems like row B (working with the row with largest amount is often a good starting point for this type of analysis) would be changed. We need to get rid of the 1 in the leftmost column and add a 1 in the rightmost column.
So, we need to change row B from 100(4) to 001(1). So, our next move is to remove 3 objects from row B, giving us this safe arrangement (the middle and rightmost column now have two 1s each, while the leftmost column has none):
A: 010 (2)
B: 001 (1)
C: 011 (3)
In the game I'm using for this example, the other person then took 2 objects from row C, leaving 1 object and giving us this unsafe arrangement (can you see why?):
A: 010 (2)
B: 001 (1)
C: 001 (1)
The only way to make this safe is to remove 2 objects from row A, the reasoning for which you should understand by now:
A: 000 (0)
B: 001 (1)
C: 001 (1)
It should now be obvious that the other player cannot win. They have to take the remaining object from either pile, and leaving the remaining object.
When you're always playing with the same arrangement, such as this 3, 5, and 7 arrangement, you can use this technique to analyze all the possible boards and, thanks to the memory systems you can learn from here, remember them for play.
The total number of cases for any arrangement, is the one greater than the total number of objects in each row (to account for the possibility of no objects in a row) multiplied together. In our 3, 5, and 7 arrangement, there's only 192 (8 * 6 * 4) possible arrangements to examine.
Also in that particular case, it turns out that the possible safe arrangements are small enough to remember. The first move should always be to remove 1 object from any row, and then to play to leave either rows of 2/4/6 (in any order), 1/4/5, 1/2/3, or 2 equal piles (which is easy to win, as discussed earlier).
The ease of winning standard Nim with a pair of equal piles also apples to more than 2 or more paired rows. Let's say you've left 4 piles on the board, 2 of which contain 3 objects each, and the other 2 piles contain 8 objects each (obivously, this started out as a very large game). You can easily see that the same mirroring strategy could be applied here.
For larger arrangements, you'd need a computer analysis to generate every possible safe state in which to leave the board. This game is usually played with 3, 5, and 7 precisely because the safe arrangements are few, and easy to memorize.
Review and Practice
Your homework? Go over to 21st Nim (Java required), and practice playing the game, starting with 2 piles (working eventually up to as many as you think you can handle), and win them using the analysis techniques you've learned here (don't forget to keep your binary/decimal converter handy).
If you're browsing with a browser that uses Flash, the 5-row Nim Master is a decent analytical challenge, as well. Make sure to choose “Normal Game: Take last stone to win”, so that you're analyzing the correct game.
Part 3 of the Secrets of Nim series will explore the unusual and surprising nature of multi-pile Misère Nim (the person who takes the last object loses).
Posts
No Response to "The Secrets of Nim (Part 2)"
Post a Comment