|
NIM
STRATEGY
NIM
is a simple game involving piles of objects (we will call them "stones").
The objective of the game is to be the person who takes the last stone.
In any move, you must take away one or more stones from any single pile.
There
is a known perfect winning strategy to playing NIM. Let's use a simple
example to illustrate how to use this strategy.
Lets
say you have three piles with 1, 4 and 7 stones:
X
XXXX
XXXXXXX
To find
out the optimal move, we first express the count of each pile as a binary
number, using this table:
| Decimal |
Binary |
| 0 |
0000 |
| 1 |
0001 |
| 2 |
0010 |
| 3 |
0011 |
| 4 |
0100 |
| 5 |
0101 |
| 6 |
0110 |
| 7 |
0111 |
Next we
add up these binary numbers a special way:
0001 X
0100 XXXX
0111 XXXXXXX
----------------
0010 Special Sum
For any
column with an even number of 1's, we put down a zero. For an odd number,
we put down a one. In mathematics, this is called the "Exclusive Or". To
win, we want to get this sum to total 0000. Looking over the numbers above,
it looks like if we took this sum away from the third pile -- changing
a 7 (0111 in binary) to a 5 (0101 in binary) -- then the special sum would
become 0000.
You
continue this operation until you win the game. Of course, if your opponent
has left you with a special sum of 0000, then you will lose, assuming perfect
play on his part. And you thought math in school was boring! |
