|
nim |
|
|
|
Nim
The game of Nim can be played with a number of heaps of matchsticks. The legal move is to strictly decrease the number of matchsticks in any heap (and throw away the removed sticks). Normal Play In normal play nim, the player who takes the last match is the winner.    A nim position with heaps of size six, five, and one To win at normal play nim, write the number of matches in each heap in binary (base two) notation. For the pictured position, these numbers are 5 = 1012 1 = 0012 Now add these numbers together without carrying: To make a winning move, subtract matches from an appropriate heap so that this "carry-free" or nim sum becomes zero. In the example, removing two matches from the heap of size 6 does it: 5 = 1012 1 = 0012 --------- 0 = 0002 If the nim sum of a position is already zero, there is no winning move. Such a position is called a P-position (for "Previous player winning"). Positions (such as the example) with nonzero nimsum are called N-positions, (for "Next player winning"). Misère Play In misère play nim, the player who takes the last match is the loser. Here is the winning strategy for misère play nim: To win at misère nim, play exactly as if you were playing normal play nim, except if your winning move would lead to a position that consists of heaps of size one only. In that case, leave exactly one more or one fewer heaps of size one than the normal play strategy recommends.Sibert-Conway Decomposition of Nim [Read the paper [PDF] for more explanation of this notation] (ie, P normal, N misère) E(1) (ie, all positions that consist of an even number of heaps of size 1) NP Positions (ie, N normal, P misère) D(1) (ie, all positions that consist of an odd number of heaps of size 1) |