GT(博弈论)

badbottle2025/10/7大约 5 分钟

博弈论 (Game Theory)

原文oi wiki:博弈论

Bash 博弈

Bash 博弈是一种简单的取石子博弈，其规则如下：

初始只有一堆石子，数量为 $N$ 。
两个玩家轮流操作，每次可以从堆中取走不超过 $M$ （ $M \le N$ ）个石子（至少取走 1 个）。
无法进行操作的玩家判负。

Bash 博弈的关键在于观察：当 $N$ 是 $M+1$ 的倍数时，先手必败；当 $N$ 不是 $M+1$ 的倍数时，先手可通过一次操作将剩余石子数变为 $M+1$ 的倍数，从而获得必胜的策略。

Nim 博弈

Nim 博弈是博弈论中最基础、最典型的问题之一，规则为：

有若干堆石子，每堆数量可以不同。
两个玩家轮流操作，每次可以从任意一堆中取走任意数量的石子（至少取走 1 个）。
最后无法操作的玩家判负。

Nim 的判定（尼姆和）

用符号 $\oplus$ 表示按位异或（XOR）。设各堆数量为 $a_1,a_2,\dots,a_n$ ，定义尼姆和

S = a_1 \oplus a_2 \oplus \dots \oplus a_n.

若初始 $S = 0$ ，则先手必败；若 $S \ne 0$ ，则先手必胜。

下面给出标准的证明思路（分两步）：

必败态（ $S=0$ ）只能转移到必胜态（ $S\ne 0$ ）。
必胜态（ $S\ne 0$ ）至少存在一种操作能转移到必败态（ $S=0$ ）。

这两点合起来即可说明 $S=0$ 时先手无法避免败局，而 $S\ne 0$ 时先手可以选择必胜策略。

证明 2：必胜态可转为必败态

设当前异或和为

x = a_1\oplus a_2 \oplus \dots \oplus a_n \ne 0.

令 $k$ 为 $x$ 的最高位 1 的位置（从 0 位开始计）。由于该位在 $x$ 中为 1，必然存在某个堆 $a_i$ 在第 $k$ 位上也为 1（否则第 $k$ 位就无法被贡献为 1）。

令

b = a_i \oplus x.

注意到 $b < a_i$ （因为 $x$ 在第 $k$ 位为 1，异或会把该位从 1 变为 0，从而使数值变小），因此可以通过取走 $a_i-b$ 个石子将堆 $a_i$ 变为 $b$ ，这是一个合法操作。

替换后新的异或和为：

[ (a_1\oplus\dots\oplus a_i \oplus \dots \oplus a_n) \oplus a_i \oplus b = x \oplus a_i \oplus b = x \oplus a_i \oplus (a_i \oplus x) = 0. ]

因此必胜态存在至少一种操作能转为必败态，证明完毕。

实际上，这就是 Nim 判定的核心：先手需要把某一堆减小到 $a_i \oplus x$ ，从而将整体的异或和变为 0，把必败态留给对手。

(注：以上为标准 Nim 证明与说明，后续可以扩展到 SG 函数与更复杂的博弈合成规则。)

SG函数模板 Sprague–Grundy 理论指出，所有公平组合游戏都等价于单堆 Nim 游戏。这一结论主要应用的场景，就是游戏由多个相互独立的子游戏组成的情形。此时，游戏的状态判定可以通过计算子游戏的 SG 函数值的 Nim 和来完成。如果游戏本身没有这样的结构，那么，判定必胜状态和必败状态只需要应用前文博弈图一节的引理 SG（sprague - grundy）函数是基于经典 Nim 请弃准广得到的，在Nim博弃中，整个游戏（博弈）的结果是若干个子游戏的异或和，当异或和为 0时局面必败，当异或和不为 0 时局面必胜。 $sg(X)=mex({sg(y)|x->y})$ 意思是如果存在x->y,那么图中某个点的sg值是该点所有出点的mex结果。容易发现 $sg(0)=0$ ，它没有出边。我们举个小例子，假设有 1 堆石子，共7个，Alice（先手）和 Bob 每次可以从中拿取 1，3，4个，谁先无法操作谁就输了，那么请问 Alice 必胜还是必败？这个问题中，我们首先可以定义一个状态：sg（x）表示当前还有x个石子的局面的sg。然后通过题目意思可以知道转移的方式（即存在哪些边），我们从可以转移到 $sg(x)=mex(sg(x-1),sg(x-3),sg(x-4))$ 当然sg的参数不能为负数，这个要记得判断下。必败态应该是x=0时，因为此时就无法操作了，其余情况至少还能拿走一个。

计算sg函数

一般用记忆化搜索去计算:

i64 getSG(i64 x)
{
	//一般情况下有sg(0)=0，需根据实际情况设置
	if(!x)return x;
	//记忆化搜索
	if(sg.count(x))return sg[x];
	unordered_set<ll>st;
	//将出点的sg求mex得到当前点的mex
	int d[]={1,3,4};
	for(i64 i=0;i<3;++i)
	{
		if(x-d[i]>=0)st.insert(getSG(x-d[i]));
	}
	for(i64 i=0;;++i)if(!st.count(i))return sg[x]=i;
}