Khighness、寻找必败态

1. 巴什博弈


1.1 问题

两个顶尖聪明的人在玩游戏，有 n 个石子，每个人每次拿 1~m 个石头，拿掉最后一块石头的人就是获胜者。请问先手与后手谁必胜？


1.2 分析

分类讨论:

（1）当n ≤ m时，这时先手的人可以一次取走所有的；

（2）当n = m+1时，这时先手无论取走多少个，后手的人都能取走剩下所有的；

（3）当n = k ∗ ( m + 1)时，对于每(m + 1)个石子，先手取i个，后手一定能将剩下的(m + 1 − i)个都取走，因此后手必胜；

（4）当n = k ∗ ( m + 1) + x ( 0< x< m + 1)时，先手可以先取 x 个，之后的局势就回到了上一种情况，无论后手取多少个，先手都能取走m+1个中剩下的，因此先手必胜。


1.3 结论

当n % m + 1) == 0时，后手必胜，否则先手必胜。


1.4 代码

1
2
3
4
5
6
7
8
9
public class BashGame {
    public void play(int n, int m) {
        if ((n % (m + 1)) == 0) {
            System.out.println("后手获胜");
        } else {
            System.out.println("先手获胜");
        }
    }
}

2. 尼姆博弈


2.1 问题

两个顶尖聪明的人在玩游戏，有 n 堆石子，第 i 堆有 ai 每个人每次能从一堆石子中取任意多个石子但不能不取，不能取的人输。请问先手与后手谁必胜？


2.2 分析

（1）当n = 1时，显然先手取走这一堆就能获胜；

（2）当n = 2且a1 != a2时，我们假设a1 > a2，先手可以先在第一堆取走a1-a2个，下一次无论后手取走多少个，先手都可以在另一堆取走相同的个数，因此先手必胜；

（3）当n = 2且a1 == a2时，先手无论取多少个，后手都可以在另一堆取相同的个数，因此后手必胜；

（4）当n >= 3时，问题变得繁琐起来，先找出规律性的结论。


2.3 结论

当 a1 ^ a2 ^ ··· ^ an = 0 时，后手必胜，否则先手必胜。

证明：

假设当前：a1 ^ a2 ^ ··· ^ an = 0，

先手回合：取走若干个后，

局势变成：a1 ^ a2 ^ ··· ^ an = K，

即：a1 ^ a2 ^ ··· ^ an ^ K = 0。

假设 K 的最高位1在第 x 位，

那么必然存在 aj (1 < = j <= n) 的 第 x 位为1，

后手回合：只要把 aj 变成 aj ^ K，

就能使得：a1 ^ a2 ^ ··· ^ an = 0。

由于 aj ^ K 使得第 x 位 为0，无论低位是什么，

第 x 位变为0后，aj 整个数一定会变小，即：aj ^ K < aj，

所以后手只需在第 j 堆取走(aj - aj ^ K)个石子即可。

先手每次取完，后手每次取(aj - aj ^ K)，

最后的局势一定是：a1 = a2 = ··· = an = 0，

此时先手无法取了，后手必胜。

反之，当a1 ^ a2 ^ ··· ^ an = K 时，

局势反转，先手每次取(aj - aj ^ K)个即可，先手必胜。


2.4 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
public class NimGame {
    public void play(int[] a) {
        int res = 0;
        for (int i : a) {
            res ^= i;
        }
        if (res == 0) {
            System.out.println("后手获胜");
        } else {
            System.out.println("先手获胜");
        }
    }
}

3. 尼姆Plus博弈


3.1 问题

两个顶尖聪明的人在玩游戏，有 n 堆石子，第 i 堆有 ai 个石子，每个人每次能从 1~d 堆石子中取任意多个石子但不能不取，不能取的人输。请问先手与后手谁必胜？


3.2 分析

特么太难了啊，呜呜呜我好菜


3.3 结论

将每堆石子数量用二进制表示，对于二进制的任意一位，如果这一位为1的石子堆数量%(d+1)==0，那么后手必胜，否则先手必胜。


3.4 证明

只需要证明三点：

  1. 终止局面为先手必败（显然）

  2. 任意先手必胜的局面都能转变成先手必败的局面

  3. 任意先手必败的局面都不能转变成先手必胜的局面

证明

证明2:

假设最高位%(d+1) != 0有m堆，那么将这些堆的这一位变成0；

假设下一位%(d+1) != 0的位有n个，之前m堆中这一位有a个1和b个0。

（1）如果n <= a，显然将这a中的n个变成0即可；

（2）如果(d+1) - n <= b，那么只要将b个中的(d+1) - n个变成1即可；

因为之前最高位是将1变成0，所以这一位即使由0变1，这堆石子也是减少的；

（3）如果两个都不满足，即a > n && b < (d + 1 - n)，那么只要将这a堆和m堆之外的(n - a)堆的这一位变成0，

那么总改变堆数为 a + b + (n - a) = b + n < (d + 1) - n + n = d + 1，

即将这一位变成%(d+1) = 0需要改变的总堆数要小于(d+1)，

即可以一次操作完成，然后以此类推就能使每一位都变为%(d+1)=0。

证明3:

因为一次最多操作d堆石子，因此不能将(d+1)堆某一位是1的石子堆的这一位都变为0。


4. 威佐夫博弈


4.1 问题

两个顶尖聪明的人在玩游戏，有 2 堆石子，每个人每次可以从任意一堆石子中取任意多的石子或者从两堆石子中取同样多的石子，不能取的人输。请问先手与后手谁必胜？


4.2 分析

威佐夫博弈不同于巴什博弈和尼姆博弈，它的特殊之处在于不能将两堆石子分开分析。

下面分析不想看的直接跳过记住结论即可

定义先手必输的局势为奇异局势，前几个奇异局势为: (0, 0), (1, 2), (3, 5), (4, 7), (6,10)……

假设 (x, y) 为第 k 个奇异局势

性质：

  • x为前 1···k 个奇异局势中没有出现过的最小正整数，y = x + k (打表找规律)
  • 任何一个自然数都包含在一个且仅有一个奇异局势中
  • 任何操作都会将奇异局势变为非奇异局势
  • 非奇异局势可以通过适当操作变为奇异局势

证明这个结论，只需证明：

  1. 任意自然数都出现过
  2. 任意自然数仅出现一次

反证法易证。

我们可以将两堆石子看成是棋盘上一个点的纵横坐标，那么游戏切换：

棋盘上有一个点，每次每个人只能将棋子往左或者往下移动任意个格子，不能移动的人输。

将能一步到达(0, 0)的点都染色，那么这些点就是必胜态，再找到横纵坐标之和最小的没被染色的点，

这个点就是下一个必败态，由此画出上图。


4.3 结论

根据Betty定理，第K个局势就是(⌊(1+√5)/2 *k⌋, ⌊(3+√5)/2 *k⌋)，其中(1+√5)/2=1.618是黄金分割系数。

因此，局势(x, y)满足(y - x)*(1+√5)/2)=x时，先手必败，否则先手必胜。


4.4 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class WizovGame {
    public void play(int a, int b) {
        // 保证 a <= b
        if (a > b) {
            int temp = b;
            b = a;
            a = temp;
        }
        // 判断 a == (b - a) * 黄金分割系数 (向上取整)
        if ( a == (int) Math.ceil( (b - a) * (1 + Math.sqrt(5.0)) / 2) ) {
            System.out.println("后手获胜");
        } else {
            System.out.println("先手获胜");
        }
    }
}

5. 斐波那契博弈


5.1 问题

两个顶尖聪明的人在玩游戏，有一堆石子，数量为n，两个人轮流取石子，规则如下：

（1）先手不能在第一次把所有的石子取完，至少取一颗；

（2）之后每次可以取的石子数至少为1，至多为对手刚取的石子数的2倍；

不能取的人输。请问先手与后手谁必胜？


5.2 结论

当n为Fibonacci数的时候，后手必胜，否则先手必胜。


5.3 证明

数学归纳法：

假设石子数量n = F[i]（斐波那契数列中的第i项{1, 1, 2, 3, 5······}）

（1）当 i = 2 时，n = 2，显然先手取一个，后手必胜

（2）当 i > 2 时，假设当 i <= k 时结论成立。

当i = k + 1时，F[i] = F[k] + F[k-1]，将石子分成两部分来看。

假设先手第一次取 x 个，后手第一次取 y 个。

1）如果 x < F[k-1] / 3，因为 n = F[k-1] 时已经证明后手一定能取到 F[k-1] 个中的最后一个，

所以问题转化成了有 F[k] 个中的最后一个，这个也已经证明后手一定能取到F[k]中的最后一个。

所以后手必胜。

2）如果 F[k-1] / 3 <= x <= F[k]时，则F[k-1]中剩余数量小于2x，后手可以直接取完，

（如果不选择一次性取完，慢慢磨最终也会是所证明的F[k-1]的情况，后手最后取完）

即后手取了F[k-1]-x个，即y <= 2/3 * F[k-1]。比较 2/3 * F[k-1] 与 1/2 * F[k] 的大小，

即比较4 * [k-1] 与 3 * F[k] 的大小：

由于 F[k] 函数递增 且 F[k] = F[k-1] + F[k-2]易知：2 * F[k-2] < F[k] < 2 * F[k-1]，

因而 3 * F[k] = 3 * F[k-1] + 3 * F[k-2] > 3 * F[k-1] + 3 / 2 * F[k-1] > 4 * F[k-1]。

也就是说，在后手取完F[k-1]那一堆石子之后，先手不能一次性取完F[k]那一堆石子，

于是问题最终演变成了F[k]的状况，后手最后取完。

3）如果 x > F[k-1]，因为F[k] < 2 * F[k-1]，后手可以一次性取完。

综上三种情况，当 i <= k 时结论成立，那么当 n = k+1 时结论也成立。


5.4 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class FibonacciGame {
    public int fibnacci(int n) {
        // 递归计算，慢
//        if (n == 1 || n == 2)
//            return 1;
//        else
//            return fibnacci(n - 1) + fibnacci(n - 2);
        // 公式计算，快
        return (int) Math.floor( ( Math.pow((1 + Math.sqrt(5)) / 2, n)  - Math.pow((1 - Math.sqrt(5)) / 2, n) ) / Math.sqrt(5) );
    }

    public void play(int n) {
        for (int i = 1; fibnacci(i) <= n; i++) {
            if (fibnacci(i+1) == n) {
                System.out.println("后手获胜");
                return;
            }
        }
        System.out.println("先手获胜");
    }
}