an impartial game is a game in which the allowable moves depend only on the position and not on which of the two players is currently moving, and where the payoffs are symmetric. In other words, the only difference between player 1 and player 2 is that player 1 goes first.
Types of impartial game positions
• A game is in a P-position if it secures a win for the Previous player (the one who just moved).
• A game is in a N-position if it secures a win for the Next player.
So in normal play Nim with three heaps, (0,0,1) is an N-position and (1,1,0) is a P-position. To find whether a Nim position is N or P, we work backwards from the end of the game to the beginning in a process called backwards induction:• A game is in a N-position if it secures a win for the Next player.
1. Label every terminal position as P.
2. Label every position that can reach a P position as N.
3. For positions that only move to N positions, label P.
4. At this point either all positions are labeled or return to step 2 and repeat the process until all positions are labeled.
Applying these rules to Nim, we first set the only terminal position (in other games there could be many) 0,0,0, to P. It is obvious that any position (0,0,n) is an N position, since the next player can just take the last heap in one turn.
Nimber arithmatic
Theorem 1. A position, (x1, x2, x3), in Nim is a P-position if and only if the nim-sum of its components is zero, x1 ⊕ x2 ⊕ x3 = 0.
You must find a move to a P-position, that is, to a position with an even number of 1’s in each column.
Read full article from My Experience: Impartial games problems
