ToB企服应用市场:ToB评测及商务社交产业平台

标题: 博弈论基础 [打印本页]

作者: 张国伟 时间: 2024-8-29 09:59
标题: 博弈论基础
前置知识

\(\operatorname {mex}\)：没有出现过的最小天然数，如 \(\operatorname {mex} \{0,2,3\}=1\)。
\(\oplus\)：按位异或。

前言

博弈类问题大致分为，公平组合游戏、非公平组合游戏（绝大多数的棋类游戏）、反常游戏。
只需要关注公平组合游戏 \(\texttt{(ICG)}\)，反常游戏是公平组合游戏的变形，经济类博弈也不是博客所讨论的范围

两个玩家轮流行动且游戏方式一致。
两个玩家对状况完全相识。
游戏肯定会在有限步数内分出胜败。
游戏以玩家无法行动竣事。

博弈的双方都被以为是神之个体，因为所有玩家对状况完全相识，且充分为自己打算，绝对理性。
当局面确定，效果肯定注定，并且没有任何随机的身分。
游戏中的每一个状态，终极导致的效果也肯定注定，只有必胜态、必败态，两种状态。
这一类博弈问题的效果没有任何意外，一方可以通过积极去改变效果是不大概的，这一点是反直觉的。

常用对数器打表来找规律。
博弈论的标题就是 要干去干，去找规律，不要怕。

巴什博弈 \(\texttt{(Bash)}\)

\(n\) 个的石头，每次操作可以拿走 \([1,m]\) 个石头。拿到末了 \(1\) 个石头的人获胜（也就是不能拿石头的人输）。
这个问题特别简单，就是显然答案是如果 \(n\) 为 \(m+1\) 的倍数那么先手输，否则先手赢。
\(\texttt{sg}\) 函数

接下来引入 \(\texttt{sg}\) 函数。
\(\texttt{sg}\) 体现当前状态的胜败情况。
有如下公式 \(sg(A)=\operatorname {mex} (sg(B)|A\to B)\)。
式子中的 \(A\) 和 \(B\) 体现状态，\(A\to B\) 体现 \(A\) 状态可以到达 \(B\)状态。也就是说我们可以通过 \(A\) 能到达的状态的SG函数值推算出 \(A\) 的 \(SG\) 值。
如果 \(\texttt{sg}\) 值为 \(0\) 则体现先手输，否则先手赢。

数学归纳法证实：

终极状态 \(SG=0\)。

对于任意一个必胜态 \(SG\not=0\)，存在一个后继态 \(SG=0\)

对于任意一个必败态 \(SG=0\)，不存在一个后继态 \(SG=0\)。

\(\texttt{e.g.}\)：在巴什博奕中：当 \(m = 2\) 时，\(\texttt{sg[0]=0,sg[1]=1,sg[2], sg[3]=0,}\cdots\)。
\(\texttt{FAQ}\):

Q: 不就是判断一个输赢吗？为什么要用一个 \(\texttt {int}\)，我 \(\texttt{bool}\) 也可以啊。
A: 是的，确实可以只有 \(\texttt{bool}\)，用 \(\texttt{int}\) 另有用途，我们下面会讲。

P2197 【模板】\(\texttt{(Nim)}\) 游戏——\(\texttt{sg}\) 多个独立的子问题的归并

标题描述

甲，乙两个人玩 \(\texttt{nim}\) 取石子游戏。
\(\texttt{nim}\) 游戏的规则是这样的：地上有 \(n\) 堆石子（每堆石子数量小于 \(10^4\)），每人每次可从任意一堆石子里取出任意多枚石子扔掉，可以取完，不能不取。每次只能从一堆里取。末了没石子可取的人就输了。假如甲是先手，且告诉你这 \(n\) 堆石子的数量，他想知道是否存在先手必胜的策略。
公式引入

若局面X由若干个子游戏 \(X1,X2...Xn\) 构成，则
\(SG(x)=SG(X_1)\oplus SG(X_2) \oplus \cdots\oplus SG(X_n)\)
数学归纳法证实：

终极局面成立

\(\forall X\)，所有后继局面可以取到 \(G(X_1)\oplus SG(X_2) \oplus \cdots\oplus SG(X_n)-1\)，取不到\(SG(X_1)\oplus SG(X_2) \oplus \cdots \oplus SG(X_n)\)
同样看做 \(\texttt{Nim}\) 游戏
设 \(S \rightarrow S_1\)
\(S \oplus (S \oplus S_1) =S_1\)
设 \((S \oplus S_1)\) 最高位为 \(k\)，存在 \(A\) 使得 \(k\) 位为 \(1\)。
那么\(A \oplus (S \oplus S_1) < A\)，所以让 \(A\) 变成\(A \oplus (S \oplus S_1)\)就行了。

这就是 \(\texttt{SG}\) 定理( \(\texttt{Bouton}\) 定理)。
问题解答

显然对于每一个子问题，对于石头个数为 \(n\)， \(\texttt {sg(n)=n}\)。
所以 \(SG=\oplus_{i=1}^{n}a_i\)。判断 \(\oplus_{i=1}^{n}a_i 是否为零即可\)
代码

#include<bits/stdc++.h>
using namespace std;
int t, n, a;
signed main(){
scanf("%d", &t);
while (t--) {
scanf ("%d", &n); int ans = 0;
while (n--) scanf("%d", &a), ans ^= a;
if (ans == 0) puts("No"); else puts("Yes");
}
return 0;
}

复制代码

P4279 [SHOI2008] 小约翰的游戏

标题描述

甲，乙两个人玩取石子游戏。
游戏的规则是这样的：地上有 \(n\) 堆石子（每堆石子数量小于 \(5000\)），每人每次可从任意一堆石子里取出任意多枚石子扔掉，可以取完，不能不取。每次只能从一堆里取。末了没石子可取的人就赢了。假如甲是先手，且告诉你这 \(n\) 堆石子的数量，他想知道是否存在先手必胜的策略。
这一题唯一的区别是末了没石子可取的人就赢了。
标题剖析

首先，如果 \(\forall i\) 有 \(a_i=1\)，那么就是看 \(n\) 的奇偶性了。
其次，如果只有一个 \(a_i\not=1\)，那么先手必赢 [1]
末了，因为要的是“只有一个 \(a_i\not=1\)”，异或和不为 \(0\), 所以只要抓住异或和不为 \(0\) 即可获胜，那么就转化为 \(\texttt{(Nim)}\) 游戏了。
示例代码

#include<bits/stdc++.h>
using namespace std;
int main() {
int t, n, x, ans, sum;
scanf("%d", &t);
while (t--) {
cin >> n, ans = sum = 0;
for(int i = 1; i <= n; ++ i) scanf("%d", &x), ans ^= x, sum += x;
if(sum == n) puts(n & 1 ? "Brother" : "John");
else puts(ans ? "John" : "Brother");
}
return 0;
}

复制代码

例二：三堆石头拿取斐波那契数博弈

标题描述

有三堆石头，数量分别为 \(a,b,c(a,b,c\le 10^5)\)。
两个人轮流拿，每次可以选择此中一堆石头，拿取斐波那契数的石头
拿到末了一颗石子的人获胜，根据 \(a,b,c\) 返回谁赢。
直接分别计算 \(\texttt{sg}\) 值即可。因为 \(\texttt{sg}\) 值都只会从最多 \(25\) 个后继推出，所以 \(\forall i, \texttt{sg}\le30\)。时间复杂度为 \(O(nm)\)。此中 \(m\) 为 \([1,n]\) 中斐波那契数的个数。
例三：P2148 [SDOI2009] E&D

标题描述

桌子上有 \(2n\) 堆石子，编号为 \(1,2,3\cdots,2n\)。
此中 \(1,2\) 为一组；\(3, 4\) 为一组； \(5, 6\) 为一组 \(,\cdots, 2n-1,2n\) 为一组。
每组可以进行分割操作：

任取一堆石子，将其移走，然后分割同一组的另一堆石子

从中取出若干个石子放在被移走的位置，组成新的一堆

操作完成后，组内每堆的石子数必须保证大于 \(0\)

显然，被分割的一堆的石子数至少要为 \(2\)

两个人轮流进行分割操作，如果轮到某人进行操作时，所有堆的石子数均为 \(1\)，判此人输掉角逐。
返回先手能不能获胜。
标题剖析

首先 \(\texttt{sg(x,y)}\) 体现当前一组内石子数分别为 \(x,y\) 的胜败情况。
直接暴力算出 \(20\times20\) 的 \(\texttt{sg}\) 表。
找规律。
发现 \(sg(x, y)=f((x-1)|(y-1))\)。
此中 \(f(x)\) 体现 \(x\) 最低 \(0\) 的位置如 \(8=(1000)_2,f(8)=0;7=(0111)_2,f(7)=3\)。
具体证实见题解 P2148 【[SDOI2009]E&D】。
代码易得，略。
例四：CF87C Interesting Game

标题简述

每次可以把一堆石子分成若干堆，使得分裂的石子是公差为 \(1\) 的等差数列。不能分的人输。
标题分析

直接算 \(\texttt{sg}\) 值。详见代码。
代码

[code]#include using namespace std;const int N = 1e5 + 10;int n, sg[N], mex[N];int main() { scanf("%d", &n); int ans = -1, cnt = 1; for (int i = 3; i b;}int main() { cin >> n; while (n--) { cin >> k; for (int i = 1; i > x, aa += x; if (k & 1) cin >> x, m.push_back(x); for (int i = 1; i > x, ab += x; } sort (m.begin(), m.end(), cmp); for (int i = 0; i < m.size(); i++) { if (i % 2 == 0) aa += m; else ab += m; } cout l >> r; for (int i = 1; i > x; SG ^= sg(x); } cout >= 1, t++; // 最高位（因为要保证有一个数能被除） for (int i = 1; i > i) | // 前半部分是被除以的，所以左移； (x & ((1 > n; for (int i = 1; i > x; for (int j = 2; j * j

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4