Nim-Value

Every position of every impartial game has a nim-value, making it equivalent to a nim-heap. To find the nim-value (also called the Sprague-Grundy number), take the mex of the nim-values of the possible moves. The nim-value can also be found by writing the number of counters in each heap in binary, adding corresponding binary digits (mod 2), and interpreting the resulting binary string as a decimal number.

If at any point in the game, the nim-value is 0 for a given player, the position is safe (i.e., he will always win if he plays correctly); otherwise, it is unsafe (i.e., he will always lose if the other player plays correctly). With two heaps in the game of nim, the only safe positions are . With three heaps (assuming nim-heaps of maximum size 7), the safe positions are (1, 2, 3), (1, 4, 5), (1, 6, 7), (2, 4, 6), (2, 5, 7), (3, 4, 7), and (3, 5, 6). For four nim-heaps of maximum size 7, the safe positions are , , and (1, 2, 4, 7), (1, 2, 5, 6), (1, 3, 4, 6), (1, 3, 5, 7), (2, 3, 4, 5), (2, 3, 6, 7), and (4, 5, 6, 7). The position (1, 3, 5, 7) corresponds to the beginning state for the game Marienbad, which is therefore an unfair game.

REFERENCES:

Ball, W. W. R. and Coxeter, H. S. M. Mathematical Recreations and Essays, 13th ed. New York: Dover, pp. 36-38, 1987.

Grundy, P. M. "Mathematics and Games." Eureka 2, 6-8, 1939.

Sprague, R. "Über mathematische Kampfspiele." Tôhoku J. Math. 41, 438-444, 1936.