上一篇刚掌握了普通 Nim 的异或套路,朋友转头就把规则改了三处:
- “每堆每次只能拿 \(1\)、\(3\) 或 \(4\) 颗,现在有三堆 \((5, 8, 12)\),你来算!”
- “或者每回合除了拿石子,还可以把某一堆劈成两堆,怎么破?”
- “再不然,桌上有几排保龄球瓶,每次能打倒 \(1\) 个或相邻 \(2\) 个,把一排打断成两截!”
光靠 第 01 篇 的 \(\mathcal{P}/\mathcal{N}\) 二值标签,面对多堆组合会立刻卡壳——知道“堆 A 单独是 \(\mathcal{N}\)、堆 B 单独也是 \(\mathcal{N}\)”,根本推不出“A 和 B 放在一起”谁赢(两堆普通 Nim 的 \((2, 2)\) 都是 \(\mathcal{N}\),合在一起却是 \(\mathcal{P}\);而 \((2, 3)\) 都是 \(\mathcal{N}\),合在一起却是 \(\mathcal{N}\))。
解决这个瓶颈的,是组合博弈论中最具威力的统一工具——Sprague-Grundy 定理(由 Roland P. Sprague 于 1935 年在 Tôhoku Mathematical Journal 与 Patrick M. Grundy 于 1939 年在剑桥学生数学刊物 Eureka 上各自独立发现)。它用一个极简单的非负整数函数 \(g(x)\),把几乎所有正常规则下的公平小游戏一次性折叠回普通 Nim。
一、博弈和与 \(\operatorname{mex}\):给每个状态称出“等价石子数”
先把“多个游戏摆在同一张桌上”写成严格定义。
给定若干独立的有限公平正常博弈 \(G_1, G_2, \dots, G_m\),它们的析取和(Disjunctive Sum)记作 \(G_1 + G_2 + \dots + G_m\):每轮玩家任选其中一个尚未结束的子游戏 \(G_i\),并在该子游戏内走一步合法操作,其他子游戏原封不动;所有子游戏都无路可走时,当前轮到的玩家判负。
普通的 \(m\) 堆 Nim \((a_1, \dots, a_m)\) 正是 \(m\) 个单堆 Nim 游戏的析取和。我们用记号 \(*k\) 表示“大小为 \(k\) 的单堆 Nim 游戏”(又称 Nimber)。
现在给任意公平博弈有向无环图(DAG)中的每个状态 \(v\) 定义它的 Sprague-Grundy 值(SG 值) \(g(v)\):
\[ g(v) = \operatorname{mex}\{ g(u) \mid v \to u \text{ 是合法走法} \}. \]
其中 \(\operatorname{mex}(S)\)(Minimum Excluded value,最小排除非负整数)定义为不在非负整数集合 \(S\) 中的最小非负整数:
- \(\operatorname{mex}(\varnothing) = 0\)(终局没有出边,SG 值恒为 \(0\));
- \(\operatorname{mex}(\{0, 1, 3\}) = 2\);
- \(\operatorname{mex}(\{1, 2, 5\}) = 0\)(只要集合里缺 \(0\),结果立刻是 \(0\))。
检查一下单堆 Nim 的 SG 值:终局 \(0\) 堆没有出边,故 \(g(0) = \operatorname{mex}(\varnothing) = 0\);\(1\) 堆只能走到 \(0\),故 \(g(1) = \operatorname{mex}(\{0\}) = 1\);归纳可得 \(n\) 堆能走到 \(0, 1, \dots, n-1\),故 \(g(n) = \operatorname{mex}(\{0, 1, \dots, n-1\}) = n\)。
再看一张带跳跃边的一般 DAG:
图 1|一般 DAG 上的自底向上 \(\operatorname{mex}\)
计算。 注意两个关键现象:第一,所有 \(g(v) = 0\)
的节点(v0、v3)恰好就是 \(\mathcal{P}\) 态,因为 \(0 \notin \{g(u)\}\)
等价于“没有出边指向 \(0\)(\(\mathcal{P}\)
态)”;第二,合法走法完全有可能让 SG
值变大!图中橙色边 v4 -> v2 就把 SG
值从 \(1\) 抬高到了 \(2\)。
二、核心直觉:为什么 SG 值能变大,却依然严格等价于 Nim 堆?
这是读 Sprague-Grundy 定理时最容易卡壳的一步。
Sprague-Grundy 定理(Sprague 1935;Grundy 1939):
- 任何有限、公平、正常规则下的单组件局面 \(G\),在任意析取和中都与单堆 Nim \(*g(G)\) 完全等价(即对任意陪伴游戏 \(H\),\(G + H\) 与 \(*g(G) + H\) 胜负完全相同)。
- 推论:析取和 \(G_1 + G_2 + \dots + G_m\) 是 \(\mathcal{P}\) 态,当且仅当 \[ g(G_1) \oplus g(G_2) \oplus \dots \oplus g(G_m) = 0. \]
要证明 \(G\) 和 \(*k\)(其中 \(k = g(G)\))完全等价,只需证明一件事:把 \(G\) 和 \(*k\) 摆在同一张桌上玩析取和游戏 \(G + *k\),后手必胜(\(G + *k \in \mathcal{P}\))!
为什么只要证明了 \(G + *k \in \mathcal{P}\),就说明在任意更大的局面 \(G + H\) 里都能把 \(G\) 替换成 \(*k\)?逻辑极其简洁:假设 \(*k + H \in \mathcal{P}\),那么 \((G + H) + (*k + *k) = (G + *k) + (*k + H)\) 是两个 \(\mathcal{P}\) 态之和,必然是 \(\mathcal{P}\) 态(后手在两个子局里各自维持必胜即可);同时 \(*k + *k\) 本身靠镜像也是 \(\mathcal{P}\) 态,因此 \(G + H\) 不可能是 \(\mathcal{N}\) 态(否则先手在 \(G + H\) 走胜着就能在整体里翻盘,矛盾)。
现在看最精彩的部分——如何证明 \(G + *k \in \mathcal{P}\)?
假设当前满足不变量 \(g(G) = k\) 且 Nim 堆大小为 \(*k\)。轮到先手行动,他只有三种可能,后手对每一种都有精准的还手方式:
图 2|\(G + *k \in \mathcal{P}\) 的三分支构造证明。 关键在于右栏 Case 3:如果对手在 \(G\) 里走了一步让 SG 值从 \(k\) 暴涨到 \(m > k\),后手压根不需要往 Nim 堆里加石子,而是直接利用 \(\operatorname{mex}\) 定义把 \(G'\) 当场拍回 \(k\)!
逐条核对这三种分支:
- 分支 1(对手把 Nim 堆 \(*k\) 缩小到 \(*j\),其中 \(0 \le j <
k\)):
根据 \(k = \operatorname{mex}\{g(G')\}\) 的定义,既然 \(k\) 是最小缺失的非负整数,那么所有比 \(k\) 小的非负整数 \(0, 1, \dots, k-1\) 必然全都出现在 \(G\) 的后继 SG 值里!所以 \(G\) 中必定存在至少一步合法走法 \(G \to G'\) 使 \(g(G') = j\)。后手在 \(G\) 里走出这一步,桌面立刻恢复 \(g(G') = j\) 且 Nim 堆为 \(*j\)。 - 分支 2(对手在 \(G\) 中走一步 \(G \to G'\),使 SG 值变小到
\(j <
k\)):
后手直接把 Nim 堆 \(*k\) 拿掉 \(k - j\) 颗变成 \(*j\),桌面恢复 \(g(G') = j\) 与 \(*j\)。 - 分支 3(对手在 \(G\) 中走一步 \(G \to G'\),使 SG 值变大到
\(m >
k\)):
这一步看起来最吓人——Nim 堆不能加石子啊!但别忘了 第 02 篇 Poker Nim 的“原路撤销”哲学!
既然 \(g(G') = m = \operatorname{mex}\{g(G'')\}\) 且 \(k < m\),那么 \(k\) 一定落在 \(G'\) 的后继 SG 集合里!于是后手根本不碰 Nim 堆 \(*k\),直接在 \(G'\) 里走一步 \(G' \to G''\) 使 \(g(G'') = k\)!桌面瞬间恢复 \(g(G'') = k\) 与 \(*k\),而且图 \(G\) 沿着有向边严格前进了两步。
由于图 \(G\) 有限无环、Nim 堆有限,对手不可能靠分支 3 无限拖延。每轮之后桌面都回到“\(g(G) = \text{Nim 堆大小}\)”的不变量,直到最终双双归零、对手无路可走认输。
这一刻你就能彻底明白 \(\operatorname{mex}\) 的设计意图:\(\operatorname{mex}\) 恰好是让“向下镜像(分支 1)”和“向上回弹(分支 3)”同时成立的唯一递归函数!
三、三大高频游戏家族:用 SG 一网打尽
拿到 Sprague-Grundy 定理后,遇到多组件公平游戏只需要两步:第一步算单个组件的 SG 表;第二步把所有组件的 SG 值异或起来,按普通 Nim 的 3 步口算法找目标 SG 值,再反查对应的合法动作。
家族 1:多堆减法博弈(Subtraction Games)
回到开头的问题:每堆每次只能拿 \(S = \{1, 3, 4\}\) 颗。先算出单堆 \(n = 0\text{–}13\) 的 SG 值:
| \(n\) | \(0\) | \(1\) | \(2\) | \(3\) | \(4\) | \(5\) | \(6\) | \(7\) | \(8\) | \(9\) | \(10\) | \(11\) | \(12\) | \(13\) |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 可达 \(g(n-S)\) | \(\varnothing\) | \(\{0\}\) | \(\{1\}\) | \(\{0,0\}\) | \(\{1,1,0\}\) | \(\{2,0,1\}\) | \(\{3,1,0\}\) | \(\{2,2,1\}\) | \(\{0,3,2\}\) | \(\{1,2,3\}\) | \(\{0,0,2\}\) | \(\{1,1,0\}\) | \(\{2,0,1\}\) | \(\{3,1,0\}\) |
| \(g(n)\) | \(0\) | \(1\) | \(0\) | \(1\) | \(2\) | \(3\) | \(2\) | \(0\) | \(1\) | \(0\) | \(1\) | \(2\) | \(3\) | \(2\) |
周期为 \(7\),循环节是
[0, 1, 0, 1, 2, 3, 2](即 \(g(n)\) 仅取决于 \(n \bmod 7\))。
注意这里体现出 SG 值与单纯 \(\mathcal{P}/\mathcal{N}\) 标签的本质区别:\(n = 4\) 和 \(n = 5\) 单独都是 \(\mathcal{N}\) 态,但 \(g(4) = 2,\ g(5) = 3\),两堆 \((4, 5)\) 的异或为 \(2 \oplus 3 = 1 \neq 0\)(先手把 \(5 \to 4\) 拿 \(1\) 颗赢);而 \(n = 4\) 和 \(n = 6\) 虽然大小不同,但 \(g(4) = g(6) = 2\),合在一起 \((4, 6)\) 异或为 \(0\),居然是后手必胜!
家族 2:拆堆游戏(Splitting Games:一步变两堆!)
这是面试和算法题最爱用来“欺负”人的花招:走一步不是让一堆变小,而是把一堆劈成两堆独立的子堆!
很多人在这直接卡死,其实套进 Sprague-Grundy 只有一行公式:如果走一步把状态 \(n\) 拆成了两个独立子游戏 \(a\) 和 \(b\),那这一步抵达的新局面就是析取和 \(a + b\),由 SG 定理,该后继状态的 SG 值就是 \(g(a) \oplus g(b)\)!因此只需把所有“拆堆后的异或值”一起塞进 \(\operatorname{mex}\) 集合即可。
来看三个在组合博弈史上赫赫有名的拆堆游戏:
Lasker’s Nim(拉斯克 Nim,世界国际象棋冠军 Emanuel Lasker 提出):
每回合既可以像普通 Nim 一样从一堆拿走至少 \(1\) 颗石子,也可以把一堆拆成两堆非空石子(总石子数不变!)。
按递归式 \(g(n) = \operatorname{mex}\big(\{g(k) \mid 0 \le k < n\} \cup \{g(a) \oplus g(n-a) \mid 1 \le a \le \lfloor n/2 \rfloor\}\big)\) 计算,仓库同目录脚本sg_lab.py跑出的前 \(17\) 项如下: \[ g(0\dots 16) = [0,\ 1,\ 2,\ 4,\ 3,\ 5,\ 6,\ 8,\ 7,\ 9,\ 10,\ 12,\ 11,\ 13,\ 14,\ 16,\ 15]. \] 规律一目了然:相对普通 Nim,仅把每个 \(4k+3\) 和 \(4k+4\) 互换了一下!即对 \(k \ge 0\): \[ g(4k+1)=4k+1,\quad g(4k+2)=4k+2,\quad g(4k+3)=4k+4,\quad g(4k+4)=4k+3. \] 为什么 \(g(3) = 4\)?因为 \(3\) 拿石子能到 \(g(0)=0, g(1)=1, g(2)=2\),劈成 \((1, 2)\) 能到 \(g(1) \oplus g(2) = 1 \oplus 2 = 3\),于是 \(\operatorname{mex}(\{0, 1, 2, 3\}) = 4\)!而 \(4\) 无论怎么拿或劈,都无法凑出 \(3\)(劈成 \((1,3)\) 得 \(1 \oplus 4 = 5\),劈成 \((2,2)\) 得 \(2 \oplus 2 = 0\)),于是 \(g(4)\) 掉回 \(3\)。Kayles(保龄球瓶博弈,Henry Dudeney 1908 / Sam Loyd):
一排 \(n\) 个紧挨着的瓶子,每次可以打倒任意 \(1\) 个瓶子,或打倒任意 \(2\) 个相邻瓶子;打倒后左右剩下的瓶子分成两段独立的短排。因此: \[ g(n) = \operatorname{mex}\Big(\{g(i) \oplus g(n-1-i)\}_{0 \le i < n} \cup \{g(i) \oplus g(n-2-i)\}_{0 \le i < n-1}\Big). \] 第 01 篇练习 5 中单排 Kayles 可以靠对称秒杀,但多排 Kayles 必须用 SG 异或。
这里藏着一个极其经典的学术警示(Guy & Smith, 1956):如果你只算前 \(30\) 项,Kayles 的 SG 值看起来毫无规律;直到算到 \(n = 71\) 之后(最后一个反常点是 \(n = 70\),其 \(g(70) = 6\) 而 \(g(82) = 2\)),整个序列才终于进入严格的 12 周期循环!永远不要仅凭前 15 项看似乱序或看似周期就草率下结论。Grundy’s Game(格伦迪博弈):
每回合选一堆,将其劈成两堆数量严格不相等的非空石子(因此大小为 \(1\) 或 \(2\) 的堆无法再劈,均为终局 \(g(1)=g(2)=0\))。前 \(21\) 项为: \[ g(0\dots 20) = [0, 0, 0, 1, 0, 2, 1, 0, 2, 1, 0, 2, 1, 3, 2, 1, 3, 2, 4, 3, 0]. \] Berlekamp、Conway 和 Guy 在 Winning Ways 中猜想它最终也是周期的;Achim Flammenkamp 用计算机一口气算到了 \(n = 2^{35}\)(超过 340 亿项),依然没有发现周期——这至今是组合博弈论里最著名的未解开放问题之一!
图 3|四类公平博弈的 SG
序列演化曲线(由仓库同目录的 sg_lab.py
生成)。 红色圆点标出所有 \(g(n)=0\) 的 \(\mathcal{P}\) 态:左上 \(S=\{1,3,4\}\) 周期 \(7\);右上 \(S=\{1,4,5\}\) 周期 \(8\);左下 Lasker’s Nim
呈锯齿线性增长(\(4k+3\) 与
\(4k+4\) 互换);右下
Kayles 在橙色虚线 \(n =
71\) 之前存在漫长的前周期(pre-period),之后锁死周期
\(12\)。
家族 3:树形砍边——Green Hackenbush 与冒号原理
一棵(或多棵)全部由绿色边构成的树扎根在地面上。两人轮流砍断任意一条绿色边;砍断后所有不再与地面连通的树枝全部掉落消失,无边可砍者输。
这看起来跟石子堆毫无关系,但只要用上 Colon Principle(冒号原理,Berlekamp–Conway–Guy 1982),整片森林瞬间坍缩成一句话:
树形 Green Hackenbush 的 SG 递推式:
- 叶子节点(无子树)的 SG 值为 \(0\);
- 如果节点 \(u\) 有若干子节点 \(c_1, c_2, \dots, c_r\),则每条边 \((u, c_i)\) 把子树 \(c_i\) 的 SG 值抬高 \(1\),再在节点 \(u\) 处全部按位异或: \[ g(u) = \bigoplus_{i=1}^{r} \big(g(c_i) + 1\big). \]
直觉验证:
- 一根长为 \(L\) 的独木竹竿(无分叉):自顶向下每多一节边,SG 值加 \(1\),故长为 \(L\) 的竹竿完全等价于大小为 \(L\) 的 Nim 堆(砍断第 \(k\) 节就等价于把堆缩成 \(k-1\)!)。
- 一根带分叉的树(例如根节点
0连到4,4上面分出一条长为 \(2\) 的左枝4-5-7和一条长为 \(1\) 的右枝4-6):在节点4处,左枝等价于 \(*2\)、右枝等价于 \(*1\),冒号原理告诉我们可以把交汇在节点4的两枝合并成一根长为 \(2 \oplus 1 = 3\) 的等效竹竿!再加上根部主干0-4这一节,整棵树的 SG 值等于 \(3 + 1 = 4\)!
如果地面上同时插着一根长为 \(3\) 的竹竿和上面那棵 SG \(= 4\) 的树,整局总 SG 值就是
\(3 \oplus 4 = 7 \neq
0\)(先手必胜:只需把树里能降到 SG \(= 3\) 的那条边砍掉——例如把
0-4 上方节点 4 里的左枝减掉 \(1\) 节即可?算一下:砍掉顶端边
5-7 后,左枝变长 \(1\),节点 4 变成
\(1 \oplus 1 =
0\),整棵树变成 \(0 + 1 =
1\);而砍掉 4-6 后,节点 4
只剩长为 \(2\)
的左枝,整棵树变成 \(2 + 1 =
3\),与竹竿 \(3\)
完美异或归零!)。
四、可复现实验:Python 通用 SG 计算器
完整验证与绘图脚本见仓库文章同目录的
sg_lab.py,核心 \(\operatorname{mex}\)
与拆堆实现不到 20 行:
def mex(values: set[int]) -> int:
m = 0
while m in values:
m += 1
return m
def sg_kayles(limit: int) -> list[int]:
"""Kayles: 打倒 1 个瓶子或 2 个相邻瓶子,把一排劈成左右两段。"""
g = [0] * (limit + 1)
for n in range(1, limit + 1):
reach = set()
for i in range(n):
reach.add(g[i] ^ g[n - 1 - i]) # 打倒第 i 个
for i in range(n - 1):
reach.add(g[i] ^ g[n - 2 - i]) # 打倒第 i 和 i+1 个
g[n] = mex(reach)
return g运行
python post/combinatorial-games/03-sprague-grundy/sg_lab.py
的真实输出片段(经删减):
=== 1. Subtraction Games ===
S=(1, 3, 4): g(0..20)=[0, 1, 0, 1, 2, 3, 2, 0, 1, 0, 1, 2, 3, 2, 0, 1, 0, 1, 2, 3, 2], period=(0, 7)
S=(1, 4, 5): g(0..20)=[0, 1, 0, 1, 2, 3, 2, 3, 0, 1, 0, 1, 2, 3, 2, 3, 0, 1, 0, 1, 2], period=(0, 8)
=== 2. Splitting Games ===
Lasker's Nim g(0..20): [0, 1, 2, 4, 3, 5, 6, 8, 7, 9, 10, 12, 11, 13, 14, 16, 15, 17, 18, 20, 19]
Kayles period: (71, 12)
Grundy's Game g(0..25): [0, 0, 0, 1, 0, 2, 1, 0, 2, 1, 0, 2, 1, 3, 2, 1, 3, 2, 4, 3, 0, 4, 3, 0, 4, 3]
五、课后练习(检验你是否真正掌握 SG 降维)
练习 1(基础):三堆减法博弈 \(S = \{1, 3, 4\}\)
每堆每次只能拿 \(1\)、\(3\) 或 \(4\) 颗石子。
- (a) 局面 \((5, 8, 11)\) 谁必胜?
- (b) 局面 \((5, 8, 12)\) 谁必胜?写出全部必胜第一步。
参考解答与思路(先独立推导再展开)
查前文周期表(周期 \(7\):[0, 1, 0, 1, 2, 3, 2]):
- (a) \((5, 8,
11) \bmod 7 = (5, 1, 4)\),对应 SG 值为 \((3, 1, 2)\)。
异或和 \(= 3 \oplus 1 \oplus 2 = 0\),因此是 \(\mathcal{P}\) 态(后手必胜)! - (b) \((5, 8,
12) \bmod 7 = (5, 1, 5)\),对应 SG 值为 \((3, 1, 3)\)。
异或和 \(S = 3 \oplus 1 \oplus 3 = 1 \neq 0\),先手必胜。需要把某一堆的 SG 值异或 \(1\)(且必须通过合法的减 \(1/3/4\) 实现):- 第 1 堆 \(5\)(\(g=3\))需要目标 SG \(= 3 \oplus 1 = 2\):拿走 \(1\) 颗变 \(4\)(\(g(4)=2\)),合法!
- 第 2 堆 \(8\)(\(g=1\))需要目标 SG \(= 1 \oplus 1 = 0\):拿走 \(1\) 颗变 \(7\)(\(g(7)=0\)),合法!
- 第 3 堆 \(12\)(\(g=3\))需要目标 SG \(= 3 \oplus 1 = 2\):拿走
\(1\) 颗变
\(11\)(\(g(11)=2\)),合法!
共 \(3\) 种必胜步(注意检验:减 \(3\) 或 \(4\) 均无法击中所需目标 SG)。
练习 2(拆堆):Lasker’s Nim 实战
在 Lasker’s Nim(可拿任意颗,或把一堆拆成两非空堆)中,当前局面为 \((3, 4, 6)\)。先手必胜还是后手必胜?如果是先手,应该拿石子还是拆堆?
参考解答与思路(先独立推导再展开)
由 Lasker’s Nim 公式(\(4k+3\) 与 \(4k+4\) 互换):
- \(g(3) = 4\)
- \(g(4) = 3\)
- \(g(6) = 6\)
异或和 \(S = 4 \oplus 3 \oplus
6 = 7 \oplus 6 = 1 \neq
0\),先手必胜。
检查三堆的目标 SG 值(当前 SG 异或 \(1\)):
- 堆 \(3\)(\(g=4\))目标为 \(4 \oplus 1 = 5\):拿或拆均无法到达 \(5\)(可达 \(\{0,1,2,3\}\));
- 堆 \(4\)(\(g=3\))目标为 \(3 \oplus 1 = 2\):直接从堆 \(4\) 拿走 \(2\) 颗石子变成 \(2\)(因为 \(g(2) = 2\)),新局面 \((3, 2, 6)\) 的 SG 异或 \(= 4 \oplus 2 \oplus 6 = 0\)!
- 堆 \(6\)(\(g=6\))目标为 \(6 \oplus 1 = 7\):拆堆最大只能拆出 \((3,3) \to 0\)、\((2,4) \to 1\)、\((1,5) \to 4\),拿石子最大到 \(5\),均达不到 \(7\)。
因此唯一必胜步是:不拆堆,从第 2 堆 \(4\) 里拿走 \(2\) 颗!
练习 3(拆堆):两排 Kayles 瓶子
桌上有两排保龄球瓶,长度分别为 \(5\) 和 \(7\)。每步可打倒任意 \(1\) 个或相邻 \(2\) 个瓶子。已知 Kayles 的小规模 SG 表为 \(g(0\dots 7) = [0, 1, 2, 3, 1, 4, 3, 2]\)。请问谁必胜?给出至少两种必胜第一步(分别动第 1 排和动第 2 排)。
参考解答与思路(先独立推导再展开)
查表:\(g(5) = 4\),\(g(7) = 2\),总异或 \(= 4 \oplus 2 = 6 \neq 0\),先手必胜。
- 最直觉的动第 2 排招式:把 \(7\)
这一排最左端(或最右端)的相邻 \(2\) 个瓶子一起打倒,留下
(0, 5)!此时桌面变成两排对称的(5, 5),\(4 \oplus 4 = 0\),后续直接镜像即可! - 动第 1 排的巧手:我们需要把长度为 \(5\) 的排变成 SG \(= g(7) = 2\)。检查打倒第 \(2\) 个瓶子(0-indexed 为
1),把 \(5\) 拆成(1, 3),其 SG 异或 \(= g(1) \oplus g(3) = 1 \oplus 3 = 2\),完美匹配 \(g(7) = 2\)!(对称地,打倒第 \(4\) 个瓶子拆成(3, 1)同样必胜。)
练习 4(开放问题体验):Grundy’s Game 手算
在 Grundy’s Game(每次把一堆拆成两堆数量不相等的非空堆)中,利用正文给出的前 \(11\) 项 \(g(0\dots 10) = [0, 0, 0, 1, 0, 2, 1, 0, 2, 1, 0]\):
- (a) 单堆 \(n = 10\) 谁必胜?
- (b) 两堆 \((6, 8)\) 谁必胜?写出必胜拆法。
参考解答与思路(先独立推导再展开)
- (a) 查表 \(g(10) = 0\),因此单堆 \(10\) 是 \(\mathcal{P}\) 态(后手必胜)。(验算:\(10\) 只能拆成 \((1,9)\to 0\oplus 1=1\)、\((2,8)\to 0\oplus 2=2\)、\((3,7)\to 1\oplus 0=1\)、\((4,6)\to 0\oplus 1=1\),全不含 \(0\)!)
- (b) \(g(6) = 1\),\(g(8) = 2\),总异或 \(= 1 \oplus 2 = 3 \neq 0\),先手必胜。只需把 \(8\) 拆成 \((2, 6)\):因为 \(g(2) = 0\) 且 \(g(6) = 1\),拆后桌面变成 \((2, 6, 6)\),总 SG \(= 0 \oplus 1 \oplus 1 = 0\)(而且 \(2\) 已经是个死堆,剩下两堆完全对称的 \(6\),后手无解!)。
练习 5(无限取法集合):只能拿 \(2\) 的幂次颗石子
单堆或多堆石子,每次只能从某一堆拿走 \(2^k\) 颗石子(即 \(S = \{1, 2, 4, 8, 16, \dots\}\))。猜想并证明单堆的 SG 公式 \(g(n)\)。
参考解答与思路(先独立推导再展开)
先手算前 \(7\) 项:
- \(g(0) = 0\)
- \(g(1) = \operatorname{mex}\{g(0)\} = 1\)
- \(g(2) = \operatorname{mex}\{g(1), g(0)\} = 2\)
- \(g(3) = \operatorname{mex}\{g(2), g(1)\} = \operatorname{mex}\{2, 1\} = 0\)(注意不能拿 \(3\)!)
- \(g(4) = \operatorname{mex}\{g(3), g(2), g(0)\} = \operatorname{mex}\{0, 2, 0\} = 1\)
- \(g(5) = \operatorname{mex}\{g(4), g(3), g(1)\} = \operatorname{mex}\{1, 0, 1\} = 2\)
- \(g(6) = \operatorname{mex}\{g(5), g(4), g(2)\} = \operatorname{mex}\{2, 1, 2\} = 0\)
猜想 \(g(n) = n \bmod 3\)!用数学归纳法三行秒证:
- 任何 \(2^k \not\equiv 0 \pmod 3\)(因为 \(2^k \bmod 3 \in \{1, 2\}\),偶数次幂余 \(1\),奇数次幂余 \(2\))。
- 因此从 \(n\) 减去 \(2^k\) 得到的任何后继 \(n - 2^k\),其模 \(3\) 余数永远不等于 \(n \bmod 3\)!
- 当 \(n \bmod 3 = 0\) 时,后继全是 \(1\) 或 \(2\),故 \(\operatorname{mex} = 0\);当 \(n \bmod 3 = 1\) 时,\(n - 1 \equiv 0\) 可达 \(0\) 且无法达 \(1\),故 \(\operatorname{mex} = 1\);当 \(n \bmod 3 = 2\) 时,\(n - 2 \equiv 0\) 且 \(n - 1 \equiv 1\) 均可达而无法达 \(2\),故 \(\operatorname{mex} = 2\)。证毕!
练习 6(树形砍边):Green Hackenbush 冒号原理
地面根点 0 上长出三棵绿色树枝:
- 第一枝是长为 \(2\)
的竹竿
0-1-2; - 第二枝是个 Y 字形:
0-3,节点3分出两条单边3-4和3-5; - 第三枝是
0-6,节点6分出一条长为 \(2\) 的左枝6-7-8和一条长为 \(1\) 的右枝6-9。
求整片森林的总 SG 值,并判断谁必胜。
参考解答与思路(先独立推导再展开)
按冒号原理 \(g(u) = \bigoplus (g(c) + 1)\) 逐枝计算:
- 第 1 枝
0-1-2:长为 \(2\) 的链 \(\implies \text{SG}_1 = 2\); - 第 2 枝 Y 字形:叶子 \(g(4) =
g(5) = 0\),故 \(g(3) =
(0+1) \oplus (0+1) = 1 \oplus 1 = 0\),加上边
0-3得 \(\text{SG}_2 = g(3) + 1 = 1\); - 第 3 枝:\(g(8)=0 \implies
g(7)=1\),\(g(9)=0\),故 \(g(6) = (1+1) \oplus (0+1) = 2 \oplus 1
= 3\),加上边
0-6得 \(\text{SG}_3 = g(6) + 1 = 4\)。
整片森林总 SG 值 \(= 2 \oplus 1
\oplus 4 = 7 \neq
0\),先手必胜!(比如直接把第 3
枝节点 6 下方的整棵子树砍成等价于 \(3\) 的状态:只需砍掉边
6-9,节点 6 变 \(2\),第 3 枝变 \(2+1=3\),此时三枝为 \(2 \oplus 1 \oplus 3 =
0\)!)
参考资料
- Sprague, R. P. (1935–1936). Über mathematische Kampfspiele. Tôhoku Mathematical Journal, 41, 438–444.
- Grundy, P. M. (1939). Mathematics and games. Eureka, 2, 6–8.
- Guy, R. K., & Smith, C. A. B. (1956). The G-values of various games. Proceedings of the Cambridge Philosophical Society, 52(3), 514–526.
- Berlekamp, E. R., Conway, J. H., & Guy, R. K. (1982). Winning Ways for Your Mathematical Plays (Vol. 1, Ch. 7 & Ch. 4). Academic Press.
- 仓库文章同目录的
sg_lab.py:SG 表、拆堆博弈、周期探测、Green Hackenbush 核验与图 3 重绘脚本。
学会了 SG 定理,你已经能碾压绝大多数正常规则小游戏了——但对手接下来一定会使出更阴的招:改判“拿最后一颗输”、让石子在台阶上流动、允许两堆同时拿、或者把取石子上限和上一步绑定。下一篇我们逐一拆招:04|那些专门坑人的变种:Anti-Nim、阶梯 Nim、威佐夫与斐波那契。
源码下载
本文相关源码已整理,共 1 个文件。
文章导航
读完这篇,下一步读什么
优先读同系列或同问题的下一篇,把单篇消费变成主题集群。
【组合博弈】04|那些专门坑人的变种:Anti-Nim、阶梯 Nim、威佐夫与斐波那契
对手发现你懂异或后最爱改的五种阴招:拿最后一颗算输(Anti-Nim 与 Misere Kayles 反例)、阶梯移硬币、两堆同步取(威佐夫黄金分割)、动态 2 倍上限(斐波那契 Zeckendorf)与翻硬币游戏,附暴力 DP 全量核验与 6 道练习。
【组合博弈】02|Nim 与异或的直觉:为什么二进制按位相加能支配石子堆?
拒绝把 Nim 异或背成黑盒魔法:通过 2 的幂筹码配对直觉证明 Bouton 定理,给出 3 秒牌桌口算必胜步方法,并用同一套不变量一次打通 Poker Nim、Northcott 棋盘与 Moore's Nim_k,附 Python 验证与 6 道练习。
【组合博弈】系列总览:从 Nim 到 Sprague-Grundy,看穿取石子小游戏的必胜法则
系统拆解 Nim 及其经典变种的组合博弈论原理:从 P/N 态倒推、对称模仿、二进制异或配对,到 Sprague-Grundy 定理、Anti-Nim、阶梯 Nim、威佐夫、斐波那契博弈与红蓝 Hackenbush,配套图解、Python 核验脚本与分级练习。
【组合博弈】05|实战反杀手册、综合测验与超越 Nim:不对称博弈与开放问题
沉淀遇到陌生小游戏时的 5 步现场诊断协议,越过公平博弈边界介绍红蓝 Hackenbush 与 Conway 超实数、PSPACE 复杂性及 Grundy's Game 等未解难题,并附 10 道覆盖全系列的闭卷综合测验与 Python 核验脚本。