java - Nim游戏问题

Question

好的，我必须制作一个 nim 游戏，并尝试通过以下 nim 游戏找到始终获胜的策略:

21 场比赛，玩家 1 和 2 每回合各进行 1、2、3、4 或 5 场比赛，并且不能与前一位玩家进行相同数量的比赛。如果/当他们拿下最后一场比赛时，该选手获胜。

我必须为此编写一些程序，但我什至不知道要开始。我怎样才能找到这种类型的 nim 游戏的获胜策略？

编辑:

所以我认为当你进行到 7 场比赛时，你总是会赢。另一个可以拿 2-5，最后一个加起来最多可以拿 7。当另一个拿 1 时，你拿 3(另一个不能拿 3)并且必须选择 1 或 2，在这种情况下你会得到最后一个并获胜。

但是，从 21 岁到 7 岁对我来说是个谜，我想不通你怎么总能成为达到 7 岁的人。

编辑 2: 好吧，如果没有你不能和以前的玩家一样的规则，我认为这很简单。

你会让 k = 5 + 1 = 6。然后你应该做第一步，使火柴剩下，然后 % 6 = 0。所以在这种情况下，先取 3，然后再填满另一个的移动玩家到 6。但是在这种情况下，这是行不通的，因为另一个玩家可以拿 3，之后你不能拿 3 来填满 6。所以这是我的问题。有什么想法吗？

编辑3:

好吧，你说我可以强制进行 7 场比赛。但是假设我对 14-7 匹配步骤采取相同的想法。 (然后就轮到对方了)

那么有两种情况: 1:他拿 2-5，我补到 7，让 7，我赢了。 2:他取了1，所以还剩13个。当我像在 (7-0) 步中那样拿 3 时，它变成 10。然后他拿 5，我不能再拿 5 来完成，我会松。

这就是问题所在，场景 2 在 (7-0) 步中没有问题，现在是。我该如何解决这个问题？

是的，解决方案:

顺便说一句，na speler 1 的意思是:在玩家 1 的回合之后等(我是荷兰人)。

好的，所以我尝试了一些方法，我想我找到了解决方案。您必须首先作为第一位玩家参加一场比赛。然后其他人可以参加 2-5 场比赛。你匹配(双关语)他的数量最多为 7，所以你将始终在中间留下 (21-1-7=) 13 场比赛。然后再次轮到玩家 2，有两种情况:玩家 2 进行 1、2、4 或 5 场比赛，在这种情况下，您进行的比赛与左边的 7 场比赛一样多。 (如前所述，当您进行比赛时，剩下 7 场比赛，您将永远获胜)。第二种情况是玩家 2 进行了 3 场比赛，在这种情况下，轮到您时中间有 10 场比赛。你不能用 3 来得到 7，因为你不能用相同数量的 2 倍。所以你拿了 5，所以还剩下 5。玩家 2 不能选择 5 来获胜，必须选择 1-4，之后你可以选择剩余的并获胜。

这就是我猜的解决方案。我以某种方式注意到了它，因为我注意到了这一点:

带有模数等的普通 Nim 游戏:

P2  1  2  3  4  5  
P1  5  4  3  2  1  
------------------
    6  6  6  6  6 

但是你不能在这里做 3,3 所以它是这样的:

p2 1  2  3  4  5 
p1    5  4  3  2  1
---------------------
      7  7  7  7 

所以你每次可以做7个，1个是特例。我不知道为什么，但我直觉地把 1 作为起点，因为感觉你需要采取主动才能控制对方的 Action 。 (一个人不能做两次 1，所以另一个人必须做 2-5 次，这让你可以控制)

无论如何，非常感谢所有的帮助。也适用于编写的整个程序。我无法使用它，因为它不会编译，因为缺乏良好的 Java 技能:)而且我也想自己解决它。

无论如何，我看到这是一个 wiki，祝以后尝试解决这个问题的人好运!

Answer 1

在这样的游戏中，您需要保持处于获胜位置的不变性(如果您已经处于获胜位置)。因此，您需要知道如何从获胜的位置开始，然后返回到它无论您的对手采取什么行动。

给你三个提示:

1. 你的 Action 组和对手的 Action 组相同:进行 1、2、3、4 或 5 场比赛。
2. 这个游戏，当你认真对待它时，它是一个加法游戏。是的，您正在减去匹配项，但在您制定策略时从加法的角度思考仍然有帮助。
3. 从这个开始:对于任何对手的移动 X(其中 X 是 1、2、3、4 或 5)，您可以采取什么移动来“取消”该移动？

我试图追求的概念在 modular arithmetic 的概念中得到了解释。 ，以防万一。

---

编辑:不过，不进行相同数量的匹配的限制使事情变得有趣。稍后我们必须将其作为一个极端案例来解决，但让我们首先看看您对我到目前为止所说的内容有何看法。请随时对此发表评论。

---

编辑 2: 您对一般第二个编辑的看法是正确的(如果不存在关于不重复移动的规则，我的意思是)。但您的第一次编辑是在正确的轨道上:您可以在 7 秒内完成工作。

不断地问自己并回答自己:

问:我如何通过让 AI 赢得最后一场比赛来可靠地迫使 AI 获胜？
A:强制AI离开7根火柴，然后用你的策略强制AI离开第7根火柴。这是因为您可以强制减去 7 个匹配项。
问:那么我如何通过确保 AI 赢得最后一场比赛(但七场)来迫使 AI 获胜？

不要想太多。采取你已经知道的——你已经可以让 AI 做的——并尽可能多地应用该步骤。

---

编辑 3: 这只是我想到的一个小问题，可能会帮助您解决您在第三次编辑中提到的问题。

如果对于移动集中的所有 X(1、2、3、4、5)，轮到 AI 时还有 2X 场比赛，那么您可以通过进行 X 场比赛来强制获胜。 (你在第三次编辑中详细说明了如何，除了其他玩家)

不幸的是，这不是你可以强制执行的事情，因为我说的是在 AI 轮到之前 有 2X 匹配，而其他策略的获胜条件取决于 之后的位置 AI 的回合，以便 AI 的移动可以强制它。

同样，您希望避免 AI 的移动导致任何 X 的 2X 匹配。