概述#

博弈论，可以定义为两人或多人面对一定的规则约束下，根据所掌握的信息，同时或先后，一次或多次地，从各自允许的行为中选择最优策略，通常要使自身收益最大化。

囚徒困境#

两名罪犯A, B分开囚禁在两个房间内，互相之间不能交流。

每名罪犯可以检举对方犯罪，也可以保持沉默。

• 若A检举B，且B沉默，则B被判20年。
• 若B检举A，且A沉默，则A被判20年。
• 若A，B都检举对方，同时被判8年。
• 若A，B都沉默，同时被判1年。

博弈：对于每个个体来讲都要是最优的。

P1288 取数游戏Ⅱ#

$\rm{Description}$#

取数游戏。给出一个环，每条边都有为负边权，所有边中至少有一个 $0$.

将一枚硬币放在环的一个节点上，两个玩家以这个放硬币的节点为起点开始游戏，轮流进行操作，操作方案如下：

1. 选择当前硬币连出的两条边中的一条，要求这条边的权值为正；
2. 将选取的这条边的权值，减少到任意一个，小于原本权值的非负整数；
3. 将硬币移动到选取边的另一侧。

如果轮到一个玩家，硬币的两条边权都是 $0$，那么输掉游戏，比如：

$\rm{Solution}$#

显然每次操作，把边权直接变为 $0$ 最优。

所以分别看起点的两端，如果它们的其中一个到第一个 $0$ 的距离为奇数，那么先手胜，反之后手胜。

巴什博奕#

$\rm{Description}$#

有 $n$ 个物品，A, B两人轮流从物品中拿走一部分，每次至少拿 $1$ 个，最多拿 $𝑚$ 个，拿走最后一个的人获胜。是否有必胜策略，若有，则求出策略。

$\rm{Solution}$#

可以想到，当物品的总量 $n=(m+1)r+s$ 时，A先拿走 $s$ 个物品，之后每次若B 取走 $k$ 个，则 A对应的取走 $m+1-k$ 个，这样A显然能够取得胜利。

若物品总量为 $n=(m+1)r$ ，此时B用同样的策略即可，B必胜。

$\rm{Code}$#

#include <iostream>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    if(n % (m + 1) == 0) {
        cout << "后手胜" << endl;
    } else {
        cout << "先手胜" << endl;
    }
    return 0;
}

威佐夫博弈#

$\rm{Description}$#

有两堆，若干个物品，两个人轮流从某一堆或从两堆中取同样多的物品，规定每次最少拿走一个，最多不限制，最后拿光的人获胜。

$\rm{Analysis}$#

用A表示先手玩家，B表示后手玩家，当前是A进行操作。为了判断 A 是否有必胜策略，可以这样分析：

• 用有序数对 $(a, b)$ 表示两堆物品的数量状态；
• $(0, 0)$ 是 $A$ 的必败策略，因为此时 $A$ 已输；
• 若局面能够移动到 $B$ 无必胜策略的局面，那么这个局面是 $A$ 的必胜态；
• 若局面无论怎么移动，都会变成 $B$ 的必胜太，那么这个局面是 $A$ 的必败态。

通过枚举，可以发现 $A$ 的必败态有：

用有序数对序列$(a_0, b_0),(a_1, b_1),(a_2, b_2)\ldots$表示上面的必败态，可以看出，满足：$a_0=b_0=0$ 且 $b_i=a_i+i$，$a_i$ 是之前没有出现过的最小自然数。

$\rm{Demonstrate}$#

前置命题： $a_{n+1}$ 是前 $n$ 组必败态中没有出现过的最小正整数。#

证明命题： $\forall n, b_n=a_n+n$.#

考虑归纳证明。若前 $k$ 个必败态分别为 $(a_1, a_1+1), (a_2, a_2+2), \cdots, (a_k, a_k+k)$，下证：第 $k+1$ 个必败态为 $(a_{k+1}, a_{k+1}+k+1)$.

从这个必败态出发，一共可能走向三类状态：从第一堆拿走，从第二堆拿走，或者两堆同时拿走，只需证明这三类都是必胜态。

**情况一：**从第一堆拿走一些。

因为任意一个比 $a_{k+1}$ 小的数都在之前的必胜态中出现过，第一堆变少之后，只需要把第二堆拿到第一堆对应的必败态。所以对于出现的新的状态，都可以直接指向必败态。

**情况二：**从第二堆拿走一些。

1. 拿完之后第二堆仍然大于第一堆。此时可以表示成 $(a_{k+1}, a_{k+1}+m), (m<k+1)$，那么两堆同时拿掉一些之后，变成 $(a_m, a_m+m)$.

   2. 拿完之后第二堆小于第一堆，设其拿成了 $(a_{k+1}, m)$，则 $m<a_{k+1}$ 一定属于之前的一个必败态，将第一堆拿到第二堆对应的必败态即可。

情况三：两堆同时拿走一些。

设拿完之后的状态是 $(m, m+k+1)$。因为 $m<a_{k+1}$，所以第一堆一定属于之前的一个必败态，将第二堆拿到第一堆对应的必败态即可。

所以现在已经得到了数列关系式 $b_n=a_n+n$.

$\rm{Attribute}$#

在这个问题中，我们称必败态为奇异局势，记为 $(a_k, b_k)$ 那么有如下性质：

1. 任何自然数都包含在一个且仅一个奇异局势中#

因为 $a_k$ 是之前没有出现过最小自然数，所以所有自然数都会被包含到奇异局势当中。

由于 $a_k>a_{k-1}$，所以 $b_k=a_k+k>a_{k-1}+k>a_{k-1}+k-1=b_{k-1}>a_{k-1}$。整理后，有 $b_k > b_{k-1}>a_{k-1}$，所以不存在自然数被两个奇异局势包含。

2. 任意操作都可以将奇异局势变为非奇异局势#

也就是说，必败态的后继一定都是必胜态。

对于奇异局势 $(a_k, b_k)$，如果只改变其中一个数，那么由性质$1$，不可能是另一个奇异局势；

如果同时改变两个数，那么这两个数的差不变，由于 $b_k=a_k+k$，对于一个差值，只可能对应一个奇异局势，所以变化后也不可能是另一个奇异局势。

3. 可以将非奇异局势变为奇异局势#

根据奇异局势满足 $b_k=a_k+k$，可以分类讨论进行证明。

具体地，对于任意的局势 $(a, b)$，

若 $a=b$，那么同时取走 $a$ 个物品即可变为 $(0, 0)$；

若 $a$ 是一个奇异局势中的 $a_k$，且 $b>b_k$，那么从 $b$ 堆中取出 $b-b_k$个物品，变为 $(a_k, b_k)$.

若 $a$ 是一个奇异局势中的 $a_k$，且 $b<b_k$，那么从两堆中同时拿走 $a-a_{b-a}$ 个物品。

若 $a$ 不属于任何一个奇异局势中，那么 $b$ 一定是一个奇异局势中的 $b_k=a_k+k$，此时有两种情况：

如果 $a>a_k$，从第一堆中拿走多余的 $a-a_k$.

如果 $a<a_k$，如果 $a=a_j (j<k)$，就从第二堆中拿走 $b-b_j$；如果 $a=b_j(j<k)$，就从第二堆里面拿走 $b-a_j$.

$\rm{Conclusion}$#

快速判断局势 $(a, b)$ 是否是奇异局势的方法。

Beatty定理#

设 $a, b$ 是正无理数，且 $\frac{1}{a}+\frac{1}{b}=1$，记 $P=\lfloor{na}\rfloor, Q=\lfloor{nb}\rfloor$，$n$ 为任意正整数。

那么 $P\cap Q=\emptyset$ 且 $P\cup Q=N^{*}$.

也就是说：取两个正无理数 $\frac{1}{\alpha}+\frac{1}{\beta}=1$，构造两个数列 $a_n=\lfloor\alpha n\rfloor$ 和 $b_n=\lfloor\beta n\rfloor$，那么两个数列单调递增，并且每个正整数在两个数列当中出现且仅出现一次。

推导#

发现奇异局势和 Beatty 定理的条件很像，考虑计算出 $\alpha$ 和 $\beta$.

两个数列 $a_n$ 和 $b_n$ 就是奇异局势中的 $(a_n, b_n)$.

$a_n+n=\lfloor{\alpha\cdot n}\rfloor+n=\lfloor{(\alpha+1)\cdot n}\rfloor=\lfloor{\beta\cdot n}\rfloor$.

所以 $\alpha+1=\beta$

所以 $\frac{1}{\alpha}+\frac{1}{\beta}=\frac{1}{\alpha}+\frac{1}{\alpha+1}=1$.

解得 $\alpha=\frac{\sqrt{5}+1}{2}$.

所以 $a_n=\lfloor\frac{\sqrt{5}+1}{2}n\rfloor$，$b_n=\lfloor(\frac{\sqrt{5}+1}{2}+1)n\rfloor=\lfloor\frac{3+\sqrt{5}}{2}n\rfloor=\lfloor(\frac{\sqrt{5}+1}{2})^2n\rfloor$.

所以根据 Beatty 定理，奇异局势的通项公式为：$a_n=\lfloor(\frac{\sqrt{5}+1}{2})n\rfloor$，$b_n=\lfloor(\frac{\sqrt{5}+1}{2})^2n\rfloor$.

而 $\frac{\sqrt{5}+1}{2}$ 是黄金比，所以威佐夫博弈的奇异局势与黄金比相关。

判断方法#

根据奇异局势的性质，对于需要判断的局势 $(a, b), (a<b)$，设 $k=b-a$，可以计算出 $a_k$ 和 $b_k$，直接和 $a,b$ 进行比较即可。

$\rm{Code}$#

#include <bits/stdc++.h>

using namespace std;
bool eq(double a, double b) {
	if(abs(a - b) < 1e-4) return true;
	else return false;
}
int main() {
	double a, b; cin >> a >> b;
	if(a > b) swap(a, b);
	double t = (1.0 + sqrt(5.0)) / 2.0;
	double k = b - a;
	if(eq(floor(k * t), a) && eq(floor(k * t * t), b)) {
		cout << 0 << endl;
	} else {
		cout << 1 << endl;
	}
	return 0;
}

必胜必败分析#

概念#

更明确的定义概念：

必胜点（N）#

先手必胜点。

必败点（P）#

先手必败点。

性质#

所有终结点都是必败点；

从必胜点出发，存在一种方法能够进入必败点；

从必败点出发，无论如何都只能进入必败点。

算法#

设计一种算法来分析，一个局面是先手必胜还是先手必败。

1. 将终结点标为必败点；
2. 将所有一步操作进入必败点的位置标为必胜点；
3. 如果从某一个点开始，一步操作后只能进入必胜点，那么标记为必败点；
4. 重复步骤2， 3.

记忆化搜索的过程，可以画出博弈树。

例子#

描述#

一个 $4$ 行 $3$ 列的矩阵，有一个小球放在左上角。两个人依次移动小球，每次只能：

• 向右移动一格；
• 向下移动一格；
• 向右下移动一格。

最后无路可走的人输。两人按最优策略，问谁必胜。

解析#

直接用 $4$ 行 $3$ 列的矩阵表示必胜必败情况。用*表示情况不确定，P表示必败，N表示必胜。

首先标记最终的点是必败点：

***
***
***
**P

之后推第四行。第四行的所有点，只能往右走，所以：

***
***
***
PNP

再看第三行。$(3, 3)$ 可以往下走到必败，所以是必胜点。$(3, 2)$ 可以往右下走到必败，所以是必胜点，$(3, 1)$ 同理，所以：

***
***
NNN
PNP

同样的，可以算出最后两行：

NNN
PNP
NNN
PNP

所以，先手必胜。

代码实现#

两个人从一堆 $n$ 个物品中轮流取物品，每次取 $1, 3, 4$ 个物品，最后没法取的人输。分析必胜必败。

bool win[1001], vis[1001];//win[i]表示剩余i个物品时的必胜必败情况
void init() {
    win[0]=false;
    vis[0]=true;
}
void dfs(int x){
    if(vis[x]){
        return;
    }
    if(x>=1){
        dfs(x-1);
    }
    if(x>=3){
        dfs(x-3);
    }
    if(x>=4){
        dfs(x-4);
    }
    win[x]=false;
    if(x>=1&&!win[x-1]){
        win[x]=true;
    }
    if(x>=3&&!win[x-3]){
        win[x]=true;
    }
    if(x>=4&&!win[x-4]){
        win[x]=true;
    }
    vis[x]=true;
    return;
}

SG函数#

组合博弈游戏#

组合博弈游戏是这样一种博弈游戏：

• 有两个游戏者
• 有一个有限的游戏状态集
• 游戏规则规定了在每一个状态可以到达的后继状态集。如果在任意状态，双方的走步集合是相同的，那么这个游戏是公平的，否则是不公平的。比如象棋是不公平的，因为每个玩家只能移动自己的棋子。
• 两个人轮流操作
• 一般情况下，当一方无法操作时，无法操作者输，游戏结束。

我是真找不到别的定义了……

对于任意一个公平的组合博弈游戏（ICG），我们将每个可能的局面当成图论当中的一个点。

在这个图中的连边规则是：把局面向这个局面经过操作后可能得到的所有局面连边，构成一个有向图。如果这个游戏对于任意的局面 $A$，都不能通过一些操作，回到这个局面 $A$，那么构成的图是一个有向无环图（DAG）。

SG函数#

定义一个 $mex$ 函数，表示对于一个集合，不属于该集合的最小非负整数。比如 $mex\{0, 1, 2, 4\}=3$.

还是在这个博弈游戏中：两个人从一堆 $n$ 个物品中轮流取物品，每次取 $1, 3, 4$ 个物品，最后没法取的人输。

我们对每个状态进行分级，终结态的级别是 $0$. 如果一个状态能够变为 $0$ ~ $n-1$ 级的状态，那么这个状态是 $n$ 级状态。

状态 $1$ 能够变成 $0$ 级状态，称它为 $1$ 级状态；

状态 $2$ 只能变成 $1$ 级，不能变成 $0$ 级，所以它的级别为 $0$；

状态 $3$ 可以变为 $0$ 级，级别为 $1$；

状态 $4$ 可以变为 $0,1$ 级，级别为 $2$；

状态 $5$ 可以变为 $0,1,2$ 级，级别为 $3$.

在博弈游戏当中，SG函数定义为：$\operatorname{sg}(x)=mex\{\operatorname{sg}(y)\mid y$ 是 $x$ 的后继$\}$，也就是上面所说的状态等级。

对于一个ICG来说，状态 $x$ 是必败态，当且仅当 $\operatorname{sg}(x)=0$.

例子#

两个人从一堆 $n$ 个物品中轮流取物品，每次取 $1, 3, 4$ 个物品，最后没法取的人输。

$\operatorname{sg}(0)=mex(\emptyset)$，

$\operatorname{sg}(1)=mex\{\operatorname{sg}(0)\}=mex\{0\}=1$，

$\operatorname{sg}(5)=mex\{\operatorname{sg}(4), \operatorname{sg}(2), \operatorname{sg}(1)\}=3$.

P1247 取火柴游戏#

$\rm{Description}$#

给定数列 $n_1, n_2, \cdots, n_k$，表示有 $k$ 堆物品，第 $i$ 堆物品的数量为 $n_i$。

两人轮流从中取物品，规则：每次可以从一堆中拿走任意正整数个物品。先拿走最后一根的人胜利。

对于给定的数列，判断先手是否必胜，若必胜，输出第一次应该在哪堆取多少物品。

$\rm{Solution}$#

必胜必败分析#

先手必胜，当且仅当 $n_1\oplus n_2\oplus\cdots\oplus n_k\neq 0$。

对于其他 nim游戏 ，假设状态表示为 $(a_1, a_2, \cdots,a_n)$，那么先手必胜，当且仅当 $\operatorname{sg}(a_1)\oplus \operatorname{sg}(a_2)\oplus\cdots\oplus \operatorname{sg}(a_n)$，证明BFS。

本题中 $\operatorname{sg}(i)=i$，所以有上面的结论。

证明#

设 $s=n_1\oplus n_2\oplus\cdots\oplus n_k$.

也就是证明：

1. 当 $s \neq 0$ 时，存在一种取法，使得 $s=0$.
2. 当 $s=0$ 时，无论怎么取物品，$s$ 都不等于 $0$.

命题一#

因为 $s\neq 0$，根据异或的定义，存在一堆物品 $i$，满足 $n_i\oplus s<n_i$ ，那么就从第 $i$ 堆取走 $n_i-(n_i\oplus s)$，剩下 $n_i\oplus s$ 个物品。

此时，$s_{\rm{new}}=n_1\oplus n_2\cdots\oplus n_k\oplus s=s\oplus s=0$.

所以命题一成立。

命题二#

反证法。若否，则 $s=0$ 时，存在一种取物品的方法使得 $s_{\rm{new}}=0$.

设取走第 $i$ 堆的若干物品，第 $i$ 堆剩余 $n_i'$ 个物品。

所以 $s_{\rm{new}}=n_1\oplus n_2\cdots\oplus n_i'\oplus\cdots\oplus n_k=0=s$.

把 $s$ 的定义式代入，得到 $n_i=n_i'$，产生矛盾。

所以命题二成立。

找方案的方法#

利用命题一。找到一堆 $i$，满足 $n_i\oplus s<n_i$，将这一堆拿走 $n_i-(n_i\oplus s)$ 个物品，使得新的异或和为 $0$，满足题意。

$\rm{Code}$#

#include <bits/stdc++.h>

using namespace std;
const int MAXN = 1000008;
int T, n;
int a[MAXN];
int main() {
    scanf("%d", &n);
    int res = 0;
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        res ^= a[i];
    }
    if(res == 0) {
        cout << "lose" << endl;
    } else {
    	for(int i = 1; i <= n; i++) {
    		if((res ^ a[i]) < a[i]) {
    			cout << a[i] - (res ^ a[i]) << " " << i << endl;
    			a[i] = res ^ a[i];
    			break;
    		}
    	}
    	for(int i = 1; i <= n; i++) {
    		cout << a[i] << " ";
    	}
    	cout << endl;
    }
    return 0;
}

P2148 [SDOI2009]E&D#

$\rm{Description}$#

有 $2n$ 堆石子，编号分别为 $1, 2, \cdots, 2n$。将第 $2k-1$ 和 $2k$ 堆 $(1\leq k\leq n)$，归为同一组。第 $i$ 堆石子的个数是正整数 $s_i$.

定义分割操作：

1. 任取一堆石子，不妨为第 $i$ 堆，将其全移走；
2. 从和第 $i$ 堆同一组的石子中，取出若干正整数个石子，放到第 $i$ 堆的位置上。操作后，两堆石子数都要大于 $0$。

给定状态，问先手是否有必胜策略。

$n\leq 2\times 10^4, 1\leq s_i\leq 2\times 10^9$.

$\rm{Solution}$#

定义#

$f(x)$ 为 $x$ 的二进制末尾首个 $0$ 的出现位置（标号从 $0$ 开始）。比如 $f(5)=(101)_2=1$.

$\operatorname{sg}(x, y)$ 为一组分别有 $x+1, y+1$ 个石子的 $\operatorname{sg}$ 值。

$S_z$ 表示满足 $x+y+1=z$ 的 $\operatorname{sg}(x, y)$ 构成的自然数集合。$s_0=\emptyset$.

引理#

1. 终止局面的 $\operatorname{sg}$ 值为 $0$，即 $\operatorname{sg}(0, 0)=0$.

2. $\operatorname{sg}(x, y)=mex($ 所有后继的 $\operatorname{sg}$ 值 $)=mex(S_x\cup s_y)$.

结论#

1. $S_z$ 等同于 $z$ 二进制下 $1$ 的位置集合。比如 $s_5=(101)_2={0, 2}$.
2. $\operatorname{sg}(x, y)=f(x\mid y)$. 比如 $sg(1, 4)=f(5)=1$.

证明#

考虑归纳证明。逐步放大 $z$，证明对于任意的 $z$，结论 $1$ 成立，且对于任意的 $x+y=z$，结论 $2$ 成立。

根据引理 $1$，结论 $2$ 在 $z=0$ 时正确。

假设已经证明结论 $2$ 在 $z-1$ 正确，考虑 $S_z$ 包含元素 $p$ 的条件。

由 $S_z$ 的定义，需要 $x+y=z-1$，由结论 $2$，需要 $f(x\mid y)=p$.

因此，$(x\mid y)$ 的二进制第 $p$ 位是 $0$，$0\sim p-1$ 位都是 $1$. 所以 $x+y$ 的 $0\sim p-1$ 位都是 $1$，第 $p$ 位是 $0$.

又因为 $x+y+1=z$，所以当包含元素 $p$ 时，无论如何，二进制下 $z$ 的第 $p$ 位总为 $1$.

所以，当且仅当 $z$ 的二进制第 $p$ 位为 $1$ 时，$S_z$ 包含元素 $p$，结论 $1$ 得证。

因为结论 $1$ 成立，所以 $\operatorname{sg}(x, y)=mex(S_x\cup S_y)=mex(S_{x\mid y})$.

又因为 $x\mid y\leq x+y=z$ 在已经证明的 $z$ 的范围内，根据 $S$ 和 $f$ 的定义，显然 $mex(S_{x\mid y})=f(x\mid y)$.

故结论 $1, 2$ 得证。

解法#

根据上述结论，$\operatorname{sg}(x, y)=f(x\mid y)$，可以快速地求出每组的 $sg$ 值。将所有组的 $\operatorname{sg}$ 值异或起来，即可判断是否必胜。

$\rm{Code}$#

#include<bits/stdc++.h>

using namespace std;
int T, n;
int lowzero(int x){
    for (int i = 0;; i++, x >>= 1) {
        if (!(x & 1)) return i;
    }
}
int main() {
	scanf("%d", &T);
	while(T--) {
        int ans = 0;
        scanf("%d", &n); n >>= 1;
        while(n--) {
            int x, y;
            scanf("%d%d", &x, &y);
            ans ^= lowzero((x - 1) | (y - 1));
        }
        if(ans) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}

参考资料#

威佐夫博弈：https://blog.csdn.net/wu_tongtong/article/details/79295069 ↗

关于异或：https://blog.csdn.net/hndu__lz/article/details/61925818 ↗

P2148：https://www.luogu.com.cn/blog/Sooke/solution-p2148 ↗