博弈论（Nim 游戏）

本文主要是介绍博弈论（Nim 游戏），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

公平组合游戏ICG

若—个游戏满足:

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

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

Nim游戏

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

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

正确性证明：
设第 $i$ 堆石子的个数为 $a_i$ 个， $\oplus$ 为异或符号

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

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

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

在这里就可以看出，先手必胜态为 $\not = 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;
}

变化不大
892. 台阶-Nim游戏 - AcWing题库

#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 = 500010;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;
}

P1288 取数游戏 II - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
这题就是简单的不知道怎么做，和博弈有关系，但完全没必要。越想多越复杂

反 Nim 游戏

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

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

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

证明：
对于结论 $1$ ，显而易见，略过。
对于结论 $2$ ：
（1）当 $a_i > 1$ 只有 $1$ 个时。因为先手可以操控这堆为 $1$ 还是为 $0$ ，即可以操控 $a_i = 1$ 的数量为奇数还是偶数，因此这是必胜态，且此时 $\not= 0$ （易得）。
（2）当 $a_i > 1$ 至少有两个时。这也有两种状态。

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

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

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

SG函数

基本定义

Mex运算
设 $S$ 表示一个非负整数集合。定义 $\operatorname {mex}(S)$ 为求出不属于集合 $S$ 的最小非负整数的运算，即：
$\operatorname {mex}(S) = \min{x}$ ， $x$ 属于自然数，且 $x$ 不属于 $S$ 。

有向图游戏
给定一个有向无环图，图中有一个唯一的起点，在起点上放有一枚棋子。两名玩家交替地把这枚棋子沿有向边进行移动，每次可以移动一步，无法移动者判负。该游戏被称为有向图游戏。任何一个公平组合游戏都可以转化为有向图游戏。具体方法是，把每个局面看成图中的一个节点，并且从每个局面向沿着合法行动能够到达的下一个局面连有向边。

SG函数
在有向图游戏中，对于每个节点 $x$ ，设从 $x$ 出发共有 $k$ 条有向边，分别到达节点 $y_1,y_2 \dots y_k$ ，定义 $\operatorname {SG}(x)$ 为 $k$ 的后继节点 $y_1,y_2 \dots y_k$ 的SG函数值构成的集合再执行 $\operatorname {mex}(S)$ 运算的结果，即:
$\operatorname {SG}(x) = \operatorname {mex}[\operatorname {SG}(y_1), \operatorname {SG}(y_2) \dots \operatorname {SG}(y_k)]$
特别地，整个有向图游戏 G 的 SG 函数值被定义为有向图游戏起点 $s$ 的 SG 函数值，即 $\operatorname {SG}(G) = \operatorname {SG}(s)$ 。

使用方法

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

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

一般 SG 函数形式为： $\operatorname {SG}(状态)$ 。
首先终止状态的 SG 值为 0，即： $\operatorname {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;
}

894. 拆分-Nim游戏 - AcWing题库
这个也简单，但是涉及了 SG 函数的本质。

#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;
}