有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。获胜策略是在每座塔中的石头数量异或为 0 的位置后面留下一个位置。这迫使对手进入具有非零异或值的配置。然后第一个玩家可以再次到达 XOR 值为 0 的位置。

例如，从 {1,2,4} 开始，获胜的一步是走到 {1,2,3}。请注意 1 XOR 2 XOR 3 = 0。假设对手从最后一堆 {1,2,1} 拿走 2 颗石头，下一个获胜的棋子将完全移除第二堆：{1, 0, 1} 再次进行 XOR价值 0;等等。

有N个石头塔和2个玩家的游戏

Game where there are N towers of stones and 2 players

algorithm

data-structures

time-complexity

game-theory