有没有办法简化我对 M 高 N 塔游戏的思考？

Question

总结一下这个游戏，有N个高度为M的塔，每回合玩家可以将一个塔缩小到除它的高度但不等于它的高度的数字，目标是让你的对手轮到他时没有可能的动作。

例如，如果 N=2,M=2 那么第一个玩家就输了，因为他唯一能做的就是将其中一个塔降低到 1 的高度，之后另一个玩家唯一能做的就是降低另一个塔高 1，现在第一个玩家没有动作可做。

我开始写这个，但它变得太复杂了，我无法在非素数 M 上真正看到 "pattern"，例如 4。我应该考虑这个问题有更好的方法吗？

1 --> Lose
1 1 --> Lose
1 1 1 --> Lose
etc. 

2 --> Win
2 2 --> Lose
2 2 2 --> Win
2 2 2 2 --> Lose
etc. 

3 --> Win
3 3 --> Lose
3 3 3 --> Win
3 3 3 3 --> Lose
etc.

4 --> Win
4 4 --> Lose (see tree below)

                   4,4                        1's turn
                  /   \
                 /     \
                /       \
               /         \
              /           \
            2,4           1,4                 2's turn  
           / \  \         /  \
          /   \  \       /    \
         /     \  \     /      \
        1,4   2,2 1,2  1,1     1,2            1's turn         
       /  \    \     \           \
      /    \    \     \           \
     1,1  1,2   1,2    1,1        1,1         2's turn
          /      \
         /        \
        1,1       1,1                         1's turn

我计算玩家 1 或 2 获胜的方式是这样的

static int Winner(int n, int m)
{
    if(m == 1)
        return 2;
    else if(IsPrime(m))
        return n % 2 == 0 ? 2 : 1;
    else
    {
       // ... ??
    }
}

编辑： 哇，我只是用

做了一个疯狂的猜测

static int Winner(int n, int m)
{
    if(m == 1)
        return 2;
    else
        return n % 2 == 0 ? 2 : 1;
}

并且通过了挑战题的所有测试用例。所以我"solved"它不明白为什么。

Answer 1

首先要考虑的是，当您缩小一座塔时，将其高度除以它的一个除数（除以 1）就像去掉一个或多个质因数。如果您用素数列表表示每座塔的高度，那么游戏就变成了 Nim 的变体。在每一轮中，一名玩家移除其中一个列表中的一个或多个数字，移除最后一个数字的玩家获胜。

具有 2 个高度为 6 的塔的示例游戏：

Tower 1 (height 6) : 2 3  <- First player removes one
Tower 2 (height 6) : 2 3

Tower 1 (height 2) : 2
Tower 2 (height 6) : 2 3  <- Second player removes one

Tower 1 (height 2) : 2    <- First player removes one
Tower 2 (height 2) : 2

Tower 1 (height 1) : 
Tower 2 (height 2) : 2    <- Second player removes one and wins

一旦你理解了这一点，你只需要知道如何用 N 堆 M 对象赢得 Nim 游戏。 And Nim has been mathematically solved for any number of initial heaps and objects.

因为在你的游戏中，玩家通过移除最后一个素数获胜，它类似于 Nim 的 "normal play"，玩家选择最后一个对象获胜。在这种情况下，获胜的策略是用 0 的 nim-sum 完成每一步，nim-sum 是每个堆中对象数量的异或。阅读维基百科页面以获取更多信息和示例。当游戏的 nim-sum 不为 0 时，总有可能采取使其为 0 的移动。否则是不可能的。因此，以 0 nim-sum 开始游戏意味着第一个玩家获胜，否则第二个玩家获胜。

在您的情况下，如果游戏开始时塔的数量是偶数，则 nim-sum 为 0，因为所有塔的高度都相同，先手者获胜。否则，如果塔的数量是奇数，则第二个玩家获胜。唯一的例外是高度为 1（这将是一个空的 Nim 游戏），默认情况下第二个玩家获胜。

这就是您的 "wild guess" 起作用的原因。

Answer 2

我们可以排除从高度1开始的塔。我们也可以排除从素数开始的高度。如果他们都是素数，那么每位玩家只有一种可能的着法。一个塔一次降到1高，直到他们都为1所以谁赢取决于n是否是奇数。

所以考虑 m 不是 1 也不是质数的情况。最快的游戏是将所有高度降低到 1，这将需要 n 步。如果移动结束时剩余的移动数为偶数，则移动的玩家获胜。如果 n 是奇数，则第一个玩家获胜。

所以玩家们试图在轮到他们之后将剩余的棋步走平。玩家可以通过将塔降低到最佳高度来将剩余步数增加 1。另一位玩家不能在同一座塔上重复此操作，因为该塔上只剩下一个动作。这样做的次数是 n，因此玩家能否将轮到的剩余步数变为偶数取决于 n 是否为奇数。

有没有办法简化我对 M 高 N 塔游戏的思考？

Is there a way to simplify my thinking about the N towers of M heights game?

algorithm

optimization

time-complexity

game-theory