很久之前就想开博弈论这个坑了，因为打比赛经常遇到博弈问题结论题，只能靠感觉来做，没有系统的学习过博弈论。

前一周数学老师在一节数学课下课前提了一个好玩的游戏，顿时风靡全班。

注：本篇文章动笔于 2020.12.16

这个游戏是这样的：现在有 $30$ 个数要报，两个人轮流报数，每次最多报 $2$ 个数，最少报 $1$ 个数，先报到 $30$ 的人赢。

数学老师找了几个人来玩 ~~(因为她认为我破坏游戏平衡就把我ban掉了)~~，每次都是她后手，而她每次都赢，于是许多同学开始试怎样报数必赢，许多同学发现了后手的必赢策略，只要对方报奇数则他报偶数，否则报奇数。那么为什么这个策略是必胜的呢？数学老师估计是忘了或者根本没打算讲，于是这个坑由我来填了！

考虑上面那个必胜策略的证明其实很简单，因为后手每次都会取到 $3$ 的倍数，而要取的数正是 $3$ 的倍数，所以后手一定会取到 $30$。

限于笔者能力，本文可能会有许多不严谨甚至错误之处，欢迎指出！

Part1 从经典取石子游戏开始

现在让我们了解几个定义：

先手和后手

对于游戏中的面临的一个状态称作局面，在一个局面下，先进行行动的称作先手，后行动的为后手。

必胜和必败

对于博弈中一个局面（也可以说是状态）下：

若先手无论采取什么行动都会输掉游戏，则为必败点，后文也会称其为 必败局面；

双方都操作最优的情况下先手必胜的局面为必胜点，后文也会称其为 必胜局面。

一般情况下讨论的博弈问题为双方都足够聪明（也就是每一步都是最优操作）。

公平组合游戏 (Impartial Combinatorial Games, 简称ICG)

终止的局面为必败点。
一个局面可以执行的合法操作和轮到哪一名玩家无关。
两名玩家交替行动。

满足这三个条件的游戏成为公平组合游戏。

巴什博弈

那么现在，让我们来考虑前言所提到的问题的一般情况：

首先，给这个有趣的游戏建立一个模型，也就是把这个问题用数学语言描述出来：

现在有 $n$ 个石子要取，两个人轮流取石子，每次最多取 $m$ 个石子，最少取 $1$ 个石子，取走第 $n$ 个石子的人赢得游戏。其中满足 $n,m > 0$。考虑两个人都足够聪明的情况下判断先手还是后手必胜，并解释必胜策略。

我们称这个问题为巴什博弈 (Bash Game)。

当 $n\leq m$ 的时候先手必胜，因为先手可以第一次就把 $n$ 个石子全取完。

那么当 $n>m$ 时呢？

假设 $(m+1) \mid n$，那么先手取 $x$ 个时，后手取 $(m+1-x)$ 个，这样可以保证后手每次都是取到 $(m+1)$ 的倍数，最终取到 $n$ （因为 $n$ 是 $(m+1)$ 的倍数），所以 $(m+1) \mid n$ 时先手必败。

否则的话，先手先取 $n\bmod (m+1)$ 个石子，这样就相当于把 $n$ 减去了 $n\bmod (m+1)$，使得 $n$ 是 $(m+1)$ 的倍数，同时把先手扔给对方，后面的策略就和上面的后手必胜策略一样了，所以 $(m+1)\nmid n$ 时先手必胜。

题目：HDU 1846

Nim 游戏

给定 $n$ 堆物品，第 $i$ 堆物品有 $A_i$ 个。两名玩家轮流行动，每次可以任选一堆，取走任意多个物品，可以一堆取光，但不能不取。取走最后一件物品则获胜。两人都采取最优策略，问先手能否获胜。

结论：对于 Nim 游戏的一个局面 $(A_1,A_2,\ldots,A_n)$ 来说，先手必败当且仅当 $A_1 \oplus A_2 \oplus \ldots \oplus A_n=0$。

注：其中 $\oplus$ 是异或即 $\text{xor}$，后文均以此记号表示异或。

证明：

$(0,0,\ldots,0)$ 中 $A_1 \oplus A_2 \oplus \ldots \oplus A_n=0$ 为必败局面。

对于 $(A_1,A_2,\ldots,A_n)$ 若 $A_1 \oplus A_2 \oplus \ldots \oplus A_n = x \neq 0$，则可以选择 $x$ 的最高二进制位 $k$，则一定存在一个 $A_i$，它的第 $k$ 位是 $1$，则满足 $A_i \oplus x< A_i$，选取 $A_i$ 使其变成 $A_i\oplus x$ 将这个局面即可转换成 $A_1 \oplus A_2 \oplus \ldots \oplus A_n = 0$。

对于 $(A_1,A_2,\ldots,A_n)$ 若 $A_1 \oplus A_2 \oplus \ldots \oplus A_n = 0$，不管怎么取一定只能到达 $A_1 \oplus A_2 \oplus \ldots \oplus A_n \neq 0$ 的局面，可以选择反证法证明，若选取了 $A_i$ 使其变成 ${A_i}’$，由于 $A_1 \oplus A_2 \oplus \ldots \oplus A_i\oplus \ldots \oplus A_n = 0$ , $A_1 \oplus A_2 \oplus \ldots \oplus {A_i}’\oplus \ldots \oplus A_n = 0$ ，两式相异或得 $A_i\oplus {A_i}’=0,A_i={A_i}’$，与不能不取的规则相矛盾。

再由数学归纳法可知结论的正确性。

证毕。

题目：洛谷P2197

Part2 博弈论的其他知识点

有向图游戏

有一个 DAG，最初有一枚棋子在起点上，可以让棋子向任意一个连向的点走一步。两名玩家交替操作，不能走的玩家失败。

注意到任意一个公平组合游戏都能转换成一个有向图游戏，把局面看成点，一个操作看成当前局面到下一个局面连的有向边即可。

Mex 运算

对于一个仅包含非负整数的可空集合 $S$，定义 $mex(S)$ 为未在 $S$ 中出现且最小的非负整数，也就是：

$\text{mex}(S)=\min\{x|x\in \mathbb{N}, x\not\in S\}$

SG 函数

在一个DAG上，对于每个节点 $x$，假设它能到达的节点为 $S$，则：

$SG(x)=\text{mex}(\{SG(k)|k\in S\})$

特别地，当 $S$ 为空时 $SG(x)=0$。

对于一个DAG $G$，它的 SG 函数定义为它起点的 SG 函数值。

显然地，SG函数有以下性质：

对于任意的局面，如果它的 SG 值为 0，那么它的任何一个后继局面的 SG 值不为 0；
对于任意的局面，如果它的 SG 值不为 0，那么它一定有一个后继局面的 SG 值为 0。

有向图游戏胜负判断

一个有向图游戏 $G$ 的一个局面 $x$ 为必胜局面当且仅当 $SG(x)\neq 0$。

若 $x$ 没有出边则 $SG(x)=0$，必败局面。
若 $x$ 有出边且 $SG(x)\neq 0$，则一定存在一个后继节点 $y$ 其中 $SG(y)=0$ ，走到这个节点即可，必胜局面。
若 $x$ 有出边且 $SG(x)=0$，则无论走到哪个后继节点 $y$，都会有 $SG(y)\neq 0$，由 2. 可知走完这一步为必胜局面，也就是无论怎么走都会使得对方走到必胜局面，则这个局面是必败局面。

证毕。

有环有向图游戏

名字是我自己乱起的，其定义如下：

有一个有向图，最初有一枚棋子在起点上，可以让棋子向任意一个连向的点走一步。两名玩家交替操作，不能走的玩家失败。假定每个人都采取最优操作（每个人的最优操作为能赢则赢，否则争取平局），求是先手必胜、后手必胜还是平局。

由于出现了环，可能出现平局的局面。

对于一个状态（棋子在哪个点），我们多定义一个平局点，代表从这个位置开始走，不必胜，但可以选择走向平局局面。

首先，对于有向无环图，根据上文”有向图游戏胜负判断”（当然也可以使用数学归纳法）可得：

出度为 $0$ 的点为必败点；
只能到达必胜点的状态为必败点；
可以到达必败点的状态为必胜点。

假如出现了环，会出现点不满足这上面三个条件的任意一个。

这些点就是平局点，它们每个点都满足“不能到达必胜点，可以到达非必败点（即平局点）”。

反向建图跑拓扑排序即可。

例题

多个有向图游戏的和及SG 定理

对于多个有向图游戏的集合 $G=\{G_1,G_2,\ldots,G_n\}$，每次可以任选一个有向图 $G_i$，在 $G_i$ 上走一步，不能走的人失败。

有向图游戏的和 $G$ 的 SG 函数为 $SG(G_1)\oplus SG(G_2) \oplus \ldots\oplus SG(G_n)$。

证明：

对于每个 $k=SG(G_i)$ 可以看成可以将当前局面的 $SG$ 变成 $[0,k)$ 中的任意一个数。

即使有向图游戏会能让 $k$ 变成 $j,j>k$ 也是不妨碍的，因为最优操作是让 $k$ 变成 $0$ ，所以必胜方直接忽略变大的操作即可；即使必败方的 $0$ 转化成了 $j,j>0$，必胜方依然能把 $j$ 变成 $0$，必败方不能无限制变大，必胜方依然是必胜的。

这一定理被称为 SG 定理，即为”游戏和的SG函数等于各个游戏SG函数的Nim和”。

Anti-SG 游戏及SJ 定理

给定 $n$ 堆物品，第 $i$ 堆物品有 $A_i$ 个。两名玩家轮流行动，每次可以任选一堆，取走任意多个物品，可以一堆取光，但不能不取。取走最后一件物品则败北。两人都采取最优策略，问先手能否获胜。

和 Nim 游戏不同的是，终止情况 $(0,0,\ldots,0)$ 是必胜局面，而不是 Nim 游戏中的必败局面。

证明：

下文称物品数大于 $1$ 的堆为“大堆”，物品数为 $1$ 的堆为“小堆”。

若都为小堆，每次选择都只能是取走一个小堆。则堆的个数为偶数是必胜局面，堆的个数为奇数是必败局面。
若有大堆：
1. 大堆个数为 $1$，此时这个局面的 SG 值 $\neq 0$ （因为大堆能决定 SG 值的最高位不是第一位），若总堆数为奇数，将大堆取成小堆，否则就把大堆全取光。取后一定是奇数个小堆，是必败局面。所以当前局面是必胜局面。
2. 大堆个数 $>1$，此时这个局面的 SG 值若 $\neq 0$，则一定能走到一个 SG 值 $=0$ 的局面，且新局面是有大堆的（因为一次最多只能取完一个大堆，而大堆数 $>1$）；此时这个局面的 SG 值若 $=0$，则不管怎样取只能走到 SG 值 $\neq 0$ 且存在大堆的局面。假如前者一直保持那样操作，那么一定是后者进行一步操作后转到2.1.的必胜局面。所以前者是必胜局面，后者是必败局面。

综上所述，先手必胜当且仅当：

仅存在小堆且当前局面的 SG 值 $=0$。
存在大堆且当前局面的 SG 值 $\neq 0$。

我们把这个结论像 “多个有向图游戏的和和 SG 定理” 一样推广成更一般的形式：

Q: 为什么不像上一小节 “多个有向图游戏的和和 SG 定理” 将 ”Nim 游戏“ 和 “多个有向图游戏的和” 直接关联起来呢？

A: 在上一小节中，”Nim 游戏“ 到 “多个有向图游戏的和” 有个步骤是说明 “能走到 SG 值更大的局面” 这一条件是不影响结论的，用取石子模型意思即为可以 “放石子”，但不影响结论。所以在这里需要推广到可以放石子时结论是怎样的。

定义 Anti-SG 游戏：

决策集合为空的游戏者胜利。
其余规则均与 SG 游戏相同。

SJ 定理：对于任意一个 Anti-SG 游戏，如果规定当局面中所有单一游戏的 SG 值为 $0$ 时，游戏结束。则先手必胜当且仅当：(1) 游戏的 SG 函数不为 $0$ 且游戏中某一个单一游戏的 SG 函数大于 $1$；(2) 游戏的 SG 函数为 $0$ 且游戏中没有单一游戏的 SG 函数大于 $1$。

该定理是贾志豪在 IOI2009中国国家集训队论文《组合游戏略述——浅谈SG游戏的若干拓展及变形》中提出的，也可以去看他的论文。

下面，我将给出按照我自己理解结合《组合游戏略述——浅谈SG游戏的若干拓展及变形》的证明给出一个自认为略微好理解的证明：

我们只需要证明：

所有终止局面为必胜局面。（由 Anti-SG 游戏的定义可知）。
任何一个必败局面一定只能转移到必胜局面。
任何一个必胜局面至少能转移到一个必败局面。

设游戏的 SG 函数为 $SG$，每个单一游戏的 SG 函数为 $sg$。

现在，我将所有局面分成四类。

必胜局面：

$SG\neq 0,\exists sg>1$（游戏的 SG 函数不为 $0$ 且存在单一游戏的 SG 函数 $>1$）；
$SG=0,\forall sg\leq 1$（游戏的 SG 函数为 $0$ 且任意单一游戏的 SG 函数 $\leq 1$）。

必败局面：

$SG\neq 0,\forall sg\leq 1$（游戏的 SG 函数不为 $0$ 且任意单一游戏的 SG 函数 $\leq 1$）；
$SG=0,\exists sg>1$（游戏的 SG 函数为 $0$ 且存在单一游戏的 SG 函数 $>1$）。

下文称必胜/必败一/二代表必胜/必败局面的第1/2种情况，为了方便起见，使用大堆来表示 SG 函数 $>1$ 的单一游戏，小堆为 SG 函数 $=1$ 的游戏。

分好类后证明就很简单了：

关于必胜一的转移：

若大堆仅有一个，可以选择取完或者取成小堆，转移成必败一。
若大堆有多个，设 $SG$ 最高位为 $k$，则一定存在一个堆，其第 $k$ 位为 $1$，将其取成 $sg\oplus SG$，由于最多取走一个大堆，所以一定剩有大堆，故可以转移成必败二。

关于必胜二的转移：

若不可操作，直接胜利。
否则，可以产生一个小堆或者取走一个小堆，转移成必败一。

关于必败一的转移：

若产生一个大堆：因为 $SG\neq 0,\forall sg\leq 1$，所以 $SG=1$，由于大堆的 $sg$ 最高位 $>1$，所以新的 $SG\neq 0$ ，只能转移到必胜一。
若产生一个小堆或者取走一个小堆，只能转移成必胜二。
所以必败一无论怎样操作都只能转移到必胜局面。

关于必败二的转移：

因为 $SG=0,\exists sg>1$，所以大堆一定有多个，故只能转移到 $\exists sg>1$ 的局面；$SG=0$ 只能转移到 $SG\neq 0$，否则可以推出没取，与规则矛盾。所以只能转移到必胜一。

综上所述，任何一个必败局面一定只能转移到必胜局面，任何一个必胜局面至少能转移到一个必败局面，SJ 定理得证。

值得注意一点的是，在此游戏中，$\forall sg=0$ 时即可认为游戏结束，因为此局面的先手（必败方）无论取什么，后手都能取走新加的，重新转换成 $\forall sg=0$ 的局面，由于必败方不能无限取下去，所以必败方依然会失败。

此定理似乎没有那么重要，仅做了解博弈论证明方式用。

例题

Part3 例题

Cutting Game

给定一张 $N\times M$ 的矩形网格纸，两名玩家轮流行动。

在每一次行动中，可以任选一张矩形网格纸，沿着某一行或某一列的格线，把它剪成两部分。

首先剪出 $1\times 1$ 的格纸的玩家获胜。

两名玩家都采取最优策略行动，求先手是否能获胜。

$2\leq N,M\leq 200$。

题目链接：POJ 2311 Cutting Game，ACWing 219. 剪纸游戏

Solution

最后终止条件为剪出 $1\times 1$ 的获胜，不符公平组合游戏中的 “终止的局面为必败点” 的性质，但可以转化终止的局面，使得终止的局面为必败点。

能剪出 $1\times 1$ 的纸片当且仅当当前为 $1\times x$ 或 $x\times 1,x>1$ 的纸片，这些纸片一定是必败点。

那么把终点定义成当前局面为 $1\times x$ 或 $x\times 1,x>1$，就满足了公平组合游戏的性质。

设 $SG(x,y)$ 为 $x\times y$ 的局面的 SG 函数值。一刀可以横着切也可以竖着切，切完一刀后是分成了两个局面，由 SG 定理，如果这样切当前 SG 函数的值就为分成的两个局面的 SG 函数值的异或值。

所以有：

$SG(x,y)=\text{mex}(\{SG(i,y)\oplus SG(x-i,y)\mid 2\leq x-2\}\cup \{SG(x,i)\oplus SG(x,y-i)\mid 2\leq i\leq y-2\})$

注意到 $SG$ 不会超过 $N,M$，则可以在 $\mathcal{O}(N^3)$ 的复杂度内求解，也就是 $\mathcal{O}(N^2)$ 枚举，单次 $\mathcal{O}(N)$ 转移。

Code

int n, m;
int SG[210][210], vis[210];
void pre() {
	for(int x = 2; x <= 200; ++x)
		for(int y = 2; y <= 200; ++y) {
			for(int i = 0; i <= 200; ++i) vis[i] = 0;
			for(int i = 2; x - i >= 2; ++i) vis[SG[i][y] ^ SG[x-i][y]] = 1;
			for(int i = 2; y - i >= 2; ++i) vis[SG[x][i] ^ SG[x][y-i]] = 1;
			for(int i = 0; i <= 200; ++i)
				if(!vis[i]) {
					SG[x][y] = i;
					break;
				}
		}
}
signed main() {
	pre();
	while(scanf("%d%d", &n, &m) != EOF)
		printf("%s\n", SG[n][m] == 0 ? "LOSE" : "WIN");
	return 0;
}

do_while_true's blog

「学习笔记」博弈论