algorithm - 寻找改进 Nim 的更好方法

Question

它最终是一个经过一定修改的 nim 游戏。

规则如下:

有两个玩家A和B。

游戏是用两堆火柴进行的。最初，第一堆包含 N 个匹配项，第二个包含 M 个匹配项。

玩家交替轮流； A 先播放。

在每一轮中，当前玩家必须选择一堆并从中移除正数的火柴(不超过该堆当前火柴的数量)。

只有当另一堆中的火柴数除以 X 时，才允许从一堆中移除 X 根火柴。

从任意一堆中拿走最后一场比赛的玩家获胜。

两个玩家都发挥最佳。

我的看法:

假设我们有两堆 2 7。我们有 3 种情况可以将第二堆减少为 wiz : 2 1 , 2 3 , 2 5 如果 A 打得最好，他/她将选择 2 3 这样唯一的留给 B 的机会是做 2 1，然后 A 可以做 0 1 并赢得比赛。解决方案的核心是，如果 A 或 B 遇到任何可能在下一步中直接失败的情况，那么它会尽力避免这种情况，并通过在此之前的第 1 步离开状态来利用这种情况对他们有利失败阶段。

但是这种方法对于一些未知的测试用例失败了，有没有更好的方法来找到获胜者，或者任何其他违背这种逻辑的测试用例。

Answer 1

这是一个经典的动态规划问题。首先，找到一个递归关系，用较小的博弈来描述博弈的结果。这里的参数是 X 和 Y，其中 X 是一个堆栈中的匹配数，Y 是另一个堆栈中的匹配数。我该如何减少这个问题？

好吧，假设轮到我进行 X 场比赛，并假设 Y 可以被数字 a1、a2 和 a3 整除，而 x 可以被 b1、b2、b3 整除。然后，我有六个可能的回合。问题简化为求解 (X-a1, Y) (X-a2, Y) (X-a3,Y), (X,Y-b1), (X,Y-b2), (X, Y-b3 ).一旦解决了这六个较小的游戏，如果其中一个对我来说是必胜游戏，那么我将采取相应的行动并赢得游戏。
还有一个参数，就是轮到谁了。这使可解决问题的规模增加了一倍。
关键是找到所有可能的 Action ，并为每个 Action 重复，为效率保留已解决游戏的存储。

需要自然地弄清楚基本情况。