algorithm - 如何确定哪个玩家会获胜

Question

两个玩家玩下面的游戏。在游戏开始时，他们从 n (1<=n<=100000) 堆石头开始。在游戏的每一步，玩家选择一堆并从该堆中取出至少一个石头，然后将零个或多个石头从该堆移到任何其他仍然有石头的堆中。如果玩家没有更多可能的动作，他就输了。给定最初的牌堆，确定谁赢：第一个玩家或第二个玩家，如果两者都玩得很好。

Answer 1

这是Nim的变体。了解 Nim 的解决方案应该可以帮助您更好地理解这个游戏。

对于 Nim 来说，游戏从n一堆石头开始。反过来，每个玩家选择一堆并从堆中取出至少一个，可能更多的石头。当没有更多的石头剩余时，游戏结束。

上面链接的维基百科文章很好地解释了获胜策略，其中涉及计算堆大小的二进制数字总和。仔细阅读，您应该能够解决此变体。

Answer 2

首先从分析已知结果的位置开始 - 这将是所有石头都在一个堆中的情况。然后你没有其他至少有一块石头的堆，所以你不能执行移动的第二部分（这是假设即使你移动 0 块石头仍然必须有另一个非空的堆）所以这是失去位置。

现在开始分析您可以从哪些位置进入亏损位置。这些将是您的第一轮获胜位置。

第一个观察：作为一个移动只影响两堆，很明显，只有当你正好有两堆时，你才能到达失败的位置。如果你只有两堆，你总是可以通过从其中一个中移除所有的石头来达到亏损的位置，因此这是一个获胜的位置。

因此，现在您必须考虑哪些位置会迫使您采取行动，将您带到找到的获胜位置。这些将再次失去位置（提示：我相信这只是您有 3 堆每堆 1 块石头的情况）。

以这种方式继续下去，最后你会想出最终的解决方案。我不想为你解决整个问题，因为这对你的技能没有好处。最好自己想出解决方案。

希望这可以帮助。

注意：如果您被允许对单个非空堆进行操作，即如果移动零棋子时您不需要另一堆非空堆，那么初始丢失位置是当您根本没有剩余棋子并且初始获胜位置是当您只有一堆带有任意数量的石头时。