博弈论基础学习笔记

博弈论挺有意思的，这里主要是基于自己的理解整理一下最基础的一点内容。

我尽可能做到在保证一定严谨性的同时也让文章更加易懂。

updated on 2022.4.2：修改了若干处笔误及格式问题
updated on 2022.5.8：修改了若干处笔误、格式问题，以及 SG 函数证明中表述不明或存在错误的地方

Zermelo's Theorem

首先是一个博弈论中最基础的定理，OI 中常见的博弈问题也都建立在这一定理的基础上。

策梅洛定理，一个游戏如果满足：

两名选手轮流操作进行游戏
有限游戏（Finite Game），游戏状态有限且操作集合有限
游戏信息对两名选手完全公开（Perfect Information）
无随机因素（eg. 骰子）

那么先手与后手其一必拥有必胜策略，或双方拥有必不败策略。

Bash Game

最基础的博弈问题，作为一个引入，其描述了这样一个问题：

有一堆总数为 $n$ 的物品，$2$ 名玩家轮流从中拿取物品。每次至少拿 $1$ 件，至多拿 $m$ 件，不能不拿，最终将物品拿完者获胜。

不难发现这一问题适用策梅洛定理，同时游戏不存在平局情况，故先手或后手必存在必胜策略。

我们先从简单的 $\texttt{case}$ 开始。

m=2

考虑 $m=2$ 的情况。

不难发现场上物品数为 $3$ 的倍数时，我们无论我们取多少物品 $k$，对方都能够通过取 $3-k$ 个物品使得场上剩余物品数仍为 $3$ 的倍数，这样，最后一个物品将被对手取走。如果场上物品数不为 $3$ 的倍数，我们可以将其取至 $3$ 的倍数，对手将会面临必败局面。于是：

$m=2$ 时，先手必败当且仅当 $n$ 是 $3$ 的倍数。

Generalization

这一结论是能够推广的，考虑一般化的 $m$，当场上物品数为 $m+1$ 的倍数时，后手也能够通过取 $m+1-k$ 个物品将场上物品数控制为 $m+1$ 的倍数，类似的讨论方式，我们可以给出巴什博弈一般化的结论：

先手必败当且仅当 $n$ 是 $m+1$ 的倍数。

Nim Game

接下来的问题将逐渐变得复杂。

nim 游戏是非常经典的公平组合游戏。

首先给出公平组合游戏（ICG，Impartial Combinatorial Games）的定义：

两名选手进行游戏
两名选手轮流操作（move），每次操作在有限的合法操作集合中选择一个
对于游戏中可能出现的一种局面（position），其合法操作集合只取决于这个局面本身，不取决于当前由谁进行操作、以前进行的操作以及任何随机因素
游戏终止当且仅当当前局面的合法操作集合为空，这样的局面称作终止局面（terminate position），判定当前进行操作的选手为负

与公平游戏相反的游戏是 Partisan Game，在这种情况下，我们需要考虑当前由谁进行操作。

同时，这里我们给出对局面进一步的分类：

P-pos，Previous Position，先手必败
N-pos，Next Position，先手必胜

一般化的定义，同时也是判定方式：

终止局面是 P-pos
能够转移到 P-pos 的局面是 N-pos
只能够转移到 N-pos 的局面是 P-pos

于是，这里有了解决博弈问题最朴素的想法，我们可以考虑博弈的所有状态，然后 dp 进行转移。

我们以 nim 游戏作为第一个例子：

Luogu P2197 nim 游戏

地上有 $n$ 堆石子，每人每次可从任意一堆石子里取出任意多枚石子扔掉，可以取完，不能不取。每次只能从一堆里取。最后没石子可取的人就输了。假如甲是先手，且告诉你这 $n$ 堆石子的数量，问是否存在先手必胜的策略。

我们设 $n$ 堆石子的个数分别为 $a_{1\dots n}$，如果现在我们想要考虑所有可能产生的状态，不难发现状态数为 $\prod_{i=1}^n (a_i+1)$，一看就非常扯淡。

然而 nim 游戏有一个非常神奇的结论：一个局面为 P-pos 当且仅当 $\bigoplus_{i=1}^na_i=0$（这个和式也被称作 nim 和）。

下面给出简要证明：

首先，一个显而易见的事实是，终止状态是 P-pos，同时满足 $a_i$ 异或和为 $0$。
接下来考虑证明异或和为 $0$ 的局面移动一步后异或和必然不为 $0$，异或和不为 $0$ 的局面必然存在一种移动方式使得移动后异或和为 $0$。
一次移动一定会改变一堆的石子数，不难发现不可能保持异或和为 $0$。
对于异或和不为 $0$ 的局面，设异或和为 $k$，设 $k$ 为 $1$ 的最高二进制位为 $p$，考虑任取 $a_j$ 使得 $a_j$ 的第 $p$ 个二进制位为 $1$，接下来使 $a_j$ 变为 $a_j\oplus k$，显然 $a_j>a_j\oplus k$，所以这一步必然合法。
$\rm Q.E.D.$

nim 游戏的目的是让自己取走最后的石子，这样的游戏方式称作 normal play，如果对其进行修改，改为取走最后石子的人为负，这样的游戏方式就被称为 misère play，见Anti-Nim。

Nim Game 的变形

K-Nim

$n$ 堆石子，每次可以从不超过 $k$ 堆石子中取任意数量的石子。

神奇结论：一个局面为 P-pos 当且仅当 $\forall x\ \sum[a_i的第x个二进制位为1]\equiv0\pmod{k+1}$。

证明：

考虑类似的思路，终止状态符合条件且为 P-pos
对于符合条件的局面，对于任一二进制位，移动一步后会有不超过 $k$ 个二进制位发生改变，且不可能所有二进制位都不发生改变，故移动一步后的局面必不符合条件
对于不符合条件的局面，考虑调整所有不符合条件的二进制位即可
$\rm Q.E.D.$

Anti-Nim

Luogu P4279 [SHOI2008]小约翰的游戏

与 nim 游戏条件相同，没有石子取的人获胜。

神奇结论：一个局面为 N-pos 当且仅当：

每一堆石子个数为 $1$，且 $\bigoplus a_i=0$
至少一堆石子个数 $>1$，且 $\bigoplus a_i\ne 0$

证明需要考虑的 $\texttt{case}$ 较多。

$\texttt{case 1}$ 每一堆石子个数为 $1$
- $\texttt{case 1.1}\ \bigoplus a_i=0$
  
  等价于堆数为偶数，此时每个人都只能直接取走一堆石子，显然最后一堆棋子被后手取走，故先手必胜。
- $\texttt{case 1.2}\ \bigoplus a_i\ne0$
  
  等价于堆数为奇数，一步操作后局面必为 $\texttt{case 1.1}$，故先手必败。
$\texttt{case 2}$ 有且仅有一堆石子个数 $>1$，必然有 $\bigoplus a_i\ne0$
- $\texttt{case 2.1}$ 堆数为偶数
  
  将石子个数 $>1$ 的堆取光，后手局面为 $\texttt{case 1.2}$，故先手必胜。
- $\texttt{case 2.2}$ 堆数为奇数
  
  将石子个数 $>1$ 的堆取到只剩 $1$ 个石子，后手局面仍为 $\texttt{case 1.2}$，故先手必胜。
综上，$\texttt{case 2}$ 先手必胜。
$\texttt{case 3}$ 超过一堆石子个数 $>1$
- $\texttt{case 3.1}\ \bigoplus a_i=0$
  
  只能够转移到这样两个状态之一：
  - 超过一堆石子个数 $>1$，$\bigoplus a_i\ne0$（下文 $\texttt{case 3.2}$）
  - 有且仅有一堆石子个数 $>1$，$\bigoplus a_i\ne0$（$\texttt{case 2}$，此时先手必败）
- $\texttt{case 3.2}\ \bigoplus a_i\ne0$
  
  类比 nim 游戏的证明过程，存在移动方式使得转移到 $\texttt{case 3.1}$。
综上，不难发现，$\texttt{case 3.1}$ 会在一定次数的转移后变为 P-pos，但 $\texttt{case 3.2}$ 一定是安全的，故 $\texttt{case 3.2}$ 先手必胜。
$\rm Q.E.D.$

存在比这精简的多的证明，但是这一证明理解起来应该较为容易。

Staircase Nim

阶梯 nim，经典的 nim 变形：

$n$ 堆石子放在 $n$ 阶台阶上，台阶编号为 $1\sim n$，地面编号为 $0$，两人轮流操作，每次可以将 $k\in[1,n]$ 台阶上的任意个石子挪到 $k-1$ 阶台阶 / 地面上，所有石子被挪到地上时游戏结束，最后进行操作的人获胜。

阶梯 nim 可以转换为普通的 nim 游戏。

具体的，我们只考虑编号为奇数的台阶，在这上面进行 nim 游戏，如果对手也移动奇数台阶上的石子，我们继续进行 nim 游戏，如果对手移动偶数台阶上的石子，我们就再把这些石子往下挪一阶。

于是，阶梯 nim 可以视作只有奇数台阶的 nim 游戏。

阶梯 nim 中，一个局面为 P-pos 当且仅当 $\bigoplus_{i\in odd}a_i=0$。

Wythoff's game

Luogu P2252 [SHOI2002]取石子游戏|【模板】威佐夫博弈

两人轮流取两堆筹码，取法有两种：取走一堆中任意个筹码，或从两堆中取走相同数目的筹码。取完所有筹码的一方获胜。

游戏中的状态可以用一个数对 $(n,m)$ 表示，不妨设 $n\le m$。

终止局面为 $(0,0)$，这是第一个 P-pos，我们考虑递推得到剩下的 P-pos，第 $k$ 个 P-pos 我们记作 $(n_k,m_k)$。

所有一步能够到达 $(0,0)$ 的状态都为 N-pos，即 $\forall x\in\mathbb{Z^+}$，$(0,x),(x,0),(x,x)$ 均为 N-pos：

在坐标系中作标记的点为 P-pos，被射线经过的点为 N-pos，下面均会使用这样的表示方式，每找到一个 P-pos，我们都以其为端点类似上图构造三条射线。

不难发现下一个 P-pos 为 $(1,2)$，当然也有与之对称的 $(2,1)$，我们不关心这一对称的局面：

重复类似的过程，下一个 P-pos 为 $(3,5)$：

结合图像，我们可以发现 P-pos 的两个性质：

除 $(0,0)$ 外，$n_k$ 为 $k$ 以前所有 P-pos 中未出现过的最小正整数。

进一步的，每个正整数都会在所有 P-pos 中出现恰好一次。

（观察图像中的竖线）
$m_k=n_k+k$（观察图像中的斜线）

接下来引入贝亚蒂定理

贝亚蒂定理，或贝亚蒂列（Beatty Sequence）指出：

若 $p,q\in\mathbb{R^+},p,q\notin\mathbb{Q}\ \ \mathrm{s.t.}\ \ \frac1p+\frac1q=1$，定义贝亚蒂列 $P=\{\lfloor kp\rfloor|k\in\mathbb{Z^+}\},Q=\{\lfloor kq\rfloor|k\in\mathbb{Z^+}\}$，有 $P\cap Q=\varnothing,P\cup Q=\mathbb{Z^+}$。

自然语言描述：若两个正无理数的倒数之和是1，则任何正整数都可刚好以一种形式表示为不大于其中一个无理数的正整数倍的最大整数。

$n_k$ 与 $m_k$ 满足贝亚蒂列的性质，于是我们猜测可以找到 $n_k$ 与 $m_k$ 对应的两个无理数，设 $n_k=\lfloor kp\rfloor,m_k=\lfloor kq\rfloor,\frac1p+\frac1q=1,p,q\in\mathbb{Z^+},p,q\notin\mathbb{Q},k\in\mathbb{Z^+}$。

我们有：
$$
\begin{aligned}
\lfloor kp\rfloor &= \lfloor kq\rfloor + k \\
\lfloor kp\rfloor &= \lfloor k(q+1)\rfloor
\end{aligned}
$$
这玩意带着下取整符号，看起来并不好处理，但考虑 $\forall t\in\mathbb{Z^+}$，我们令 $k=10^t$，由此可以知道 $p$ 与 $(q+1)$ 的整数部分与小数点后 $t$ 位均相同，进一步便有 $p=q+1$。

代入有：
$$
\begin{aligned}
\frac1{q+1}+\frac1{q}&=1\\
2q+1&=q^2+q\\
q^2-q-1&=0
\end{aligned}
$$
$q>0$，故 $q=\frac{1+\sqrt5}{2}$，即 $q=\varphi$（黄金分割比，$1.618\dots$），$p=\varphi+1=\varphi^2$。

综上，如果用 $(n_k,m_k),n_k\le m_k$ 表示威佐夫博弈中的 P-pos，$k\in\mathbb{N}$，我们有：
$$
\begin{aligned}
n_k&=\lfloor k\varphi\rfloor\\
m_k&=\lfloor k\varphi^2\rfloor=n_k+k\\
\end{aligned}
$$

Sprague-Grundy Function

任何一个 ICG 都可以被抽象为一个关于状态（局面）的有向图，一枚棋子被放在初始状态上，双方轮流挪动棋子，棋子到达终止局面时，游戏结束，如果存在环的话则游戏永远不会结束，故而我们一般考虑 DAG 上的情形。

我们希望在 DAG 上以一种更加一般化的方式来分析 ICG。

我们仍然从 nim 游戏开始。

nim 游戏中的一个状态可以视作是多个子状态的组合，每个子状态仅包含一堆石子。

显然，每个子状态都非常容易分析，除石子数为 $0$ 的情况，其余时候都是先手必胜，但我们无法将这些状态合并起来，就算每一堆石子都是先手必胜的，我们也无法判断整体是否先手必胜。

状态的阶数

从上面的分析中我们已经发现胜态与胜态之间是不能一概而论的，我们引入状态的阶数用于解决这一问题。

我们继续考虑只包含一堆石子的子局面：

石子个数为 $0$，（先手）必败，定义其阶数为 $0$。
石子个数为 $1$，只能转移到阶数为 $0$ 的状态，必胜，定义其阶数为 $1$。
石子个数为 $2$，能够转移到阶数为 $0$ 或 $1$ 的状态，通常我们会将这一状态转移至必败态，但如果整体需要，我们也可以将其转移至必胜态，这就是其与 $1$ 阶状态的区别，定义其阶数为 $2$。
$\dots$

简单分析不难发现：

对于一个状态而言，如果其阶数为 $0$，则其为必败态，否则为必胜态。
一个阶数为 $k$ 的状态可以任意转移至阶数低于 $k$ 的状态。

这也意味着一个状态阶数为 $k$ 的充要条件是其能够任意转移至阶数低于 $k$ 的状态。

$SG$ 函数就是用来表示状态的阶数的函数，引入作用于集合的运算 $\mathrm{mex}$（minimal excludant）表示集合中未出现过的最小非负整数。

根据上述分析，我们同时能够初步得到 $SG$ 函数的定义，同时也是计算公式：
$$
SG(x)=\mathrm{mex}\{SG(y)|x\to y\}
$$
似乎这样的定义存在漏洞，因为某些状态可能能够转移至阶数更高的状态，但实际上，后手能够将阶数再降回来，这样的操作相当于是无效的。

状态的合并

我们初步来试着合并两个状态，用一个数对 $(a,b)$ 来表示两个子状态的阶数分别为 $a,b$：

$(0,1)$，必胜，只能转移至 $(0,0)$，阶数为 $1$。
$(0,2)$，必胜，能够转移至 $(0,0),(0,1)$，阶数为 $2$。
$(1,1)$，必败，只能转移至 $(0,1)$，阶数为 $0$。
$(1,2)$，必胜，能够转移至阶数为 $0,1,2$ 的状态，阶数为 $3$。
$(2,2)$，必败，能够转移至阶数为 $2,3$ 的状态，阶数为 $0$。
$\dots$

比较容易发现的是，合并两个状态时，两个状态阶数不同时必胜，否则必败。

证明较为简单，如果两个状态阶数相同，我们的操作只能改变其中一个状态的阶数，后手便可以对另一状态模仿操作，使两个状态阶数再次相同然后丢给我们，最终我们的局面会是 $(0,0)$。

然而我们还无法确定合并后状态的阶数。

我们知道 nim 游戏中的状态可以用异或来进行合并，那么，这一结论是否也能够适用于 $SG$ 函数，我们不妨先假设 $SG$ 函数的合并方式就是异或。

验证上面的几组情况，我们发现这个结论似乎的确是正确的。

如果有了这个结论，我们就可以轻松地对状态进行拆分与合并了。

Proof

接下来，我们来证明，$SG(x+y)=SG(x)\oplus SG(y)$，$+$ 为状态的组合。

考虑数学归纳法。

根据定义，$SG(x+y)=\mathrm{mex}\{SG(z)|(x+y)\to z\}$。

将 $z$ 展开，$SG(x+y)=\mathrm{mex}(\{SG(x)\oplus SG(a)|y\to a\}\cup\{SG(b)\oplus SG(y)|x\to b\})$。

我们要证明的是 $SG(x)\oplus SG(y)$ 不属于两个集合中的任何一个，而任意比其小的非负整数属于两个集合中的其中一个。

前者显然，由于 $y\to a,x\to b$，$SG(a)\ne SG(y),SG(b)\ne SG(x)$，$SG(x)\oplus SG(y)$ 就不可能属于两个集合中的任何一个。

只需证明后者成立。

$\forall t<SG(x)\oplus SG(y)$，$t$ 为非负整数，记 $s=t\oplus SG(x)\oplus SG(y)$。

$s$ 存在一个最高为 $1$ 的二进制位 $k$，$t,SG(x),SG(y)$ 三者中必然存在一者 $r$ 满足第 $k$ 个二进制位也为 $1$，此时有$r\oplus s<s$，同时我们知道 $r\ne t$，因为 $t<SG(x)\oplus SG(y)=t\oplus s$。

$x,y$ 等价，那么不妨设 $r=SG(x)$，$s\oplus SG(x)=t\oplus SG(y)<SG(x)$，这也就意味着我们可以构造 $c$ 使得 $x\to c$ 同时 $c=t\oplus SG(y)$.

考虑集合 $\{SG(b)\oplus SG(y)|x\to b\}$，令 $b=c$，则 $t\in \{SG(b)\oplus SG(y)|x\to b\}$。

综上，$\rm Q.E.D.$

Summary

ICG 中，我们定义 $SG$ 函数：

$SG(x)=\mathrm{mex}\{y|x\to y\}$
一个状态若能拆分为多个子状态，则其 $SG$ 函数值为其所有子状态 $SG$ 函数值的异或和。
一个状态为必败态当且仅当其 $SG$ 函数值为 $0$。

Anti-SG

如果将终止状态定义为必胜态，也就是无法操作的人获胜，我们有 $SJ$ 定理，对于一个状态，这个状态为必胜态当且仅当以下两个条件同时成立或同时不成立：

$SG(x)=0$
$SG(y)\le1$，$y$ 是 $x$ 的子状态

证明类比 Anti-Nim，我们对 $SG$ 函数的操作实际上十分类似 nim 游戏。

本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。

Catalog