algorithm - 素数塔博弈的最优策略

Question

考虑以下游戏:

你有一个由 N 个立方体组成的塔。每一回合，玩家只能从塔中取出质数，或质数立方体的幂。赢家是最后一个玩的玩家，这意味着最后一个玩家获得质数(或质数的幂)的立方体并且没有更多的立方体。

注意事项:

1) 每回合的运行时间必须最短。

2)圈数没有限制

目标:

a) 找到一种算法来赢得比赛，并确定当只有一个塔时我们是否需要成为第一位玩家或第二位玩家。

b) 与 a 相同，但现在我们有 2 个塔，它们的立方体数量不同。

示例:如果我们有数字 N=6，如果我们先玩:

我们可以取 1，但玩家 2 将取 5 并获胜

我们可以取 2，但玩家 2 取 4 并获胜(2 是质数和 2 的幂)

我们可以取 3，但玩家 2 取 3 并获胜

我们可以取 4，但玩家 2 取 2 并获胜

我们可以取 5，但玩家 2 将取 1 并获胜

因此，在这种情况下，算法应该确定我们必须先玩，在这种特定情况下，我们可以选择丢弃我们想要的任意数量的立方体。

Answer 1

多堆版本是一个有限的加法游戏，因为每个塔都是一个单独的游戏，人们可以选择下一个玩哪个，并且游戏保证在有限的步骤中结束，并有明确的胜利者。所有加法游戏都可以简化为Nim .

具体来说，立即失败的 nim 分数是 0 , 立即获胜是 1 ，否则是一个大小为n的塔具有您无法一次达到的最小 nim 分数，其中可能的 nim 分数来自 0, 1, 2, ... .

这使我们能够递归地计算单个塔的 nim 分数。获胜策略将是尝试始终给对方得分 0 ，最终你会让他们失去。请注意，如果您获得的职位 nim 分数大于 0 ，你总能找到让对方得分为0的着法。 (如果没有办法得到 0 ，那么你的 nim 分数就会是 0 )。因此，如果您获得了得分为 0 的职位并且对方正确下棋，您将始终获得 0 的分数最终我们输了。

现在这是加法博弈的基本结果。如果您可以为多个塔中的每一个计算 nim 分数，则组合的 nim 分数就是 xor个人 nim 分数。

所以这是前几个 nim 分数。

0:  0 (you just lost)
1:  1 (nim(1-1) = 0)
2:  2 (nim(2-2) = 0, nim(2-1) = 1)
3:  3 (nim(3-3) = 0, nim(3-2) = 1, nim(3-1) = 2)
4:  4 (nim(4-4) = 0, nim(4-3) = 1, nim(4-2) = 2, nim(4-1) = 3)
5:  5 (nim(5-5) = 0, nim(5-4) = 1, nim(5-3) = 2, nim(5-2) = 3, nim(5-1) = 4)
6:  0 (can't get 0)
7:  1 (nim(7-7) = 0)
8:  2 (nim(8-8) = 0, nim(8-7) = 1)
9:  3 (nim(9-9) = 0, nim(9-8) = 1, nim(9-7) = 2)
10: 4 (nim(10 - 4) = 0, nim(10-9) = 2, nim(10-8) = 2, nim(10-7) = 3)

等等。很容易递归地计算这个。内存，它将是O(n**2 / log(n)) (对于每个 n 数字，构建您在所有 O(n / log(n)) 可能的移动之后可以达到的 nim 值集，然后从 0 开始计数，直到不超过 O(n / log(n)) 可能的值您找到了首先，这是无法实现的。)

要实际玩它，您不仅应该存储塔的 nim 分数，还应该查找如何获得可以从中获得的所有更好的 nim 值。在单塔版本中，让您立即知道如何玩。在多塔版本中，它稍微复杂一些。当您获得一个 nim 分数非零的位置时，您应该寻找 nim 分数在分数的前导二进制数字中为 1 的塔。您想与该塔一起移动，使其新的 nim 分数成为其他塔的异或。这个新分数将始终小于其当前的 nim 分数，因此您将能够进行移动并交回 0 分。