问素数塔博弈的最优策略

EN

多堆游戏是一个有限的加法游戏，每个塔都是一个独立的游戏，人们可以选择下一个游戏，并保证游戏在有限的步骤中结束，并有一个清晰的胜利者。所有的加法游戏都可以减少到尼姆。

具体来说，立即输掉的nim得分是0，立即获胜的是1，否则一个n大小的塔有一个最小的可能的nim得分，你不能一步一步地达到，如果可能的话，nim的分数是从0, 1, 2, ...中提取出来的。

这使得我们可以递归地计算单个塔的nim分数。获胜的策略是总是给对方一个分数的0，最终你会让他们输掉的。请注意，如果给您的职位的nim分数大于0，则始终可以找到给对方一个0分数的移动(如果没有办法获得0，那么nim的得分将是0)。所以，如果你得到了一个0分数的职位，而另一个人打得正确，那么你总是会得到一个分数的0，最终我们会输掉的。

下面是关于加性游戏的基本结果。如果您可以计算每个多个塔的nim分数，则组合的nim分数只是单个nim分数的xor。

下面是尼姆的第一个分数。

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))可能值之后，您发现第一个值是无法实现的)。

要想真正发挥它，你不仅应该存储塔的尼姆分数，还应该查找如何从它得到更好的尼姆值。在一个单一的塔式版本，这让你立即知道如何发挥。在多塔版本中，它稍微复杂一些。当你得到一个有非零尼姆分数的位置时，你应该去找一个塔，它的尼姆得分在得分的领先二进制数中是1。你想和那座塔一起移动，让它的新的尼姆得分成为其他塔的xor。这个新的分数将总是小于它现在的尼姆分数，因此你将能够作出移动，并退回一个0分。

我找到了另一种解决方案--你需要始终保持塔中的数字是模6等于0，这样竞争对手就不能获得立方体的素数(或素数的幂)。

对于两个塔，你需要两个塔都是同样的模组，这意味着它们两个模块6必须是相同的。