【博弈论和 SG 函数 | 那忘算 10】巴什博奕 尼姆博弈及其变种 威佐夫博弈（附例题）

专栏指路：《再来一遍一定记住的算法（那些你可能忘记了的算法）》

前导：

博弈论（Game Theory）是研究具有斗争或竞争性质现象的数学理论和方法，也是运筹学的一个重要分支。

在信竞中，我们不需要对此了解太深，只要看懂原理证明后熟记模板。

1.巴什博奕（Bash Game）

规则

  • 有一堆物品，共个
  • 两个玩家轮流取物，每次可以取个，最后取光物品的人获胜

必胜策略

  • 若，则先手必败
  • 否则先手必胜

原理解析

当物品数量是的倍数时，无论先手取多少，

后手都可以取先手取的数量，使剩余物品数仍是的倍数。

最终会剩下个物品，先手无论取多少，后手都能取光获胜。

示例

  • ，先手必胜
  • 先手先取个，使剩余个（的倍数）
  • 之后无论对手取个，先手都取个
  • 最终先手获胜

代码：

（先手获胜输出 1，后手获胜输出 2）

#include<bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, K; cin >> n >> K; if (n % (K + 1) != 0) { cout << '1' << "\n"; } else { cout << '2' << "\n"; } return 0; }

至此，我们初步了解博弈的规则：

想尽办法让对手处于必败之地。

在巴什博弈中，当前玩家的物品数满足就是必败的。

因为无论怎么取，对方玩家都能让你回到必败状态。

而最小的必败状态为，最终游戏失败。

2.尼姆博弈（Nim Game）

规则

  • 有多堆物品，数量分别为
  • 两个玩家轮流从某一堆中取任意多的物品
  • 最后取光所有物品的人获胜

必胜策略

  • 计算所有堆物品数量的异或值：
  • （异或：把运算的两个数转成二进制，相同位为，反之为）
  • 若，则当前局面为必败态（先手必败）
  • 若，则当前局面为必胜态（先手必胜）

原理解析

  • 尼姆和（异或值）为的状态称为必败态（P-position）
  • 尼姆和不为的状态称为必胜态（N-position）
  • 而我们需要证明：
  • （1）必胜态的后续操作里必有一个必败态
  • （2）除外的必败态的后续操作都是必胜态
  • （3）必败态和必胜态交替出现，物品不断变少，终态为必败态

证明（1）：如果我们拿到必胜态异或值，设的二进制为的最高位为。

我们只要找中二进制为的最高位也是的，

（易证必定存在这样的，且必为奇数个）

让异或上，此时的第位变成，整体变小，符合操作规范。

全部的异或值变成，为必败态。

证明（2）：如果我们拿到必败态异或值，因为不是。

所以中肯定存在二进制第位为的数，且为偶数个。

只要让这些二进制第位为的其中一个的第位变成，整体异或值就不为。

（就是你无论怎么取都会脱离必败态，而且操作后的一定不为）

证明（3）：在保证双方都是最优策略的情况下，两态肯定是交替出现。

且每个都不断减小，最终为，是必败态。

例题指路：P2197 【模板】Nim 游戏 - 洛谷 (luogu.com.cn)

代码：

#include<bits/stdc++.h> using namespace std; int main () { ios::sync_with_stdio(false); cin.tie(0); int T; cin >> T; while (T--) { int n; cin >> n; int sum = 0; for (int i = 1; i <= n; i++) { int x; cin >> x; sum ^= x; } if (sum == 0) { cout << "No" << "\n"; } else { cout << "Yes" << "\n"; } } return 0; }

通过进一步的了解，我们发现：

应该让对手的下一次操作，也就是轮到我们时，是必胜的。

接下来的学习，我们会通过这些总结的规律，来给不同的情况建立尼姆博弈模型。

2.1.输出方案的尼姆游戏/取火柴

例题：

P1247 取火柴游戏 - 洛谷 (luogu.com.cn)

这道题要求我们在先手必胜的情况下，输出先手的取物方案。

根据前面的分析，我们知道要找中二进制为的最高位也为二进制为的最高位的。

同时题目要求字典序最小，for 一遍就好。

代码：

#include<bits/stdc++.h> using namespace std; const int N = 5e5 + 10; int a[N]; int main () { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; int sum = 0; for (int i = 1; i <= n; i++) { cin >> a[i]; sum ^= a[i]; } if (sum == 0) { cout << "lose" << "\n"; } else { for (int i = 1; i <= n; i++) { if ((a[i] ^ sum) < a[i]) { //如果异或上 S 的 a[i] 变小了，那么就说明这个 a[i] 第 k 位为 1 //如果 a[i] 第 k 位为 0，异或上 S 第 k 位肯定会变成 1，就变大了 //虽然这里不加括号优先级顺序也是对的，但还是保险起见 cout << a[i] - (a[i] ^ sum) << " " << i << "\n"; //注意是先输出拿了多少个，然后再 i a[i] = (a[i] ^ sum); //a[i] 变成取完的样子 break; } } for (int i = 1; i <= n; i++) { //再输出一遍 cout << a[i] << " "; } cout << "\n"; } return 0; }

2.2.尼姆游戏变形/反转硬币

题面：

在一条直线上排列着一行硬币，有的正面朝上、有的背面朝上。

2 名游戏者轮流对硬币进行翻转。

翻转时，先选一枚正面朝上的硬币翻转。

如果愿意，可以从这枚硬币的左边选取一枚硬币一同翻转（左边的硬币不一定要正面朝上）。

最后翻转使所有硬币反面朝上的玩家胜利。

输入：给你初始状态正面朝上硬币的集合。

解析：

假设初始状态第 x 个硬币是正面朝上的，如果翻动 x，有以下几种情况：

（1）不翻左边的

那么在正面朝上硬币的集合里，x 就会直接消失。

（2）翻左边的，左边的硬币反面朝上

那么在正面朝上硬币的集合里，x 会变成被翻的左边硬币的下标。

（3）翻左边的，左边的硬币正面朝上

那么在正面朝上硬币的集合里，x 和左边的硬币下标会一起消失。

注意到前面两种情况很像尼姆游戏，（1）是把大小为 x 的物品堆全部取完。

（2）则是从大小为 x 的堆里取出 （x -左边硬币的下标）个。

（3）可以理解为同样从大小为 x 的堆里取出 （x -左边硬币的下标）个，

而在初始堆个数集合（正面朝上硬币的集合）里，x 变成了左边硬币的下标。

发现现在的x 和左边硬币下标相同，两者异或值为 0。

也就是相当于不对尼姆和做出贡献，相当于：

在正面朝上硬币的集合里，x 和左边的硬币下标一起消失。

代码就不放了，就是尼姆博弈的板子。

2.3.*（必学）台阶型尼姆游戏（Staircase Nim）

题面：

游戏开始时有许多硬币任意分布在楼梯上，共阶楼梯从地面由下向上编号为到。

每次操作时可以将楼梯上的若干个（至少一个）硬币移动到楼梯上。

两名游戏者轮流操作，将最后一枚硬币移至地上的人获胜。

解析：

这次我们来尝试自己发现必胜策略。

考虑所有台阶只有一个台阶上有一个硬币的情况，易得：

如果这个硬币在奇数台阶上，先手必胜。

如果这个硬币在偶数台阶上，先手必败。

（第阶台阶是地面）

这可以同化到普通尼姆游戏的“所有堆只有一个堆有硬币”的情况。

于是，我们猜测：

台阶型尼姆游戏的必胜策略为，

当奇数台阶上硬币数的异或和不等于 0时，先手必胜。

反之必败。

该如何证明呢？还记得前面的三条定律吗：

  • （1）必胜态的后续操作里必有一个必败态
  • （2）除外的必败态的后续操作都是必胜态
  • （3）必败态和必胜态交替出现，物品不断变少，终态为必败态

只要证明我们猜测的必胜策略满足上面三条，那么该策略就是正确的。

读者自证不难，这里就不赘述了（好吧我还是讲讲）。

大家可以把偶数级台阶看作丢硬币的框子，把奇数台阶看作普通尼姆游戏的硬币堆。

和之前证明唯一的不同点就是是可以变大的。

如果遇到了奇数台阶全为的情况，但还有偶数台阶不为 0。

那这时候无论怎么做，都会让一个奇数台阶变大，就相当于增加。

而之后的操作虽然会增加有些，但最后所有硬币都会流向更低的台阶，

也就是地面，可以证明所有硬币流向地面一定是经过偶数次操作。

这时轮到的人是遇到奇数台阶全为的情况的人，游戏失败。

所以奇数台阶全为的情况是必败态。

总结：

对于上一个物品堆的数量可以传递到下一个的博弈，是阶梯尼姆博弈。

做这类题的时候要注意哪类变量可以相邻传递，判别哪些是无关紧要的“偶数阶梯”。

例题：

原题：[POJ1704] Georgia and Bob

acwing 链接：236. 格鲁吉亚和鲍勃 - AcWing题库

解析：

注意到：

选择一个棋子，并将其向左移动，但是不能越过任何其他西洋棋棋子或超过左边界。

也就是当前棋子 i 的移动范围只有i 的前面至棋子 i - 1 的后面。

当 i 往前移动，i + 1 的移动范围增加 1。

而所有棋子移动范围归 0 时为必败态（终态）。

那台阶尼姆模型就已经很明显了：

我们把1 格到第 1 个棋子间的空白格（第 1 个棋子的可移动范围）作为 a[n]。

第 1 个棋子和第 2 个棋子间的空格（第 2 个棋子的可移动范围）作为 a[n - 1]，以此类推，

第 n - 1 个棋子和第 n 个棋子间的空格（第 n 个棋子的可移动范围）作为 a[1]。

（因为台阶模型的模板就是 a[i + 1] 传递到 a[i]，所以这里这样定义）

还有一个比较阴的就是输入的位置不是从小到大，需要自己排。

代码：

#include<bits/stdc++.h> using namespace std; const int N = 1e3 + 10; int a[N], p[N]; int main () { ios::sync_with_stdio(false); cin.tie(0); int T; cin >> T; while (T--) { int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> p[i]; } sort (p + 1, p + n + 1); int sum = 0, last = 0; // 假如第 1 个棋子在 2 格，那么它的可移动范围就等于 2 - 0 - 1 for (int i = 1; i <= n; i++) { a[n - i + 1] = p[i] - last - 1; // 假如上一个棋子在 3 格，当前棋子在 5 格，那么可移动范围就是 5 - 3 - 1 last = p[i]; } for (int i = 1; i <= n; i++) if (i & 1) { sum ^= a[i]; } if (sum != 0) { cout << "Georgia will win" << "\n"; } else { cout << "Bob will win" << "\n"; } } return 0; }

2.4.多堆限制型尼姆游戏（Moore's Nim_k）

规则

n 堆石子，每次可以从不超过 k 堆中取任意多个石子，最后不能取的人失败。

判断

把 n 堆石子的石子数用二进制表示，统计每个二进制位上 1 的个数。

若每个二进制位上 1 的个数全部为 0，则先手必败，否则先手必胜。

解析

我们发现，这和之前讲过的巴什博弈有点像，其实两者本质原理是一样的。

如果当前为必败态（非终态），这轮的玩家取完。

下一轮的玩家只要遍历所有二进制位，如果当前二进制位有堆被取过，

那当前玩家就取该位为的 1 的堆，直到该二进制位 1 的个数为 0。

2.5.反尼姆游戏（anti-nim）

规则

有多堆物品，数量分别为，

两个玩家轮流从某一堆中取任意多的物品，最后取光所有物品的人失败。

判断

一个状态为必胜态，当且仅当：

（1）所有堆的石子个数为 1，且尼姆和为 0。

（2）至少有一堆的石子个数大于 1，且尼姆和不为 0。

解析

顾名思义，就是取光物品反而失败的尼姆游戏。

那判断条件为什么不是普通尼姆游戏反着来呢？

我们看单堆的情况，在普通尼姆游戏，数量不为 0 的单堆是必胜态。

但在反尼姆游戏中，单堆且数量为 1 才是必败态。

这是因为两者遵循不同的取胜技巧：

  • 在普通尼姆中，当只剩一堆石子时，玩家会取走所有石子获胜
  • 在反尼姆中，当只剩一堆且 > 1 个石子时，玩家会留下 1 个石子迫使对手失败

所以我们应该以一个新的视角去看待反尼姆。

分类讨论下：

（1）所有堆的石子个数为 1，有奇数堆

很明显，这是必败态。

（2）所有堆的石子个数为 1，有偶数堆

这是必胜态。

（3）其他情况

经过2.4的思考，你应该稍微有点头绪：

假设上一个玩家面对的状态是每个二进制位上 1 的个数都是 2 的倍数，

当前玩家只要遍历上一个玩家取过堆的所有二进制位，

如果该二进制位被改变了，那就去找其他这个位为 1 的堆， 把那个堆的 1 取出来就行。

所以上一个玩家是必败态。

更归纳的想，如果每个二进制位上 1 的个数都是 2 的倍数，

那么当前状态的尼姆和就为 0，反之不为 0。

也就是尼姆和为 0 的是先手必败态，反之为必胜态。

（意外的和普通尼姆的判断方式一样呢）

例题：

P4279 [SHOI2008] 小约翰的游戏 - 洛谷 (luogu.com.cn)

代码：

很板的反尼姆，按照判断部分打就行。

#include<bits/stdc++.h> using namespace std; const int N = 510; int a[N]; int main () { ios::sync_with_stdio(false); cin.tie(0); int T; cin >> T; while (T--) { int n; cin >> n; int sum = 0; bool flag = 0; for (int i = 1; i <= n; i++) { cin >> a[i]; if (a[i] != 1) { flag = 1; } sum ^= a[i]; } if (flag == 0) { if (n & 1) { cout << "Brother" << "\n"; } else { cout << "John" << "\n"; } continue; } if (sum != 0) { cout << "John" << "\n"; } else { cout << "Brother" << "\n"; } } return 0; }

2.6.*（必学）树上阶梯尼姆/初见SG 函数

（很抱歉我没有把这道题放在2.3后面，但我觉得按难度排的话这样是最好的。）

例题：

P2972 [USACO10HOL] Rocks and Trees G - 洛谷 (luogu.com.cn)

哎，洛谷这糟糕透顶的题面，别看。

看我的：

首先，再来回顾下我们的两种状态。

在任何回合制游戏中，在双方都绝对聪明（最优解），一个局面只有两种命运：

  • 必败态（P-position）：轮到你走，但你不管怎么走，都会把“胜利”拱手送给对方。

  • 必胜态（N-position）：轮到你走，你至少有一种走法，能把“必败”扔给对方。

判断规则很简单：

  1. 没有可走（游戏结束状态）→必败。

  2. 如果所有走法都会走到“必胜态” → 当前是必败
    因为你无论怎么走，都会把“必胜”送给对方，那你不是输定了吗？

  3. 如果存在一种走法能走到“必败态” → 当前是必胜
    因为你可以故意走那一步，把“必败”扔给对方，让对方头疼去。

至此，我们再次总结博弈论的底层逻辑：

尽量把烂摊子留给对方。

2.6.1.介绍SG 函数和mex

一个游戏局面，如果轮到某人操作：

  • 不能操作的局面的 SG 值 = 0。

  • 一个局面的 SG 值 = 它所有“走一步之后”的局面的 SG 值中，没有出现过的最小非负整数。

    • 这个操作叫 mex（最小排除值）。

定义：当前状态 SG 函数如果为 0，则必败，不为 0 则必胜。

  • 如果局面能一步走到 SG=0（必败），那mex不会选 0，它至少会选 1。 SG > 0 →必胜。

  • 如果局面所有走法都去不了 SG=0，那mex就只能选 0。所以 SG = 0 →必败。

所以，SG 值是否为 0，直接对应“必胜 / 必败”。

我们发现这里的SG 函数的定义就是前面所说的尼姆和，只不过，我们换了种方式证明。

同时SG 函数和 mex的运用范围也更广，任何满足：

双人轮流、零和（只分输赢，不和局）、游戏过程透明、无随机性、有限性（一定会结束）

即所谓“公平组合游戏”。

的游戏都可以使用 SG 函数来判断胜负态。

2.6.2.重新理解异或

当游戏被劈成好几段（分成小游戏）时，它们互不干扰，轮流操作时你一次只能动其中一段。

就相当于尼姆游戏一次只能取一个堆，本题一次只能移动一个点的石子。

这时候，不能直接把 SG 值加起来（比如 1+1 = 2），考虑使用异或（XOR）。

因为异或有一个神奇的性质，它完美符合“必胜/必败”的传递规则：

如果一堆数字的异或结果是 0，那么你只要改变其中一个数字，

（把它变小或变任意数），异或结果一定不是 0。


如果异或结果不是 0，那么你总能找到一种方法，

只改变其中一个数字，让新的异或结果变成 0。

这完全对应了第一步里的“必胜/必败”规则：

  • 总异或 = 0（必败）：无论你怎么操作（相当于改变其中一个 SG 值），结果必然非 0（走到必胜态）。

  • 总异或 ≠ 0（必胜）：你一定有办法把它变成 0（走到必败态）。

解析：

说回本题，是个很明显的阶梯尼姆，只要异或上树奇数层的点的 SG 值，就能判断答案。

（从根节点 1（0层）开始，一层层往下层数递增）

考虑求出每个点的 SG 值。

注意到：

“最多 L 个石头从这个节点，向树根靠近一个单位。”

那么对于石头数量的点，。

（都可以达到，只有本身不行）

对于石头数量的点，。

对于石头数量的点，。

以此类推，得：

换个脑子想这不就是巴什博弈嘛。

代码：

#include<bits/stdc++.h> using namespace std; const int N = 1e4 + 10; int sg[N], p[N], r[N], dep[N]; int main () { ios::sync_with_stdio(false); cin.tie(0); int n, T, L; cin >> n >> T >> L; for (int i = 1; i <= 1000; i++) { sg[i] = i % (L + 1); } int sum = 0; dep[1] = 0; for (int i = 2; i <= n; i++) { cin >> p[i] >> r[i]; dep[i] = dep[p[i]] + 1; if (dep[i] & 1) { sum ^= sg[r[i]]; } } for (int i = 1; i <= T; i++) { int x, y; cin >> x >> y; if (dep[x] & 1) { //不是奇数层对异或值没影响 sum ^= sg[r[x]]; // 再异或上一次就相当于没异或 r[x] = y; sum ^= sg[r[x]]; } if (sum != 0) { cout << "Yes" << "\n"; } else { cout << "No" << "\n"; } } return 0; }

2.7.有向无环图的尼姆游戏/再会 SG 函数

题面：

来源：USACO 2006 January Gold

样例输入：

4
2 1 2
0
1 3
0
1 0
2 0 2
0
4
1 1
1 2
0
0
2 0 1
2 1 1
3 0 1 3
0

样例输出：

WIN
WIN
WIN
LOSE
WIN

解析：

拓扑好序列，按照拓扑序列从后往前，

没有后继的点的 SG 值为 0（必败），有后继节点的点就用mex 函数。

最后的总状态为所有点的SG 值的和（异或和）。

（我觉得不太难，代码写了注释，直接看就好）

代码：

#include<bits/stdc++.h> using namespace std; const int N = 1010; int sg[N], n; vector<int> G[N]; int dfs_SG(int x) { if (sg[x] != -1) { //记忆化搜索 return sg[x]; } bool v[1010] = {0}; //一定要在里面定义 for (int y: G[x]) { v[dfs_SG(y)] = 1; // mex{SG[y]} } int i = 0; while (v[i]) { // 从 0 开始找第一个没出现过的 SG i++; } return sg[x] = i; } int main() { ios::sync_with_stdio(false); cin.tie(0); while(cin >> n) { memset(sg, -1, sizeof(sg)); for (int i = 0; i < n; i++) { int x; cin >> x; G[i].clear(); //多测要清空 for (int j = 1; j <= x; j++) { int y; cin >> y; G[i].push_back(y); // 建图 } } int m; while (cin >> m) { if (m == 0) { break; } int sum = 0; for (int i = 1; i <= m; i++) { int x; cin >> x; sum ^= dfs_SG(x); } if (sum != 0) { cout << "WIN" << "\n"; } else { cout << "LOSE" << "\n"; } } } return 0; }

2.8.要求从集合中选数的尼姆游戏

题面：

POJ 2960 S-Nim

代码：

实在是太简单了，我真的不想写解析。

（其实这个做法的复杂度存疑，不过现在机子跑得快，过这道题绰绰有余）

#include<bits/stdc++.h> using namespace std; const int M = 1e5 + 10, N = 110; bool v[M]; int sg[M], k[N], sum[N]; int main () { ios::sync_with_stdio(false); cin.tie(0); int K; while (cin >> K) { if (K == 0) { break; } for (int i = 1; i <= K; i ++) { cin >> k[i]; } memset(sg, 0, sizeof(sg)); memset(v, 0, sizeof(v)); for (int i = 1; i <= M - 10; i++) { for (int j = 1; j <= K; j ++) if (k[j] <= i) { v[sg[i - k[j]]] = 1; } for (int j = 0; j <= M - 10; j ++) if (!v[j]) { sg[i] = j; break; } for (int j = 1; j <= K; j ++) if (k[j] <= i) { v[sg[i - k[j]]] = 0; } } int T; cin >> T; for (int i = 1; i <= T; i++) { int n; cin >> n; sum[i] = 0; for (int j = 1; j <= n; j++) { int x; cin >> x; sum[i] ^= sg[x]; } } for (int i = 1; i <= T; i++) { if (sum[i] != 0) { cout << "W"; } else { cout << "L"; } } cout << "\n"; } return 0; }

3. 威佐夫博弈 (Wythoff's Game)

规则

  • 有两堆物品，数量分别为和
  • 两个玩家轮流操作，每次可以：
    • 从一堆中取任意多的物品
    • 从两堆中取同样多的物品
  • 最后取光物品的人获胜

必胜策略

  • 令，计算
  • 计算，其中（黄金分割比）
  • 若，则当前局面是必败态
  • 否则是必胜态

性质

  • 威佐夫博弈的必败态为，其中：

必败态满足：

完备覆盖性：每个正整数恰好出现在一个必败态中

这满足定律（1）必胜态的后续操作里必有一个必败态。

无重复性：任意两个必败态没有公共元素

这满足定律（2）除外的必败态的后续操作都是必胜态

而前面两条和威佐夫博弈的定义恰好满足定律（3）：

必败态和必胜态交替出现，物品不断变少，终态为必败态

证明

beatty 定理：

如果一对无理数和满足，那么这样两个数列 :

（其实就是和的并集啦）

就既无重复又无遗漏地包含了所有的正整数。

证明指路。

我们发现，将代入，

和代入，正好满足。

也就是：

  • 威佐夫博弈的必败态为，其中：

满足三定律。

例题：

P3024 [USACO11OPEN] Cow Checkers S - 洛谷 (luogu.com.cn)

代码：

板，令，当（）时为必败态。

#include<bits/stdc++.h> using namespace std; int main () { ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; int T; cin >> T; for (int i = 1; i <= T; i ++) { int x, y; cin >> x >> y; if (x > y) { swap(x, y); } double t = 1.0 * (y - x) * (1 + sqrt(5)) / 2; if (x == floor(t)) { cout << "Farmer John" << "\n"; } else { cout << "Bessie" << "\n"; } } return 0; }