Игра, где есть N башен из камней и 2 игроков

Question

Мне было интересно, есть ли простой способ увидеть рисунок здесь. Я думал об этом часами и не смог сформулировать его полностью.

Как работает игра, есть 2 игрока, N Башни камней, когда очередь игрока, он должен удалить по крайней мере 1 камень с башни, а игрок, который удаляет последний камень (ы), выигрывает.

Вот что я вытягиваюсь до сих пор, как карта высоты башен, кто победит:

// {1} ---> "First" (remove the single stone) 
// {2} ---> "First" (remove both stones) 
// {n}, n > 2 ---> "First" (remove all the stones) 
// {1, 1} ---> "Second" (because your only option is to remove 1 stone and then your opponent only has to remove 1 stone to win) 
// {1, 2} ---> "First" (because you can remove 1 stone from the 2nd tower and then your opponent is left with {1, 1} which makes him lose as I explained in the last one) 
// {1, 3} ---> "First" 
// {1, n}, n > 1 ---> "First" 
// {2, 2} ---> "Second" 
// {2, 3} ---> "First" 
// {2, 4} ---> "First" 
// {2, n}, n > 2 ---> "First" 
// {m, n} ---> m < n ---> "First" 
// {1, 1, 1} ---> "First" 
// {1, 1, 2} ---> "First" 
// {1, 1, 3} ---> "First" 
// {1, 1, n} ---> "First" 
// {1, 2, 2} ---> "First" 
// {1, 2, 3} ---> "Second" 
// {1, 2, 4} ---> "First" 
// {1, 2, 5} ---> "First" 
// {1, 2, n}, n > 3 ---> "First" 
// {2, 2, 2} ---> "First" 
// {2, 2, 3} ---> "First" 
// {2, 2, n}, n > 1 ---> "First" 

Фактов Я придумываю:

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

Либо я не могу найти достаточного количества шаблонов для написания линейного решения.

Любая помощь?

Answer 1

Эта игра известна как NIM. Победившая стратегия заключается в том, чтобы оставить позицию, позади которой XOR числа камней в каждой башне равен 0. Это заставляет противника перейти в конфигурацию с ненулевым значением XOR. Первый игрок может затем снова достичь позиции с величиной XOR 0.

Например, начиная с {1,2,4} выигрышным ходом является переход на {1,2,3}. Обратите внимание, что 1 XOR 2 XOR 3 = 0. Предположим, что противник берет 2 камня из последней кучи {1,2,1}, следующий победный ход полностью удалит вторую кучу: {1, 0, 1} снова делает XOR значение 0; и так далее.