博弈论学习笔记

挖个巨坑，慢慢填。

从 Nim 游戏入手

问题：有 \(n\) 堆石子，第 \(i\) 堆石子有 \(s_i\) 个，两个人轮流取石子，每人每次只能从一堆中取任意数量的石子，可以取完，不能不取。问先手必胜还是必败。

前置知识：

1. 异或 \(\oplus\)：有两个数均为 \(0\) 或 \(1\)，若它们相等则异或结果为 \(0\)，不相等结果为 \(1\)
2. 按位异或 \(\oplus\)：将两个正整数分别表示成二进制，对应位进行异或。易证，按位异或满足交换律、结合律，同时有自反性，即 \(a\oplus a=0\)
3. 异或和：若干个正整数 \(a_1,a_2,a_3,\ldots,a_n\) 的异或和为 \(a_1\oplus a_2\oplus a_3\oplus\ldots\oplus a_n\)。容易发现，若 \(s\)（二进制）中某一位为 \(1\) 的数字个数为奇数，则异或和中该位为 \(1\)；若为偶数，则异或和中该位为 \(0\)

结论：若 \(s\) 的异或和为 \(0\)，先手必败，反之则先手必胜。

感性理解一下。考虑只有两堆的特殊情况，如果两堆的数量相等，那么先手必败，策略为：先手从一堆中取若干个，后手从另一堆中取相同个数，则易证一定被后手取完。反之，如果两堆的数量不等，那么先手必胜，策略为：先从多的那堆里取若干个，使两堆数量相等，接下来同上（后手变为上面的先手）。

考虑用异或来解释。若先手取时两堆不相等（即异或和不为 \(0\)），则从多的那堆里取若干个使两堆相等（使得异或和变为 \(0\)）。接下来无论后手怎么取，一定会导致两堆数量不相等（使异或和不为 \(0\)）。先手从另一堆中模仿后手操作，使两堆再次相等（异或和重新变成 \(0\)），以此类推。

有了以上感性理解，我们就可以尝试推广到 \(n\) 堆的普遍情况。

定理一：当异或和不为 \(0\) 时，一定存在一种取石子方式使得异或和变为 \(0\)。

证明：

若我们所在的状态满足 \(s_1\oplus s_2\oplus\ldots\oplus s_n=m (m\ne 0)\)（\(s_i\) 表示第 \(i\) 堆的石子数），则\(s_1\oplus s_2\oplus\ldots\oplus s_n\oplus m=m\oplus m=0\)（自反性），所以只要随便选择一堆 \(s_i\) 变为 \(s_i\oplus m\) 即可。但是由于要“取”石子，所以要求变化后石子数必须减少，那么是否一定存在一堆 \(s_i\) 满足 \(s_i\oplus m<s_i\) 呢？答案是肯定的。

\(m\)（二进制）的最高位（设为第 \(k\) 位）的 \(1\) 一定是由 \(s\) 中奇数个 \(1\) 得来的，也就是在 \(s\) 中一定存在至少一个第 \(k\) 位为 \(1\) 的数。随便选一个，假设为第 \(i\) 个，则将上式最后的 \(\oplus m\) 与 \(s_i\) 结合，结果一定会比 \(s_i\) 小。因为 \(s_i\) 比 \(k\) 高的位不变，第 \(k\) 位由 \(1\) 变为了 \(0\)，剩下的无论怎么变结果都会比 \(s_i\) 小。

所以只要异或和不为 \(0\)，一定可以通过选合适的一堆取若干个石子使得 \(s_i\to s_i\oplus m\)，则异或和 \(m\to 0\)。

定理二：当异或和为 \(0\) 时，无论如何取石子，取后异或和都将不为 \(0\)。

证明：

假设取后异或和仍然为 \(0\)，则 \(m=0\)，又因为 \(m\) 只能选一堆结合，所以 \(s_i\) 只能不变。但题目要求必须取，与假设矛盾，所以取后异或和一定不为 \(0\)。

综上所述，当先手处于异或和不为 \(0\) 的状态时：

1. 先手一定可以通过一定方式变成异或和为 \(0\)（定理一）
2. 此时后手只能变成异或和不为 \(0\)（定理二），接下来重复步骤 1
3. 胜利状态的 \(s\) 全为 \(0\)，异或和为 \(0\)，而对手只能变成异或和不为 \(0\)，所以永远取不到胜利状态
4. 由于每步石子数必然会减少，最终一定会达到胜利状态，则胜利状态必然由先手取到

若先手处于异或和为 \(0\) 的状态，则任何操作都将导致异或和不为 \(0\)，接下来后手如上操作，则后手必胜。

未完待续，不定期更新。