If you don’t remember how a normal Nim game works, let's have a quick recap.

Normal Nim Game:

Basically, you have any number of piles with any number of stones. It's a two-player impartial game. In a player's move, they can choose any number of stones from a single pile and remove them. The game ends when there are no piles or stones left. The player who takes the last stone wins, or the player who cannot make a move (because there are no stones left) loses.

Misere Nim Game:

Now, the rules of Misere Nim game are the same as normal Nim game, with the only exception being that here, the player who takes the last stone loses, or the player who cannot make a move (because there are no stones left) wins.

Solution of Normal Nim Game:

In a normal Nim game, in any state, if the XOR of the number of stones in all piles is 0, then the player who is making the move is in a losing position, no matter what move they make. Obviously, if the other player is not as dumb as me and moves optimally, initially, if the XOR sum of all piles is 0, player 1 loses the game; otherwise, player 2 loses the game.

Case 1: Initially XOR Sum 0:

In this case, no matter what move player 1 makes, they will make the Nim sum (XOR sum) non-zero. Hence, they will give their opponent a winning state. And then, if the 2nd player plays optimally, they will make a move such that the Nim sum becomes 0 again, hence giving player 1 a losing move. Here, we can see that player 2 is forcing player 1 to lose, and player 1 will end up losing. So, in one word, initially, if the Nim sum is 0, player 1 loses or player 2 wins.

Case 2: Initially Nim Sum Non-Zero:

In the first move, player 1 will make such a move that the Nim sum becomes 0, forcing player 2 into a losing position. Here, player 2 is useless; no matter what move they make, they will give player 1 a winning position because they cannot make the Nim sum 0, as they are already in a Nim sum 0 position. So, they will force to give player 1 a Nim sum non-zero position or a winning position. And eventually, player 1 will win the game.

Solution of Misere Nim Game:

Now, here things are a little bit complex. If we think of this like the opposite of normal Nim, as the conditions are kind of opposite, we face a problem. Here, it looks like in the base case when the Nim sum is 0, the player who is making the move is in a winning position (opposite of normal Nim). But...

Let the initial Nim sum be 0. If we assume this is a winning position, then player 1 will give player 2 a non-zero Nim sum, which is a losing position. Now, player 2 is not forced to give player 1 a 0 Nim sum or a winning state. So, they will give player 1 a non-zero sum, again a losing position. It doesn’t generalize the game. Or, in this way, we cannot simply say who will win or who will lose.

But if we look closely, it's all about who will take the last stone. So, if player 1 can force player 2 to take the last stone, player 1 will win; vice versa. This can be possible if we go back to normal Nim game. Here, we can say that if the Nim sum is 0 in a state, there must be more than one pile with 1 or more stones. For now, let's assume that the piles contain more than one stone.

Let this 0 Nim sum state be the initial state. Now, player 1 moves and gives player 2 a non-zero state, and then player 2 will give player 1 a 0 Nim sum state. The game will run and always end up in a position where there will be 2 piles with the same number of stones. The number of stones will be more than 1, as we have assumed. And the turn will be player 1's turn. Now, no matter what move player 1 makes, if player 2 plays optimally, player 2 can always force player 1 to remove the last stone. You can verify this.

Three cases can happen:

If player 1 removes one full pile, player 2 will remove another pile except one stone.

Else, if player 1 removes one pile except one stone, player 2 will remove another pile entirely.

Else, if player 1 removes some number of stones from a pile, player 2 will remove the same number of stones from another pile. (Continue)

So, for sure, we can say that if the initial XOR sum or Nim sum is 0, then player 1 loses or player 2 wins in a Misere Nim game, and vice versa.

Now, you can say that this is exactly the same as the Normal Nim game. Yes, it is. But if you remember when we solved the Misere Nim problem, we assumed that there would be more than one stone in at least one pile. But it is not always true in the actual game. So, here is a little corner case we have to handle. That is when all the piles contain a single stone. For example, if the piles are 1, 1. Then, from our solution, player 1 should be the winner, but you can see clearly player 1 will remove one pile, then player 2 must remove the other last stone. So, player 1 wins here. That means in this corner case, if the number of piles is even, player 1 wins; else, player 2 wins.

So, in conclusion, if the game is Normal Nim, then the XOR sum 0 is a losing state and vice versa. If the game is Misere Nim, same as before, XOR sum 0 is a losing state, but here we have to handle a corner case, that is if all piles contain a single stone.

Thanks for reading! For more discussion, please reach out at: [email protected]

This is my first CP blog, so your feedback is pretty valuable to me. --Md Redwan Hasan