博弈论（Nim 游戏）

大家好，欢迎来到IT知识分享网。

公平组合游戏ICG

若—个游戏满足:

1. 由两名玩家交替行动;
2. 在游戏进程的任意时刻，可以执行的合法行动与轮到哪名玩家无关;
3. 不能行动的玩家判负;
   则称该游戏为一个公平组合游戏。
   NIM博弈属于公平组合游戏，但城建的棋类游戏，比如围棋，就不是公平组合游戏。因为围棋交战双方分别只能落黑子和白子，胜负判定也比较复杂，不满足条件 $2$ 和条件 $3$。
   
   

可以看出，公平组合游戏不存在平局，而且一定可以结束。

Nim游戏

问题：给定 $n$ 堆石子，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿），最后无法进行操作的人视为失败。
问如果两人都采用最优策略，先手是否必胜。

结论：如果所有石子数的异或和不等于 $0$，则先手必胜，反之先手必败。

• 如果每堆石子数都为 $0$，那么一定是先手必败，此时异或和为 $0$。
• 如果异或和 $x$ 不是 $0$。设 $x$ 在二进制下最高位 $1$ 为 $k$，那么一定有一个 $a_i$ 的二进制下第 $k$ 位为 $1$，那么一定有 $0\le a_i\oplus x<a_i$，那么我们可以从第 $a_i$ 堆拿走 $a_i-a_i\oplus x$ 个石子，那么 $a_i$ 就变成了 $a_i-(a_i-a_i\oplus x)=a_i\oplus x$，对于整体的异或和，就相当于又异或了一个 $x$，$x\oplus x=0$，所以我们一定可以一步吧当前 $x\ne 0$ 变为 $x=0$，使得对手每次面对的都是 $x=0$。
• 如果 $x$ 是 $0$。我们拿完石子后一定不能让 $x$ 依旧为 $0$。反证法：设我们拿完石子后可以让 $x$ 为 $0$，那么我们从第 $a_i$ 堆拿 $k$ 颗石子，那么新异或和 $y$ 就等于 $x\oplus a_i\oplus (a_i-k)=0$，因为 $x=0$，所以 $y=a_i\oplus (a_i-k)=0$，所以 $a_i=a_i-k$，所以 $k=0$。而 $k>0$，所以假设失败，也就是证明了我们拿完石子后不可能让 $x$ 依旧为 $0$。

总结一下，主要有三条关系：

• 如果 $a_i$ 都等于 $0$，那么一定先手必败。
• 我们一定可以一步吧当前 $x\ne 0$ 变为 $x=0$。
• 我们拿完石子后不可能让 $x$ 依旧为 $0$。
  也就是说我们一定可以让，对手面对的每次都是 $x=0$。但他无法改变，到我时 $x\ne 0$。又因为石子总数是不断减少的，所以他一定会先面临到 $a_i$ 都等于 $0$ 的状态，此时无法移动，也就盘他为失败，对于我就是胜利。说明结论成立。
  

在这里就可以看出，先手必胜态为 $x\ne 0$；先手必败态为 $x=0$。

值得注意的是，这个结论表述不是唯一的，但是和别的结论表述是等价的。

例题

891. Nim游戏 – AcWing题库

#include <iostream> #include <cstring> #include <algorithm> using namespace std; int n, m; int main() { 
    cin >> n; while (n -- ) { 
    int a; scanf("%d", &a); m ^= a; } if (m == 0) cout << "No"; else cout << "Yes"; return 0; } 

#include <iostream> #include <algorithm> #include <cstring> using namespace std; int n, m; int main() { cin >> n; int res = 0; for (int i = 1; i <= n; i ++ ) { int a; scanf("%d", &a); if (i & 1) res ^= a; } if (res) puts("Yes"); else puts("No"); return 0; } 

P1247 取火柴游戏 – 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

绿色的水题，看懂上面的 Nim 游戏就能做出来。

#include <iostream> #include <cstring> #include <algorithm> #include <cstdio> using namespace std; const int N = ; int n, m; int g[N]; int main() { cin >> n; int res = 0; for (int i = 1; i <= n; i ++ ) { scanf("%d", &g[i]); res ^= g[i]; } if (res) { int k = 0; for (int i = 31; i >= 0; i -- ) { if (res >> i & 1) { k = i; break; } } for (int i = 1; i <= n; i ++ ) { if (g[i] >> k & 1) { cout << g[i] - (g[i] ^ res) << ' ' << i << endl; g[i] = g[i] ^ res; break; } } for (int i = 1; i <= n; i ++ ) cout << g[i] << ' '; } else puts("lose"); return 0; } 

反 Nim 游戏

玩法和 Nim 游戏一样，只不过胜利标准变成了，不可移动为胜利。

结论：先手必胜条件为（下面为先手必胜的两种方式）：

1. 所有 $a_i=1$，且 $a_i$ 的数量为偶数，则先手必胜。
2. 当至少有一个 $a_i>1$ ，且所有 $a_i$ 的异或和 $x$ 为不等于 $0$，即 $x\ne 0$。

1. 当 $x=0$ 时。此时根据 Nim 游戏可知，操作一次后 $x$ 必定不等于 $0$，即变成下面的 2. ；或者操作一次后 $a_i>0$ 仅剩一个，即回 $(1)$，即给对方为必胜态。
2. 当 $x\ne 0$ 时，根据 Nim 游戏可知，此时一定可以让 $x=0$，且 $a_i>1$ 个数一定大于 $2$（如果只有一个 $a_i>1$，那么就和 $(1)$ 中 $x\ne 0$ 相悖）。即回到 1.。

可以看出 $(2).1$ 一定是必败态（因为它只能给对方必胜态，或者 $(2).2$，而 $(2).2$ 一定可以回到 $(2).1$，即不断循环，直到给对方必胜态），而 $(2).2$ 就是必胜态。

把 $(2)$ 和 $(1)$ 结合起来就得到，结论 $2$。证毕

SG函数

基本定义

使用方法

一般的博弈论问题都可以转化为 SG 函数求解。

以上为基本定义，现在来说说是干什么的。

一般 SG 函数形式为：$\mathrm{SG}(状态)$。
首先终止状态的 SG 值为 0，即：$\mathrm{SG}(终点状态)=0$。按照 SG 函数的运算，可得如图（红色为当前节点的 SG 值）：
![[博弈论1.png|269]]
如图可知，每个 SG 值不为 $0$ 的点，一定可以到一个 SG 值为 $0$ 的点；同理每个 SG 值为 $0$ 的点只能到一个 SG 值不为 $0$ 的点或者无法移动。这就和上面的 Nim 游戏有点像，如果先手（SG 值）不为 0，那么我可以让后手的每一次都为 0，反之同理。可以知道，SG 函数不为 0 那么先手必胜，反之先手必败。

因此对于两个绝顶聪明的人，这类游戏在开始就决定了胜负。

上面是一个图的情况。如果这个图有很多个会怎么样？即一个游戏，既可以在一个图上移动，也可以在其他图上移动。那么一个状态，有很多 SG 值，这时候就把每个图起始的 SG 函数都异或起来，变成一个异或和 $x$ 即可，如果 $x=0$，则先手必败，反之先手必胜。这个证明和 Nim 游戏的证明思路是一模一样的，这里不赘述。

注意有的题目需要计算 SG 函数，但是有的题可以不用，如最上面两个 Nim 游戏，直接运用结论就很快，当然也可以算 SG 函数，Nim游戏比较特殊，每堆石子数恰好就是它的 SG 函数值。

例题

893. 集合-Nim游戏 – AcWing题库

#include <iostream> #include <algorithm> #include <cstring> #include <unordered_set> using namespace std; const int N = 10010; int n, m; int g[N], f[N]; int sum; int sg(int x) { 
    if (f[x] != -1) return f[x]; unordered_set<int> s; for (int i = 1; i <= n; i ++ ) if (x - g[i] >= 0) s.insert(sg(x - g[i])); for (int i = 0; ; i ++ ) if (!s.count(i)) return f[x] = i; } int main() { 
    cin >> n; for (int i = 1; i <= n; i ++ ) cin >> g[i]; cin >> m; memset(f, -1, sizeof f); while (m -- ) { 
    int s; cin >> s; sum ^= sg(s); } if (sum) puts("Yes"); else puts("No"); return 0; } 

#include <iostream> #include <cstring> #include <algorithm> #include <unordered_set> using namespace std; const int N = 110; int n, m; int f[N]; int sg(int x) { if (f[x] != -1) return f[x]; unordered_set<int> s; for (int i = 0; i < x; i ++ ) { int a = sg(i); for (int j = 0; j <= i; j ++ ) { int b = sg(j); s.insert(a ^ b); } } for (int i = 0; ; i ++ ) { if (s.count(i) == 0) return f[x] = i; } } int main() { cin >> n; memset(f, -1, sizeof f); int res = 0; for (int i = 1; i <= n; i ++ ) { int a; cin >> a; res ^= sg(a); } if (res) puts("Yes"); else puts("No"); return 0; } 

拓展

博弈论的核心：保持自己在可胜态，且让对手无法改变其可败态或者改变我的可胜态。

可胜态，不是必胜态，但只要一直保持自己是可胜态，最后就必胜。同理，可败态不是必败态，但只要能让他一种在可败态，那么就是必败。

阻止对方所有能让我变成非可胜态的举动。（必胜态主导必败态，也就是说除非必胜放水，必败态无法转移到必胜态）。

另一种解释：如果一个状态可以到达一个必败态，那么它就是必胜态；如果一个状态不能到达一个必败态，他就是必败态。

例题