Note:
To find this game in Zillions of Games click the "Nim"
tile, which has a picture of a ship. There are five initial setups
to choose from under the Variant menu.
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!
Reference:
Creating
Nim Games by Sherron Pfeiffer
Next
--> Best Play in Neutron
|