Where is my flaw in solving the Misere Nim game

Question

The game is that you have N piles of stones, on each player's turn he must remove at least 1 stone from a pile, and the player who removes the last stone loses.

I wrote out the winner in a dozen or so cases starting with the base case

/*
    stones             | winner  | N | ones 
    ========================================
    {1}                | Second  | 1 |  1   
    {i}, i>1           | First   | 1 |  0
    {1,1}              | First   | 2 |  2
    {1,i}, i>1         | First   | 2 |  1
    {i,j}, i,j>1       | Second  | 2 |  0
    {1,1,1}            | Second  | 3 |  3
    {1,1,i}, i>1       | First   | 3 |  2
    {1,i,j}, i,j>1     | First   | 3 |  1
    {i,j,k}, i,j,k>1   | First   | 3 |  0
    {1,1,1,1}          | First   | 4 |  4
    {1,1,1,i}          | First   | 4 |  3
    {1,1,i,j}, i,j>1   | Second  | 4 |  2
    {1,i,j,k}, i,j,k>1 | First   | 4 |  1
    {i,j,k,m}, ...     | Second  | 4 |  0
*/

and from that I think I deduced a formula

static string GetWinner(int[] piles)
{
    int n = piles.Length, m = piles.Count(stones => stones == 1);
    if(m == n) // one stone per pile
        return n % 2 == 0 ? "First" : "Second";
    // if here, m < n
    return n % 2 == 0 ? (m % 2 == 0 ? "Second" : "First") : "First";
}

but this is failing the test case {2,1,3} which should result in "Second".

I try to use the following fact.

• Any number of stones in a pile that is greater than 2 would give the same results if it were 2. The reason is because if it's greater than 2 and the player doesn't shrink the pile to 1 on that turn then the player has basically give his opponent the turn.

However, there might be something I'm wrong about ..

Answer 1

I think your following statement is off:

Any number of stones in a pile that is greater than 2 would give the same results if it were 2

If the state is {1,2,2} The first player can win by removing the 1 stone. If the state is {1,2,3} the first player cannot win. So there is a difference between if the number of stones is 2 or 3.

because if it's greater than 2 and the player doesn't shrink the pile to 1 on that turn then the player has basically give his opponent the turn.

This is correct, except that it is sometimes 'desirable' to give the turn to the other player, i.e. passing the turn.

The optimal strategy has to do with the XOR of the number of items in each pile in binary representation. See https://en.wikipedia.org/wiki/Nim for the optimal solution and details.

Answer 2

I can not deeply understand the math behind the answer, but after some research and optimisation, this is the solution I came up with for python3:

from functools import reduce

def misereNim(s):
    if(max(s)==1):
        return "First" if (len(s) % 2 ==0) else "Second"
    else:
        xor = reduce((lambda x, y: x ^ y), s)
        return "Second" if xor == 0 else "First"

if __name__ == '__main__':

    s = [9, 8, 4, 4, 4, 7]

    result = misereNim(s)
    print(result)