专栏文章

浅谈博弈论

cchenyyy
算法·理论参与者 9已保存评论 9

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
9 条
当前快照
1 份
快照标识符
@miofc14r
此快照首次捕获于
2025/12/02 18:17
3 个月前
此快照最后确认于
2025/12/02 18:17
3 个月前
查看原文

前言

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

海盗分金币

海盗分金币是博弈论里一个简单的经典游戏，需要一定的思维。
假设现在有五个海盗（P1, P2, P3, P4, P5），他们都极度聪明、理性、自私，优先考虑自己的生存，再考虑将金币最大化，且如果收益相同，海盗倾向于杀死前面的人。
他们得到了 100100 枚金币，需要指定分配方案。规则如下：
1.海盗们按照顺序，一个接一个提出分配金币方案；
2.如果一个海盗的建议有百分之五十及以上的人同意，则这个方案通过，否则他将被杀死。
为了解决这个问题，我们可以从最简单的开始考虑。

1.一个海盗（P5）

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

2.两个海盗（P4，P5）

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

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

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

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

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

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

因为 P1 知道他死了后 P3 和 P5 都没有金币，因此他可以分别给他们 11 枚金币，于是 P1 的最大收益是 9898。
至此我们便解决了这个简单的问题。

巴什博弈

巴什博弈是最基础的取石子游戏之一，其规则如下：
1.最开始有一堆石子，总共 nn 个；
2.玩家轮流取石子，每次至少取 11 个，至多取 mm 个；
3.取走最后一颗石子的胜。

必胜策略

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

证明

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

Nim游戏

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

游戏规则

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

解决方法

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

Nim 和

“Nim 和”其实就是所有石子数量的异或和。
异或就是一个二进制中的运算，在异或中相同位为 00，不同位为 11，通常计为 xor⁡\operatorname{xor} ，如 4xor⁡5=(100)2xor⁡(101)2=(001)2=14\operatorname{xor}5 = (100)_2\operatorname{xor}(101)_2 = (001)_2 = 1。
我们记“Nim 和”为 SS，则 S=p1xor⁡p2xor⁡…xor⁡pnS = p_1\operatorname{xor}p_2\operatorname{xor}\dots\operatorname{xor}p_n。
于是我们得到这个结论：
1.当 S≠0S\ne0 时先手有必胜策略；
2.当 S=0S=0 时后手有必胜策略。
下面我们证明这个结论。

证明

假设此时 S=0S=0，则根据异或性质，无论怎么选，结果都是 S≠0S\ne0，因为当选走了某堆中的某些石子时，设选了第 ii 堆 中的 xx 个，则 S=p1xor⁡…xor⁡(pi−x)xor⁡…xor⁡pnS=p_1\operatorname{xor}\dots\operatorname{xor}(p_i-x)\operatorname{xor}\dots\operatorname{xor}p_n， 所以其中二进制中每位相同的数字的数量的奇偶性一定会发生变化，即新“Nim 和” S ′≠SS\ '\ne S，因此 S ′≠0S\ '\ne0。
而若此时 S≠0S\ne0，则我们可以选出一堆石子满足条件 pixor⁡S≤pip_i\operatorname{xor}S \le p_i，然后取走里面 pi−pixor⁡Sp_i-p_i\operatorname{xor}S 个石子，于是新“Nim 和” S ′=Sxor⁡pixor⁡(pi−(pi−pixor⁡S))=Sxor⁡pixor⁡pixor⁡S=0S\ '= 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≠0S\ne0 当先手按上文方案取石子时便可使 S=0S=0，而后手无论怎么选都会使 S≠0S\ne0，于是先手有必胜策略，反之亦然。
于是我们便证明了“Nim 和”可以判断先手、后手有无必胜策略。

SG函数

定义

对于一个游戏状态 xx，其 SG 函数的值的定义为： SG(x)=mex⁡{SG(y)∣x→y}SG(x)=\operatorname{mex}\{SG(y)\mid x\to y\}
其中 mex⁡\operatorname{mex} 表示集合中最小的未出现过的非负整数，x→yx\to y 表示 yy 是 xx 的后继。

性质

当 zz 满足条件 z=x+yz=x+y 时，SG(z)=SG(x)xor⁡SG(y)SG(z)=SG(x)\operatorname{xor}SG(y)，注意，这里的 x+yx+y 表示 xx 与 yy 的组合，即在此处意义下 2+4=(2,4)2+4=(2,4)。
于是由结合律推广，SG(x)=SG(x1+x2+…xn)=SG(x1)xor⁡…xor⁡SG(xn)SG(x)=SG(x_1+x_2+\dots x_n)=SG(x_1)\operatorname{xor}\dots\operatorname{xor}SG(x_n)。
下面我们证明这个结论。

证明

由上文，SG(z)=mex⁡{SG(w)∣z→w}SG(z)=\operatorname{mex}\{SG(w)\mid z\to w\}，又因为 z=x+y,z→wz = x+y,z\to w，所以 w=x+uw = x+ u 或 w=y+vw= y+v，于是得到 SG(z)=SG(x+y)=mex⁡{{SG(x+u)∣y→u} ∪ {SG(y+v)∣x→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)xor⁡SG(u)SG(x+u)=SG(x)\operatorname{xor}SG(u) 和 SG(y+v)=SG(y)xor⁡SG(v)SG(y+v)=SG(y)\operatorname{xor}SG(v)，我们便可以推出 SG(x+y)=SG(x)xor⁡SG(y)SG(x+y) = SG(x)\operatorname{xor}SG(y)，原因是我们知道当 SG(x)=0SG(x)=0 且 SG(y)=0SG(y)=0 时 SG(z)=0SG(z)=0。
下面给出证明方法。
我们令 X=SG(x)X=SG(x)，Y=SG(y)Y=SG(y)，A={SG(x+u)∣y→u}A=\{SG(x+u)\mid y\to u\}，B={SG(y+v)∣x→v}B=\{SG(y+v)\mid x\to v\}。
于是我们需要证明： SG(x+y)=mex⁡{A ∪ B}=Xxor⁡YSG(x+y)=\operatorname{mex}\{A\,\cup\,B\}=X\operatorname{xor}Y
即需证明：
1.Xxor⁡Y∉A ∪ BX\operatorname{xor}Y\notin A\,\cup\,B；
2.对于所有 W<Xxor⁡YW < X\operatorname{xor} Y，都有 W∈A ∪ BW\in A\,\cup\,B。

第一部分

假设 Xxor⁡Y∈AX\operatorname{xor}Y\in A，则存在 uu 使得 SG(x+u)=Xxor⁡YSG(x+u)=X\operatorname{xor}Y。因为 y→uy\to u，所以 SG(u)≠SG(y)SG(u)\ne SG(y)。但因为 SG(x+u)=SG(x)xor⁡SG(u)SG(x + u)=SG(x)\operatorname{xor}SG(u)，所以： SG(u)xor⁡X=Xxor⁡Y⟹Y=SG(u)SG(u)\operatorname{xor}X=X\operatorname{xor}Y\Longrightarrow Y=SG(u) 与 Y≠SG(u)Y\ne SG(u) 矛盾，因此 Xxor⁡Y∉AX \operatorname{xor}Y\notin A。
同理可得 Xxor⁡Y∉BX\operatorname{xor}Y\notin B，所以 Xxor⁡Y∉A ∪ BX\operatorname{xor}Y\notin A\,\cup\,B。

第二部分

设 W<Xxor⁡YW<X\operatorname{xor}Y,我们需要证明 W∈A ∪ BW\in A\,\cup\,B。
令： Z=Xxor⁡Yxor⁡WZ=X\operatorname{xor}Y\operatorname{xor}W
因为 W<Xxor⁡YW < X\operatorname{xor}Y，所以 Z≠0Z\ne0。
所以 Zxor⁡X=Wxor⁡Y<XZ\operatorname{xor}X=W\operatorname{xor}Y<X，即 xx 存在某个后继 vv 使得: SG(v)=Wxor⁡YSG(v)=W\operatorname{xor}Y 于是： SG(y+v)=SG(v)xor⁡SG(y)=(Wxor⁡Y)xor⁡Y=WSG(y + v)=SG(v)\operatorname{xor}SG(y)=(W\operatorname{xor}Y)\operatorname{xor}Y=W 所以 W∈BW\in B。
因此我们便证明了上面两个条件，即： SG(x+y)=SG(x)xor⁡SG(y)SG(x+y)=SG(x)\operatorname{xor}SG(y) 证毕。

结语

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

评论

共 9 条评论，欢迎与作者交流。

正在加载评论...