博弈论学习笔记【未完】

编程入门行业动态更新时间:2024-10-27 00:24:09

博弈论学习笔记【<a href=https://www.elefans.com/category/jswz/34/1764943.html style= 未完】"/>

博弈论学习笔记【未完】

博弈论

文章目录

博弈论
- 0x00. 初始定义
- - 0x01. 公平游戏的定义
  - 0x02. 必胜必败状态的定义
  - 0x03. mex运算的定义
  - 0x04. SG定理 / SG函数
  - 0x05. SJ定理
- 0x10. Bash 游戏
- 0x20. Nim 游戏
- - 0x21. 普通 Nim
  - 0x22. 阶梯 Nim
- 0x30. SG 类问题 / 选取集合类问题
- - 0x31. 一堆石子的选取集合类问题
  - 0x32. 多堆石子的选取集合类问题
- 0x40. Anti-SG 类问题
- - 0x41. Anti-Nim 问题
- 0x50. 黄金比博弈 / 威佐夫博弈
- 0x60. 图 / 树上的博弈论问题
- - 0x61. 有向无环图上的单游戏博弈
  - 0x62. 有向无环图上的多游戏博弈
- 0x70. Every-SG 问题
- 0x80. Multi-SG 问题
- - 0x81. 分割类博弈
- 0x90. 斐波那契博弈
- 0xa0. 其他博弈论
- - 0xa1. DP 类博弈论
  - 0xa2. 其他类博弈论
- 0xb0. 总结
我太菜了！ \Huge{我太菜了！} 我太菜了！

参考过的文章：

Link 好文要顶

0x00. 初始定义

0x01. 公平游戏的定义

公平游戏的定义：

两个玩家交替行动。
其中不能进行移动的玩家就赢了/输了。
在游戏进行的时候，可以执行的操作和当前是哪一个玩家无关。

0x02. 必胜必败状态的定义

必胜状态的定义：如果这个状态对方无论怎么走都必败，就是一个对于你的必胜状态。

必败状态的定义；如果这个状态对方无论怎么走都必胜，就是一个对于你的必败状态。

0x03. mex运算的定义

mex ⁡ { a 1 , a 2 , a 3 , ⋯ , a k } \operatorname{mex}\{a_1,a_2,a_3,\cdots,a_k\} mex{a1,a2,a3,⋯,ak} 为在 a a a 数组中最小的没有出现过的自然数。自然数是指 ≥ 0 \ge 0 ≥0 的整数。

0x04. SG定理 / SG函数

如果一个状态 x x x 可以转移到 a 1 , a 2 , a 3 , ⋯ , a k a_1,a_2,a_3,\cdots,a_k a1,a2,a3,⋯,ak 这些状态，那这个状态的值就是 mex ⁡ { a 1 , a 2 , a 3 , ⋯ , a k } \operatorname{mex}\{a_1,a_2,a_3,\cdots,a_k\} mex{a1,a2,a3,⋯,ak}，其中终止状态的 SG 值为 0 0 0。

如果一个状态的 SG 值为 0 0 0 就是必败状态，否则就是必胜状态。

0x05. SJ定理

对于任意一个 Anti-SG 游戏，如果我们规定：当局面中所有的单一游戏的 SG 值为 0 0 0 时，游戏结束，则先手必胜当且仅当满足下列条件：

游戏的 SG 函数值不为 0 0 0 且游戏中某个单一游戏的 SG 函数值大于 1 1 1。
游戏的 SG 函数值为 0 0 0 且游戏中没有任意一个单一游戏的 SG 函数值大于 1 1 1。

0x10. Bash 游戏

人Win LK 和 6872 玩游戏。

有 1 1 1 堆石子，一共有 n n n 个石子，每一个人一次可以取 1 ∼ k 1\sim k 1∼k 个石子，问谁可以获胜。

~~这不是小学奥数题吗~~

进行分类讨论。

如果 n m o d ( k + 1 ) = 0 n\bmod (k+1) = 0 nmod(k+1)=0，那么先手拿 a a a 个，后手拿 k + 1 − a k + 1 - a k+1−a 个一定可以拿到最后一个。先手必败。
否则，先手可以先拿 n m o d ( k + 1 ) n\bmod (k+1) nmod(k+1) 个，然后后手变成先手，状态变成第一种情况，先手必胜。

bool check(int n, int k)
{ return n % (k + 1); }

0x20. Nim 游戏

0x21. 普通 Nim

Link

人win LK 和 6872 玩游戏。

nim 游戏的规则是这样的：地上有 n n n 堆石子（每堆石子数量小于 1 0 4 10^4 104 ），每人每次可从任意一堆石子里取出任意多枚石子扔掉，可以取完，不能不取。每次只能从一堆里取。最后没石子可取的人就输了。假如人Win LK 是先手，且告诉你这 n n n 堆石子的数量，他想知道是否存在先手必胜的策略。

结论：如果每一堆石子的值都异或起来，答案为 0 0 0，那么 6872 必胜，否则 LK 必胜。

证明：

如果轮到某一个人走，却没有办法走，对于他的对手就是必胜状态，那么这种情况所有的石子一定全部都是 0 0 0，也就是每一堆都没有石子，那么异或和也为 0 0 0。

否则，如果异或和不为 0 0 0，一定存在某一种方式拿走一些石子让异或和为 0 0 0；同理，如果异或和为 0 0 0，那么一定存在某一种方式拿走一些石子让异或和不为 0 0 0。（不会证明这个鬼玩意）

代码：

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

AC Link

0x22. 阶梯 Nim

人win LK 和 6872 玩游戏。

有一个 n n n 阶的台阶，每一个台阶都有一些石子，现在人Win LK 和 6872 轮流将石子从上一级台阶移动到下一级台阶，如果没有台阶上有石子就败，人Win LK 想知道他没有必胜策略。

容易发现，如果一个人将偶数级台阶移到了奇数级台阶，那么可以用同样的操作将奇数级台阶移动到偶数级台阶。所以说只要将奇数台阶上的所有石子的异或和异或起来即可。

代码：

#include <bits/stdc++.h>using namespace std;signed main()
{int n, xr = 0;cin >> n;for (int i = 1; i <= n; i ++){int x;cin >> x;if (i & 1)xr ^= x;}if (xr) cout << "Yes\n";else cout << "No\n";return 0;
}

0x30. SG 类问题 / 选取集合类问题

0x31. 一堆石子的选取集合类问题

请看 0xa0。

0x32. 多堆石子的选取集合类问题

人Win LK 和 6872 玩游戏。

有 n n n 堆石子，每一堆石子只要能拿就可以拿 a 1 , a 2 , a 3 , ⋯ , a k a_1,a_2,a_3,\cdots,a_k a1,a2,a3,⋯,ak 个石子，谁不能拿他的对手就赢了，人Win LK 想要知道他能不能赢。

实际上就是 0x04 SG 定理。使用 SG 定理可以通过这道题。

#include <bits/stdc++.h>using namespace std;const int N = 1e6 + 10;
int f[N], a[N];
int n, m;int sg(int x)
{if (f[x] != -1)return f[x];vector <int> arr;for (int i = 0; i < m; i ++)if (x >= a[i])arr.push_back(sg(x - a[i]));sort (arr.begin(), arr.end());arr.erase(unique(arr.begin(), arr.end()), arr.end());set <int> se;for (auto &u : arr)se.insert(u);for (int i = 0; ; i ++)if (!se.count(i))return f[x] = i;return -1;
}signed main()
{memset (f, -1, sizeof f);cin >> m;for (int i = 0; i < m; i ++)cin >> a[i];cin >> n;int xr = 0;for (int i = 0; i < n; i ++){int x;cin >> x;xr ^= sg(x);}if (xr)cout << "Yes\n";elsecout << "No\n";return 0;
}

0x40. Anti-SG 类问题

0x41. Anti-Nim 问题

Link

人Win LK 经常和他的好朋友 6872 玩一个非常有趣的游戏：桌子上有 n n n 堆石子，人Win LK 和他的好朋友 6872 轮流取石子，每个人取的时候，可以随意选择一堆石子，在这堆石子中取走任意多的石子，但不能一粒石子也不取，我们规定取到最后一粒石子的人算输。

人Win LK 相当固执，他坚持认为先取的人有很大的优势，所以他总是先取石子，而他的好朋友 6872 就聪明多了，他从来没有在游戏中犯过错误。人Win LK 一怒之前请你来做他的参谋。自然，你应该先写一个程序，预测一下谁将获得游戏的胜利。

结论：先手必胜需要满足所有堆的石子数都为 1 1 1 且异或和为 0 0 0（也就是有偶数堆）或者有一个或者以上堆的石子数 > 1 >1 >1 且石子堆的异或和不为 0 0 0。

代码：

#include <bits/stdc++.h>using namespace std;int a[55];signed main()
{int T;cin >> T;while (T --){int n;cin >> n;for (int i = 1; i <= n; i ++)cin >> a[i];if (n % 2 == 0){bool flag = true;for (int i = 1; i <= n; i ++)if (a[i] != 1){flag = false;break;}if (flag){cout << "John\n";continue ;}}bool flag = false;for (int i = 1; i <= n; i ++)if (a[i] > 1){flag = true;break;}if (!flag){cout << "Brother\n";continue ;}int xr = 0;for (int i = 1; i <= n; i ++)xr ^= a[i];if (xr)cout << "John\n";elsecout << "Brother\n";}
}

AC Link

0x50. 黄金比博弈 / 威佐夫博弈

0x60. 图 / 树上的博弈论问题

0x61. 有向无环图上的单游戏博弈

题意：给定一个有 N N N 个节点的有向无环图，图中有一个节点有棋子，人Win LK 和 6872 交替移动棋子。

玩家每一步可将这个棋子沿一条有向边移动到另一个点，无法移动者输掉游戏。

对于给定的图和棋子初始位置，人Win LK 和 6872 都会采取最优的行动，人Win LK 想要知道他是否有必胜策略。

实际上就是简单的图上 DP，直接暴力进行状态转移即可。

代码（你觉得这么简单的题还需要代码吗）

0x62. 有向无环图上的多游戏博弈

Link

题意：给定一个有 N N N 个节点的有向无环图，图中某些节点上有棋子，人Win LK 和 6872 交替移动棋子。

玩家每一步可将任意一颗棋子沿一条有向边移动到另一个点，无法移动者输掉游戏。

对于给定的图和棋子初始位置，人Win LK 和 6872 都会采取最优的行动，人Win LK 想要知道他是否有必胜策略。

有向无环图（DAG）上的多游戏博弈问题：终点的 sg 函数值为 0 0 0，其他节点的 sg 值为他可以到达的所有点的 sg 值的 mex 值。

然后就可以在图上进行遍历求解 sg 函数的值了。

#include <bits/stdc++.h>using namespace std;int n, m, k;
const int N = 2010;
vector <int> z[N];
int f[N];int sg(int u)
{if (~f[u])return f[u];vector <int> arr;for (auto &i : z[u])arr.push_back(sg(i));sort (arr.begin(), arr.end());arr.erase(unique(arr.begin(), arr.end()), arr.end());set <int> se;for (auto &u : arr)se.insert(u);for (int i = 0; ; i ++)if (!se.count(i))return f[u] = i;return 114514;
}int main()
{cin >> n >> m >> k;while (m --){int a, b;cin >> a >> b;z[a].push_back(b);}memset (f, -1, sizeof f);int xr = 0;for (int i = 0; i < k; i ++){int x;cin >> x;xr ^= sg(x);}if (xr)cout << "win\n";elsecout << "lose\n";return 0;
}

AC Record

0x70. Every-SG 问题

题意：人Win LK 先走，每个游戏由两堆石子组成，每次可以从较多的那一堆中取走较小那堆的数量的倍数个石子。问人Win LK 赢还是 6872 赢。

如果 x > y x>y x>y 就交换。

如果 ⌊ y x ⌋ = 1 \lfloor\frac{y}{x}\rfloor = 1 ⌊xy⌋=1，那么直接计算答案即可。

否则，只需要考虑 k = 1 k=1 k=1 的后续状态即可。

#include <bits/stdc++.h>using namespace std;int f[1010][1010], g[1010][1010];int sg(int x, int y)
{if (x > y)swap (x, y);if (~f[x][y])return f[x][y];if (x == 0 || y == 0)return f[x][y] = 0;int a = y % x, b = y / x;if (b == 1){f[x][y] = sg(a, x) ^ 1;g[x][y] = g[a][x] + 1;return f[x][y];}else{g[x][y] = sg(a, x) + g[a][x] + 1;return f[x][y] = 1;}
}signed main()
{memset (f, -1, sizeof f);int n;while (cin >> n){int mx = 0, a, b;while (n --){cin >> a >> b;sg(a, b);if (a > b)swap(a, b);mx = max(mx, g[a][b]);}if (mx & 1)cout << "MM\n";elsecout << "GG\n";}
}

0x80. Multi-SG 问题

0x81. 分割类博弈

人Win LK 和 6872 正在玩游戏。

人Win LK 先走，每一次拿走 n n n 堆石子中的一堆，假设这一堆石子中有 x x x 个，那么可以放入两堆石子，且放入满足石子的个数小于 x x x 个，不过可以为 0 0 0。如果 x = 0 x=0 x=0 那么不能分割。不能拿的人的对手就赢了，人Win LK 想要知道他有没有必胜策略。

容易发现， x x x 状态可以分裂成 ( a , b ) (a,b) (a,b) （ 0 ≤ a , b < x 0\le a,b < x 0≤a,b<x）。

然后引入 SG 定理： s g ( a , b ) = s g ( a ) xor ⁡ s g ( b ) sg(a,b) = sg(a) \operatorname{xor} sg(b) sg(a,b)=sg(a)xorsg(b)。然后只需要枚举 a a a 和 b b b 即可。

代码：

#pragma GCC optimize(3, "Ofast", "inline")
#include <bits/stdc++.h>using namespace std;const int N = 210;
int f[N], n;int sg(int x)
{if (~f[x])return f[x];set <int> se;for (int i = 0; i < x; i ++)for (int j = 0; j <= i; j ++)if (!se.count(sg(i) ^ sg(j)))se.insert(sg(i) ^ sg(j));for (int i = 0; ; i ++)if (!se.count(i))return f[x] = i;return 114514;
}signed main()
{memset (f, -1, sizeof f);cin >> n;int res = 0;for (int i = 1; i <= n; i ++){int x;cin >> x;res ^= sg(x);}if (res)cout << "Yes\n";elsecout << "No\n";return 0;
}