The Game of Nim

In the game of nim:

There are some piles of stones and players. Each player take turns taking or more stones from a pile. The player that takes the last stone wins the game.

Since this is a non-random, perfect information game (i.e. a combinatorial game), the winner is already predetermined at the start of the game, assuming optimal play. ¹

Let a -position be a position where the previous player wins, and a -position be a position where the next player wins.

There a final -position, , where the previous player wins (no stones left to take).
There are some -positions, , that have at least move that lead to ( pile of stones).
There are some -positions, , where all possible moves lead to .

In a -position, there is at least move that leads to a -position.
In a -position, all possible moves lead to -positions.
A position is either a -position or -position.

Let the bitwise XOR (mod 2) () ² of every pile be the nim-sum , and let the number of stones in each pile be .

Crucially, XOR is associative and commutative, but also satisfies an additional property:
. ³ When a pile is reduced from to , becomes .

All -positions are positions where the nim-sum equals .

Proof. The final -position has the nim-sum . Every move from a -position changes the number of stones in a pile (i.e. the value of a single ), which changes the nim-sum to be greater than .

All -positions are positions where the nim-sum is greater than .

Proof. Let the highest bit set of the nim-sum be the th bit. There exists an with the th bit set, because there are an odd number of with the th bit set.
Since the th bit of is flipped from to and all the higher bits of are unchanged, . Hence, there exists possible move where we can reduce pile to stones, and change the nim-sum back to .

In the misère game with flipped objectives, the player that takes the last stone loses (and the player that starts his turn with no piles of stones wins).

Surprisingly, the optimal strategy is almost the same!

Since stones are removed from exactly pile each turn, the game will reach a -position where there is only pile more than stone, , and all other piles have just stone (or there are no other piles). Let this be the -position.

At the -position, we can either remove the whole pile or remove all stones except from the pile , depending on which move will leave an odd number of piles of stone behind.

After the -position, all piles have just stone so the game is forced for both players.

Hence, the winning player still ends each turn with nim-sum , except if it is the -position.

Nim with different incentives

We can modify nim with different incentives:

There are piles of stones and players. Each player take turns taking or more stones from a pile.

The player that takes the last stone gets coins, and the other player gets coin for each move made (by either player) in the game.

The only goal for each player is to win by getting more coins than the other player. (Taking the last stone is only beneficial if it allows the player to get more coins than the other player.)

Find the possible values of where both players will have exactly the same number of coins after a game (i.e. resulting in a draw).

Since there are piles of stones each, the first player (P1) has a nim-sum of and no control over who gets the last stone, while the second player (P2) has full control over who gets the last stone.

If P2 makes every move to return the nim-sum to , the game will eventually reach the -position.

At the -position, P2 can decide to take the whole pile of stones, or take all stones except from that pile. Let this be the -choice.

After the -choice, all piles have just stone and game is forced for both players.

At the -position, let be the total number of moves if P2 decides to take the whole pile of stones and there is an even number of piles of stone.

The total number of moves in the game will always differ by exactly depending on the -choice.

Hence, regardless of the value of and whether the number of piles of stone is even or odd, P2 can make the -choice such that P1 will never have more coins than P2.

P1 can force a draw if or and there is an odd number of piles of stone in the -position.

A specific situation where P1 can force a draw is when .
P1 takes stone from the largest pile each turn, and the only move for P2 that returns the nim-sum to is to similarly take stone from the largest pile. Since each player takes stone each every turn and there is a total of stones, it results in a draw with P2 taking the last stone.

Since is the maximum number of total moves possible, the maximum value of that will result in a draw is .

Instead of taking just stone from the largest pile, P1 can also take all the stones from the largest pile of stones, where . This forces P2 to similarly take stones from the largest pile to return the nim-sum to . Assuming that the initial total number of moves is , each time P1 makes such a move, the total number of moves is reduced by .

Somewhere in the game, P1 will start his turn in a position where is an even number of piles of stone, and exactly piles of more than stone. Let this position be a -position.

After P1 makes a move at the final -position, it will change into the -position, because the number of piles of more than stone is now exactly .

Recall earlier:

At the -position, let be the total number of moves if P2 decides to take the whole pile of stones and there is an even number of piles of stone.

Since this causes P2 to take the last stone, is even.

P1 can force a draw if or , and there is an odd number of piles of stone in the -position.

When is odd, and P2 forces P1 to take the last stone.
When is even, and P2 takes the last stone.

Following the strategy described, P1 should assume (for the sake of calculation) that P2 will always take the same number of stones as P1 every move, and aim for moves if is even, otherwise aiming for moves if is odd. ⁴

To ensure that there is always an odd number of piles of stone in the -position, P1 should always take all but stone from the largest pile in the final -position.

For , P1 and P2 each take a whole pile of stones every move. At the final -position, there are piles of stones, but if P1 takes all but stone from a pile, the game will have a total of moves, higher than the desired amount of moves.

Hence, will not result in a draw and the smallest value of that will result in a draw is .

For a draw, the possible values of .

Index- nim ⁵

In the game of index- nim:

There are some piles of stones and players. Each player take turns taking or more stones from at least but up to piles. The player that takes the last stone wins the game.

A player can win and take the last stone if any element in the nim-sum sequence (bitwise sum  of all the piles) is greater than at the start of the player’s turn.

Let the number of stones in each pile be .

We first convert each into binary (base ):
The nim-sum sequence, , for

A -position has at least element in the nim-sum sequence , and a -position has all elements in the nim-sum sequence .

Proof. The final -position is one with no stones left, and all elements in the nim-sum sequence . The -positions are positions where at least but up to piles of stones, taking all the piles leads to the final -position, and at least element in the nim-sum sequence ,

Similarly:

In a -position, there is at least move that leads to a -position.
In a -position, all possible moves lead to -positions.
A position is either a -position or -position.

Let be an empty set of piles. and let the last non-zero element in the nim-sum sequence be the th element in the sequence.

Then, select piles which have the th bit set that are not in , and add these piles to the set of piles . ⁶

Repeat the above step, decrementing such that is the previous non-zero element in the nim-sum sequence, until there are no non-zero elements before .

When the loop terminates, since each .
We can reduce each pile in the set of piles to change all elements in the nim-sum sequence back to .

Similarly, the strategy is the same in misère index- nim where the objective is flipped and the player that takes the last stone loses. The winning player still ends each turn with all elements of the nim-sum sequence , except if it is the -position.

The -position in index- nim is the -position where there are to piles with more than stone, and all other piles have just stone (or there are no other piles).

At the -position, the winning player can take stones from to piles such there there is piles of just stone left at the end of the turn.

After that, all piles have just stone. Each turn, the losing player takes piles, where , and the winning player takes piles, so piles are taken every turns.

In the end, the losing player is forced to the take the last pile of stone.

Index- nim with different incentives

Nim with different incentives can be modified for index- nim:

There are piles of stones and players. Each player take turns taking or more stones from at least but up to piles.

The player that takes the last stone gets coins, and the other player gets coin for each move made (by either player) in the game.

The only goal for each player is to win by getting more coins than the other player. (Taking the last stone is only beneficial if it allows the player to get more coins than the other player.)

Find the possible values of where both players will have exactly the same number of coins after a game (i.e. resulting in a draw).

We can follow the same strategy.
P1 takes stone from the largest pile, so P2 takes stone each from the largest piles as that is the only move that will change all elements in the nim-sum sequence back to .
Or P1 takes all the stones from the largest pile, so P2 takes all the stones from the largest piles as that is the only move that will change all elements in the nim-sum sequence back to .

The -choice at the -position is now whether P2 takes stones from to piles such there there is piles of stone left (for P1 to take the last stone), or such that there is piles of stone left (for P2 to take the last stone).
Similarly, depending on the -choice, the total number of turns is more or less.

The possible values of which result in a draw is the same, .

The complete proof is left as an exercise for the reader. 🙃