公平组合游戏
2026-05-17
定义
公平组合游戏需要严格满足以下条件:
- 两名玩家轮流行动。
- 局面对双方公开且无隐藏信息,且没有等概率随机元素。
- 同一个状态下两名玩家能做出的操作集合是相同的。
- 游戏必然在有限步内结束,通常约定无法操作的玩家为负。
图论建模
- 节点:当前局面
- 连边:可行操作
如果这么建模,当一个玩家面对出度为 0 的点,这个玩家就输了。
在 DAG 建模中,所有节点被严格归为两类:
- P 态:下一个操作的玩家必输。
- N 态:下一个操作的玩家必胜。
相应的,还有它们的转移:
- 若一个节点出度为 0,则该节点为 P 态。
- 若一个节点存在一个为 P 态的后继状态,则该节点为 N 态。
- 若一个节点所有后继状态都为 N 态,则该节点为 P 态。
因数减法博弈
给定一个正整数 n,两名玩家轮流操作,每次操作玩家可以减去当前数字的一个大于 1 的真因数,无法操作者判负(即面对 1)。
结论:奇数为 P;含奇数因子的偶数为 N;2k 时,k 为奇数是 P,否则为 N。
证明略。
Chomp Game
有一个 n×m 的矩形棋盘(n,m>1),两名玩家轮流操作,每次玩家可以选择一个未被涂黑的 (x,y),然后将以 (1,1)、(x,y) 为顶点的矩形涂黑,无法操作者判负(即面对全黑棋盘)。
结论:先手必胜。
证明:
假设后手必胜,那么我们让先手第一步走 (1,1),根据后手必胜,此时它一定能走出一步必胜棋,记为 (x,y)。
由于先手比后手先走,先手可以先选择 (x,y) 从而获胜,因此先手必胜。
巴什博弈
桌面上有 n 堆棋子,两名玩家轮流取,每次最多取 m 个,最少取 1 个,无法操作者判负。
经过我们的注意,若先手取 x 个,我们总能取走 m−x+1 个,总共让石子数减少 m+1 个,因此:
- 若 (m+1)∣n,后手必胜。
- 若 (m+1)∤n,先手必胜。
Nim 游戏
桌面上有 n 堆石子,第 i 堆有 ai 个石子,两名玩家轮流操作,每次可以从一堆中取走任意多的石子,谁取完最后一个谁胜利,给定每堆石子数量,怎么判断先手必胜还是先手必输?
Bouton 定理
定义当前局面的 Nim 和(异或和)为 S=a1⊕a2⊕⋯⊕an。
- 若 S=0,则当前局面为 P 态,即先手必败。
- 若 S=0,则当前局面为 N 态,即先手必胜。
接下来是 Bouton 定理的证明。
- 对于全空局面,显然为 P 态。
- P 态的转移:
假设当前局面 S=0,显然玩家如何操作后产生的新异或和 S′=0。 - N 态的转移:
显然可以将提供 S 最高位 1 的那一堆取走最高位 1 与剩下 1 的差,此时 S=0。
SG 函数
定义 mex 函数表示一个集合中不属于这个集合的最小非负整数。
对于有向无环图中的一个节点 u,定义其 SG 函数为:SG(u)=mex({SG(v)∣u→v})。
根据这个定义,我们可以得到:SG(x)=0 时,当前节点为 P 态;反之则为 N 态。
Sprague-Grundy 定理
设复合游戏 G 由 n 个互相独立的子游戏 G1,⋯,Gn 组成,则复合游戏的 SG 值等于其各子游戏值的异或和:
SG(G)=SG(G1)⊕SG(G2)⊕⋯⊕SG(Gn)
集合 Nim 游戏
桌上有 n 堆棋子,给定包含 k 个正整数的集合 S,两名玩家轮流操作。对于一个操作,可以从一堆中取出 x(x∈S)个石子,无法操作者判负。
很明显,我们需要考虑一局游戏,令 f[i] 表示有 i 个棋子的 SG 值,根据定义:
f[i]=mex({f[i−x]∣x∈S,i≥x})
显然可以用 O(V⋅∣S∣) 的动态规划处理出 f 所有取值,那么最终答案即只需要关注 (i=1⨁nf[Ai])=0 即可。
齐肯多夫定理
对于任何正整数 n,都可以被唯一地表示为若干个不连续的斐波那契数之和,形式化的:
n=Fk1+Fk2+⋯+Fkm(k1≥k2+2,k2≥k3+2,⋯)
斐波那契博弈
有一堆石子,共 n 个,两名玩家轮流取,无法操作者判负,要求:
- 先手第一步不能全部取完。
- 第二步开始,当前操作人取的个数不能超过对手上次操作的 2 倍。
给定 n,先手必胜还是必败?
当 n 为斐波那契数的时候,先手必败;否则先手必胜。
至于证明,考虑将 n 使用齐肯多夫定理分解,先手直接取走最小的 Fkm,由于分解出的斐波那契数不连续,所以 Fkm−1>2⋅Fkm,即后手不能取走 Fkm−1,先手永远掌握局势。
Beatty 定理
若有两个正无理数 α,β>1 且 α1+β1=1,则序列 ⌊kα⌋ 和 ⌊kβ⌋ 必定完美分割正整数集。
证明:
考虑 ⌊nα⌋ 和 ⌊nβ⌋ 中小于正整数 N 的数字共有多少个。
对于 α 序列,⌊nα⌋<N⟹nα<N⟹n<αN,由于 α 为无理数,即共有 ⌊αN⌋ 个小于 N 的数。
所以两个序列小于 N 的数共有 ⌊αN⌋+⌊βN⌋ 个。
根据 x=⌊x⌋+{x},原式变为:
αN−{αN}+βN−{βN}=N(α1+β1)−({αN}+{βN})
由于倒数和为 1,原式变成 N−({αN}+{βN}),由于原式结果应为整数,且 N 为整数,即两个无理数小数之和为整数,只能为 1,所以原式为 N−1,证毕。
威佐夫博弈
有两堆石子,分别有 a 个和 b 个,两名玩家轮流操作,无法操作者判负,每次操作有两种选择:
- 从其中一堆取任意正整数个石子。
- 从两堆中同时取走相同正整数个石子。
给定 a,b,问谁必胜。
我们可以将 (a,b) 映射为二维平面上的一个坐标。
由于只能单堆减小或双堆同时减小相同的量,游戏过程等价于:在网格图上有一枚棋子,每次只能向左、向下、或向左下方对角线移动任意步。 目标是走到原点 (0,0)。
这样来看,如果某个节点为 P,那么它正上、正右、右上方都将为 N 态。
列举一些例子,容易发现:
- 第 k 个 P 态的坐标差值 Δ=bk−ak=k。
- ak 和 bk 构成的集合,必须不重不漏的包含所有非负整数。
考虑证明:
- P 只能到 N:
- 单堆取:改变 ak 或 bk,差值变化因此改变后不在 P 态。
- 双堆取:坐标差值不变,由于差值为 k 的 P 态仅有一个,所以改变后不为 P 态。
- N 能走到 P:
令当前状态为 (a,b),且 a≤b,k=b−a。- 若 a>ak:由于 b−a=bk−ak=k,两堆同时取 a−ak 个即可。
- 若 a≤ak:由于每个数必定出现,即 a 必定是更小的 ai 或 bi,分别按照 b 取到 bi 或 b 取到 ai 即可。
那么如何快速求出 (ak,bk) 呢?考虑将差值的规律带入 Beatty 定理:
令 ak=⌊kα⌋,bk=⌊kβ⌋。
由于 bk−ak=k,即近似有 β−α=1,将其与 α1+β1=1 联立,解得:
{α=21+5β=23+5
由此,ak=⌊k⋅21+5⌋,bk=ak+k。
阶梯博弈
有 n 个台阶,第 i 阶上有 ai 个棋子,两个玩家轮流操作,每次可以将第 i 阶上的若干个棋子移动到 i−1,第 0 阶的棋子无法移动,无法操作者判负,则先手必胜还是先手必败?
由于不满足各个台阶相互独立,考虑只看奇数阶,看作一个普通 Nim 游戏,考虑操作:
- 奇数阶到偶数阶:相当于拿走石子。
- 偶数阶到奇数阶:相当于增加石子,在普通 Nim 中不允许,所以我们可以立刻将其拨弄到偶数阶,维护状态。
因此,只需要判断奇数阶 ai 的异或和即可。
分裂 Nim 游戏
桌面上有 n 堆石子,两名玩家轮流操作,无法操作者判负,每次操作有两种选择:
- 从一堆石子中取若干个。
- 将一堆石子分裂成两堆。
令 f[x] 表示一堆数量为 x 的石子的 SG 值。
- 对于操作 1:可以转移到 f[0],f[1],⋯,f[x−1] 。
- 对于操作 2:将 x 分裂成 i 和 x−i,根据 SG 定理,这两堆石子等价于 f[i]⊕f[x−i]。
将状态总结一下:
f[x]=mex({f[k]∣0≤k<x}∪{f[i]⊕f[x−i]∣1≤i<x})
反常 Nim 游戏
有 n 堆石子,两个玩家轮流操作,每次取一堆中任意多石子,无法操作者获胜。
显然传统的 N/P 态不好使了,因此衍生出 Sprague-John 定理。
Sprague-John 定理
为了解决反常 Nim 游戏,规定:
- 全小局:全场石子满足 ai≤1。
- 存大局:全场存在一堆 ai>1。
SJ 定理内容:
N 态当且仅当满足以下两种情况之一:
- 处于全小局且全局异或和 S=0。
- 处于存大局且全局异或和 S=0。
证明:
- 全小局:
- 若 S=0,即有偶数个 1,最后一个 1 被后手拿走,先手获胜。
- 若 S=0,即有奇数个 1,最后一个 1 被先手拿走,先手必败。
- 存大局:
- 若 S=0,进行任意操作必定使得 S=0 且存在 ai>1。
- 若 S=0,若有多于一个 ai>1,转移到存大局且 S=0(P 态);若仅有一个 ai>1,则操作 ai 使得留下奇数个 1(P 态)。
树上删边博弈
给定一颗树,每次可以删去一条边,这条边删除后不与根节点相连的子树消失,两名玩家轮流操作,无法操作者判负,请问先手必胜还是必败。
对于当前节点 u 及其儿子 v1,v2,⋯,vk,由于各个儿子相互独立,根据 SG 定理将其异或,由于有 (u,vi) 这条边,相当于取石子游戏多了一颗石子,即:
SG(u)=i=1⨁k(SG(vi)+1)
所以只需要对这棵树进行 DFS,如果根节点 SG 不等于 1,先手必胜。
