algorithm - 石头游戏 - 2 名玩家完美游戏

Question

最近了解了nim游戏和grundy number
我被困在一个问题上。请给我一些想法

问题:
A和B用一堆石头玩游戏。 A开始比赛，他们交替移动。在每一步中，玩家必须从堆中移除至少一个且不超过 sqrt 的数字石头。因此，例如，如果一堆包含 10 block 石头，那么玩家可以从这堆中取出 1、2、3 block 石头。
A和B都玩得很完美。无法进行有效移动的玩家输了。现在你得到了石头的数量，你必须找到如果双方都打得最好的将获胜的球员。
例子

n=3 一场胜利，

n=5 B 赢

n<=10^12

我可以通过使用 Grundy number https://www.topcoder.com/community/data-science/data-science-tutorials/algorithm-games/ 用少量石头解决这个问题?

grundy 函数是 g(x)，其中 x 是剩余的石头。
调用 F(s) 是我们可以从 x 石头中获得的剩余石头数量的集合。
如果 s 是终端位置，则 g(s)=0

如果 s 不是终端位置，令 X = {g(t)| t 在 F(s)} 中。那么，grundy number of s 是 X 中不存在的大于等于 0 的最小整数。

例如 x=10 所以 F(x)={9,8,7} 取 1,2 或 3 个石头。 (sqrt(10)<=3)

如果 g(n)>0 => 第一个玩家获胜

g(0)=0

g(1)=1

g(2)=0

g(3)=1

g(4)=2
……

但是这个算法很慢。

提前致谢。

Answer 1

我要添加第二个答案，因为我的第一个答案提供了没有优化的背景理论。但由于 OP 显然正在寻找一些优化和没有大量​​递归的非常快速的解决方案，我接受了我自己的建议:

Of course, the really fast way to do this is to do some more math and figure out some simple properties of n you can check that will determine whether or not it is a winner or a loser.

我将使用我在那里定义的术语，所以如果这没有意义，请阅读该答案!具体来说，n 是堆大小，k 是要移除的棋子数量，如果玩家 A 从大小为 n 的堆开始有获胜策略，则 n 为赢家，否则为输家。让我们从以下关键见解开始:

Most numbers are winners.

为什么这是真的？对于小数字来说并不明显:0 是输家，1 是赢家，2 是输家，3 是赢家，4 也是如此，但 5 又是输家。但是对于更大的数字，它变得更加明显。

如果某个整数 p 很大并且是失败者，那么 p+1, p+2, ... p+k_m 都是一些 k_m 的获胜者，k_m 的大小大约为 sqrt(p)。这是因为一旦我找到了一个失败者，对于任何不比这大太多的堆，我可以移除一些石头让我的对手留下那个失败者。关键是确定 k 的最大有效值是多少，因为 k 是根据起始堆大小 n 而不是最终堆大小 p 定义的。

所以问题变成了，给定一个整数 p，对于 k 的哪个值，k <= sqrt(n) 其中 n = p+k 是真的。换句话说，给定 p，多少起始堆大小 n 允许我移除 k 并让我的对手留下 p。好吧，既然 n = p+k 并且值都是非负的，我们必须有

k <= sqrt(n) = sqrt(p+k) ==> k^2 <= p + k ==> k^2 - k - p <= 0。

对于 p 的任何固定值，这是 k 中的二次方程。可以使用二次公式找到解决方案集的端点:

k = (1 +- sqrt(1 + 4p))/2

因此，对于 (1-sqrt(1+4p))/2 和 (1+sqrt(1+4p))/2 之间的 k 值，不等式得到满足。当然，sqrt(1+4p) 至少是 sqrt(5) > 2，所以左端点为负数。那么 k_m = floor((1+sqrt(1+4p))/2)。

更重要的是，我声称 p 之后的下一个失败者是数字 L = p + k_m + 1。让我们尝试证明这一点:

Theorem: If p is a loser, then L = p + k_m + 1 is also a loser and every integer p < n < L is a winner.

证明:我们已经证明了区间 [p+1, p+k_m] 中的每个整数 n 都是赢家，所以我们只需要证明 L 是输家即可。

相反，假设 L 是赢家。然后存在一些 1 <= k <= sqrt(L) 使得 L - k 是失败者(根据定义)。由于我们已经证明整数 p+1, ..., p+k_m 是赢家，所以我们必须有 L - k <= p，因为没有小于 L 和大于 p 的数字可以成为输家。但这意味着 L <= p + k 并且 k 满足方程 k <= sqrt(L) <= sqrt(p + k)。我们已经证明方程 k <= sqrt(p + k) 的解不大于 (1+sqrt(1+4p))/2，因此任何整数解必须满足 k <= k_m。但是 L - k = p + k_m + 1 - k >= p + k_m + 1 - k_m = p + 1。这是一个矛盾，因为 p < L - k < L 并且我们已经证明没有更大的失败者小于 p 且小于 L。

QED

上述定理为我们提供了一个很好的方法，因为我们现在知道获胜者落入由单个失败者分隔的整数区间，并且我们知道如何计算两个失败者之间的间隔。特别是，如果 p 是失败者，则 p + k_m + 1 是失败者，其中

k_m = 楼层((1+sqrt(1+4p))/2)。

现在我们可以以纯迭代的方式重写函数，这种方式应该很快并且需要恒定的空间。该方法只是计算失败者的序列，直到我们找到 n(在这种情况下它是失败者)或确定 n 位于两个失败者之间的区间内。

bool is_winner(int n) {
  int p = 0;
  // loop through losers until we find one at least as large as n
  while (p < n) {
    int km = floor((1+sqrt(1+4p))/2);
    p = p + km + 1;
  }

  /* if we skipped n while computing losers, 
   * it is a winner that lies in the interval 
   * between two losers. So n is a winner as 
   * long as it isn't equal to p.*/
  return (p != n);  
}