Nim

Resources

• https://cp-algorithms.com/game_theory/sprague-grundy-nim.html

Good explanation by ChatGPT below.

In the game of Nim, there are multiple piles of objects. On each turn, a player can remove any number of objects from one pile. The goal is to force your opponent into a situation where they cannot make a move (all piles are empty). The key to understanding the solution lies in the xor-sum of the pile sizes.

• Xor-Sum: The xor-sum of the pile sizes is the bitwise exclusive or (xor, denoted by ⊕\oplus⊕) of the sizes of all piles.
  • For example, if the pile sizes are a1,a2,…,ana_1, a_2, \ldots, a_na1​,a2​,…,an​, the xor-sum is calculated as a1⊕a2⊕…⊕ana_1 \oplus a_2 \oplus \ldots \oplus a_na1​⊕a2​⊕…⊕an​.

Theorem

The theorem states that the current player has a winning strategy if and only if the xor-sum of the pile sizes is non-zero.

• This is not very intuitive, it can be proven by induction

1. Winning and Losing Positions:
   • Losing Position: If the xor-sum of the pile sizes is 0, the player whose turn it is will eventually lose, provided both players play optimally.
   • Winning Position: If the xor-sum $\ne 0$, the current player has a winning strategy.

Proof Breakdown:

1. Base Case: When all piles are empty (the multiset is empty), the xor-sum is zero, and the theorem holds (the current player loses).
2. Induction Hypothesis: Assume the theorem is true for all states that can be reached from the current position. That is, if you reach a state with xor-sum zero, you’re in a losing position, and if you reach a state with non-zero xor-sum, you’re in a winning position.

Let $s$ be the xor-sum of the current position. We’ll define $t$ as the XOR value of the new position that we end up in. We have 2 different scenarios: 3. Case 1: $s=0$ (player is in losing position) - Consider any move the player makes by reducing a pile from size $x$ to size $y$. After the move, the xor-sum becomes: $t=s\oplus x\oplus y=0\oplus x\oplus y=x\oplus y$ - Since $y<x$, it follows that $x\oplus y\ne 0$. Thus, any move results in a new position where the xor-sum is non-zero, which is a winning position for the opponent. Therefore, the current player is in a losing position. 4. Case 2:$s\ne 0$ (player is in winning position) - Now, assume $s\ne 0$. The current player can make a move that turns the xor-sum to zero, putting the opponent in a losing position. - Let $d$ be the index of the leading non-zero bit in the binary representation of $s$. The player will reduce the size of a pile where the bit in position $d$ is set. Let $x$ be the size of that pile. - The player changes $x$ to $y=x\oplus s$. This choice ensures that the bit at position $d$ is cleared in the new pile size $y$, making $y<x$. Therefore, the move is legal. - Notice that we’re not choosing any arbitrary $x$. It’s true because we’re choosing an $x$ with the leading bit $d$ set - After the move, the new xor-sum becomes: $t=s\oplus x\oplus y=0$ - Thus, the current player forces the game into a state with xor-sum zero, putting the opponent in a losing position.

The proof shows that if the xor-sum is zero, the current player is in a losing position, and if the xor-sum is non-zero, the current player can always make a move that forces the opponent into a losing position. Hence, the theorem holds.

Related

• Sprague-Grundy Theorem