浅谈博弈论

chenyyy · 2025-08-09 21:59:24 · 算法·理论

前言

前几天与 fyh 谈了谈博弈论，感觉挺有意思的，决定学习一下，也分享一下收获。

海盗分金币

海盗分金币是博弈论里一个简单的经典游戏，需要一定的思维。

假设现在有五个海盗（P1, P2, P3, P4, P5），他们都极度聪明、理性、自私，优先考虑自己的生存，再考虑将金币最大化，且如果收益相同，海盗倾向于杀死前面的人。

他们得到了 100 枚金币，需要指定分配方案。规则如下：

1.海盗们按照顺序，一个接一个提出分配金币方案；

2.如果一个海盗的建议有百分之五十及以上的人同意，则这个方案通过，否则他将被杀死。

为了解决这个问题，我们可以从最简单的开始考虑。

1.一个海盗（P5）

这个海盗可以将所有金币独吞，此时 P5 最大收益为 100。

2.两个海盗（P4，P5）

P4 可以将金币独吞，此时 P5 反抗也没有用，因此 P4 最大收益为 100。

3.三个海盗（P3，P4，P5）

因为 P3 知道如果他死了那么 P5 一个金币也得不到，因此他可以给 P5 \ 1 个金币，那么 P5 就会支持他，因此 P3 的最大收益是 99。

4.四个海盗（P2，P3，P4，P5）

因为 P2 知道他死了后 P4 没有金币，所以他可以给 P4 \ 1 个金币收买人心，所以 P2 的最大收益是 99。

5.五个海盗（P1，P2，P3，P4，P5）

因为 P1 知道他死了后 P3 和 P5 都没有金币，因此他可以分别给他们 1 枚金币，于是 P1 的最大收益是 98。

至此我们便解决了这个简单的问题。

巴什博弈

巴什博弈是最基础的取石子游戏之一，其规则如下：

1.最开始有一堆石子，总共 n 个；

2.玩家轮流取石子，每次至少取 1 个，至多取 m 个；

3.取走最后一颗石子的胜。

必胜策略

当 n \bmod (m + 1) = 0 时，后手有必胜策略；

当 n \bmod (m + 1) \ne 0 时，先手有必胜策略。

证明

当 n \bmod (m + 1) \ne 0 时，先手可以取 n \bmod (m + 1) 个石子，然后无论后手取 x 个，先手都可以取 m + 1 - x 个石子，直至先手胜利，反之亦然。

Nim游戏

Nim 游戏是组合数学和博弈论中的经典问题，可以看作是多堆的巴什博弈。它的规则简单，但蕴含数学原理。

游戏规则

1.初始状态：n 堆石子，每堆分别有 p_1,p_2,\dots,p_n 个石子； 2.玩家操作：轮流拿石子，每次必须从 n 堆中的任意一堆中拿走至少 1 个石子（可以拿完）； 3.胜负判定：谁拿走最后一颗石子谁获胜。

解决方法

我们可以通过“Nim 和”来判断先手是否有必胜策略。

Nim 和

“Nim 和”其实就是所有石子数量的异或和。

异或就是一个二进制中的运算，在异或中相同位为 0，不同位为 1，通常计为 \operatorname{xor} ，如 4\operatorname{xor}5 = (100)_2\operatorname{xor}(101)_2 = (001)_2 = 1。

我们记“Nim 和”为 S，则 S = p_1\operatorname{xor}p_2\operatorname{xor}\dots\operatorname{xor}p_n。

于是我们得到这个结论：

1.当 S\ne0 时先手有必胜策略；

2.当 S=0 时后手有必胜策略。

下面我们证明这个结论。

证明

假设此时 S=0，则根据异或性质，无论怎么选，结果都是 S\ne0，因为当选走了某堆中的某些石子时，设选了第 i 堆 中的 x 个，则 S=p_1\operatorname{xor}\dots\operatorname{xor}(p_i-x)\operatorname{xor}\dots\operatorname{xor}p_n， 所以其中二进制中每位相同的数字的数量的奇偶性一定会发生变化，即新“Nim 和” S\ '\ne S，因此 S\ '\ne0。

而若此时 S\ne0，则我们可以选出一堆石子满足条件 p_i\operatorname{xor}S \le p_i，然后取走里面 p_i-p_i\operatorname{xor}S 个石子，于是新“Nim 和” S\ '= S\operatorname{xor}p_i\operatorname{xor}(p_i-(p_i-p_i\operatorname{xor}S))=S\operatorname{xor}p_i\operatorname{xor}p_i\operatorname{xor}S=0。

因此若 S\ne0 当先手按上文方案取石子时便可使 S=0，而后手无论怎么选都会使 S\ne0，于是先手有必胜策略，反之亦然。

于是我们便证明了“Nim 和”可以判断先手、后手有无必胜策略。

SG函数

定义

对于一个游戏状态 x，其 SG 函数的值的定义为：

其中 \operatorname{mex} 表示集合中最小的未出现过的非负整数，x\to y 表示 y 是 x 的后继。

性质

当 z 满足条件 z=x+y 时，SG(z)=SG(x)\operatorname{xor}SG(y)，注意，这里的 x+y 表示 x 与 y 的组合，即在此处意义下 2+4=(2,4)。

于是由结合律推广，SG(x)=SG(x_1+x_2+\dots x_n)=SG(x_1)\operatorname{xor}\dots\operatorname{xor}SG(x_n)。

下面我们证明这个结论。

证明

由上文，SG(z)=\operatorname{mex}\{SG(w)\mid z\to w\}，又因为 z = x+y,z\to w，所以 w = x+ u 或 w= y+v，于是得到 SG(z)=SG(x+y)=\operatorname{mex}\{\{SG(x+u)\mid y\to u\}\,\cup\,\{SG(y+v)\mid x\to v\}\}。

现在假设我们已经得到 SG(x+u)=SG(x)\operatorname{xor}SG(u) 和 SG(y+v)=SG(y)\operatorname{xor}SG(v)，我们便可以推出 SG(x+y) = SG(x)\operatorname{xor}SG(y)，原因是我们知道当 SG(x)=0 且 SG(y)=0 时 SG(z)=0。

下面给出证明方法。

我们令 X=SG(x)，Y=SG(y)，A=\{SG(x+u)\mid y\to u\}，B=\{SG(y+v)\mid x\to v\}。

于是我们需要证明：

即需证明：

1.X\operatorname{xor}Y\notin A\,\cup\,B；

2.对于所有 W < X\operatorname{xor} Y，都有 W\in A\,\cup\,B。

第一部分

假设 X\operatorname{xor}Y\in A，则存在 u 使得 SG(x+u)=X\operatorname{xor}Y。因为 y\to u，所以 SG(u)\ne SG(y)。但因为 SG(x + u)=SG(x)\operatorname{xor}SG(u)，所以：

与 Y\ne SG(u) 矛盾，因此 X \operatorname{xor}Y\notin A。

同理可得 X\operatorname{xor}Y\notin B，所以 X\operatorname{xor}Y\notin A\,\cup\,B。

第二部分

设 W<X\operatorname{xor}Y,我们需要证明 W\in A\,\cup\,B。

令：

因为 W < X\operatorname{xor}Y，所以 Z\ne0。

所以 Z\operatorname{xor}X=W\operatorname{xor}Y<X，即 x 存在某个后继 v 使得:

于是：

所以 W\in B。

因此我们便证明了上面两个条件，即：

证毕。

结语

信息竞赛接触的博弈论并不多，基本就是这些，其他的下次再写吧！