|
|
|
|
|
|
|
|
|
Nim is a very simple game. Like Magic Squares, it's based on Boolean arithmetic and, in addition, a binary representation of integers. The most important operation for Nim is exclusive or or XOR defined by the following table
XOR applies bitwise to the binary representation of two or more numbers. For example, if x=7 and y=11 are two decimal numbers then their binary representations will be respectively. Therefore, x ^ y = 1100. If a, b, c denote the number of checked boxes in the three consecutive rows, then the winning move should leave
Quite often this would imply that the sum of two of the numbers equals the third one. For example, take a=1, b=4, c=5. However, it's not always the case. For example, if a=3, b=5, c=6 with 3^5^6=0. The reverse does not hold either (say, consider a=3, b=5, c=8. In this case, 3^5^8 = 14). Oftentimes such simplified strategy would result in loosing initiative to your computer which will never give it back. Now, bit is a position in a binary representation. There is a 0th bit (the rightmost one), the next is 1st, and so on. A bit is said to be turned on if the corresponding digit is one. Otherwise, it's turned off. The relationship a^b^c=0 is equivalent to saying that, considering all three numbers, every bit is turned on an even number of times, i.e., either 0 or 2.
Here is a proof. First of all, if after your move (1) holds while a, b, c are not 0, your opponent can't win on the next move. Condition (1) assures that for every bit turned on there is another bit on but in a different row. Since at every turn a player is allowed to uncheck boxes only in one row, it is impossible to turn all the bits off in one move. What must be shown is this: A) Any move in a position where (1) holds will result in a position where (1) does not hold. B) In a position where (1) does not hold there is always a move that leaves (1) true. To prove A) let us assume (1) and that c is not 0. Assume also that after c' boxes have been unchecked in the third row we still have
However, notice that (1) is equivalent to a^b = c whereas (2) is the same as a^b = c-c'. Therefore, c'=0. Which does not constitute a move. Contradiction. Proving B) will actually be giving away the algorithm used by the computer. Thus assume (1) does not hold, i.e. a^b^c = X different from 0. The most significant bit of X was contributed either by all three numbers or by just one of them. Let Y denote the binary number corresponding to this bit. Since it makes no difference let us assume that it's c that has contributed the most significant bit of X. With this we make a decision on our next move to uncheck boxes in the third row. The question is how many. The answer is clear from the previous - remove (c - (a^b)) checks. After that move the third row will contain a^b boxes so that a^b^(a^b)=0. We only have to prove that
Let Z denote the binary number comprising bits from c that canceled out by a^b. Then (c-Z) => Y > (a^b-Z) which proves (3). In practical terms, the program first finds the largest of a&X, b&X, and c&X. The largest of these three numbers contains the most significant bit of X. Here conjunction & is defined by the following table
Assume c&X is the largest of the three numbers. Then remove from the c's row (c-a^b) boxes. This number is bound to be positive and, after this operation, rows will contain a, b, and a^b boxes, respectively. These quantities satisfy (1). If, say, a&X proved to be the maximum, remove (a-b^c) boxes from the first row. The right move is not always unique. For example, assume we have the following distribution:
Note that in this case X=19^20^21=(10010)2=18 with the most significant bit corresponding to 16. The bit has been contributed by all three rows. Therefore, for all three rows there exists a winning move:
The game of Nim and the XOR operation are so fundamental in the Theory of Impartial Games that the latter has been often called a nim-sum. Nim has many incarnations of which some do not at all have an obvious relationship to the game. Nim-sum is even more widely spread and appears as an agent that glues together even not Nim - like games. Here is a list of pertinent games available at this site: Reference
Copyright © 1996-2009 Alexander Bogomolny |
| 33061457 |  |
