Где мой недостаток в решении игры Misere Nim

Question

Игра состоит в том, что у вас есть N кучи камней, на каждом шагу игрока он должен удалить хотя бы 1 камень из кучи, а игрок, который удаляет последний камень, теряет.

я написал победитель в дюжине случаев, начиная с базового случаем

/* 
    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 
*/ 

и из что я думаю, что я вывел формулу

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"; 
} 

но это провалив тест, {2,1,3}, что должно привести к "Second".

Я стараюсь использовать следующий факт.

• Любое количество камней в куче, которая больше, чем 2 даст те же результаты, если бы это было 2. Причина в том, что если он больше, чем 2, и игрок не сжимает кучу до 1 на этом ходу, тогда игрок в основном дает своему противнику ход.

Однако, там может быть что-то я неправ ..

Answer 1

Я думаю, что ваше следующее утверждение выключено:

Любое количество камней в куче, что больше 2 будет дают те же результаты, если они были 2

Если состояние {1,2,2}, игрок может выиграть, удалив 1 камень. Если состояние {1,2,3}, первый игрок не может выиграть. Таким образом, существует разница между количеством камней 2 или 3.

потому что, если он больше 2, и игрок не сжимает кучу до 1 на этом ходу, тогда игрок в основном дает своему противнику поворот.

Это правильно, за исключением того, что иногда «желательно» давать поворот другому игроку, то есть проходить поворот.

Оптимальная стратегия связана с XOR количества элементов в каждой куче в двоичном представлении. См. https://en.wikipedia.org/wiki/Nim для оптимального решения и деталей.