Nimvalue

Nimvalue is a concept used in combinatorial game theory, particularly in the analysis of impartial games. An impartial game is one where the available moves depend only on the state of the game, not on which player is moving. Nimvalue is a way to assign a numerical value to game positions, enabling the application of the Sprague-Grundy theorem.

The Sprague-Grundy theorem states that every impartial game under the normal play convention (where the last player to move wins) is equivalent to a nim heap of a certain size. This size is precisely the nimvalue, also known as the Grundy number or nimber, of the game position. The nimvalue of a terminal position (a position with no moves) is 0. For a non-terminal position, its nimvalue is the smallest non-negative integer that is not among the nimvalues of the positions reachable in one move. This operation is known as the mex (minimum excluded value) function.

For example, in the game of Nim, a position consisting of several heaps of objects is equivalent to a single nim heap whose size is the XOR sum of the sizes of the individual heaps. The nimvalue of a single heap of size n is simply n. Therefore, the nimvalue of a Nim position is the XOR sum of the heap sizes. A position with a nimvalue of 0 is a P-position (previous player winning), meaning the player whose turn it is to move from this position will lose if the other player plays optimally. A position with a non-zero nimvalue is an N-position (next player winning), meaning the player whose turn it is to move can force a win.