前四篇我们分别拆解了 P/N 倒推与对称、Nim 二进制筹码与 Moore’s \(\text{Nim}_k\)、Sprague-Grundy 定理 以及 五大高频规则魔改。但真到桌游局或算法面试白板前,对手不会提前剧透“这道题考阶梯 Nim”——他只会抛出一段口头规则。
这篇收官章做三件事:
- 把整套方法论压成一张 5 步现场诊断流程图和一张速查表,让你面对任何陌生小游戏都能在 30 秒内选对锤子。
- 走出 Nim 所在的公平博弈小圈子,看清这套理论的边界:不公平博弈(红蓝 Hackenbush 与超实数)、PSPACE 完全性以及组合博弈论中至今悬而未决的开放问题。
- 提供一套 10 道闭卷综合测验(满分 100 分),独立做完并对完答案,就能确认自己以后不会再被这类小游戏牵着鼻子走。
一、5 步现场诊断协议:遇到陌生小游戏怎么拆?
拿到一条陌生规则,克制住“先试着推演两步”的冲动,严格按下面五关自顶向下排查:
图 1|组合博弈 5 步现场诊断协议。 每一关都在排除一类大陷阱,避免把正常规则的锤子砸到反常规则或不公平规则的钉子上。
- 第一关(看双方权限):是不是公平博弈(Impartial)?
如果同一局面下,先手和后手的可选动作不同(比如红蓝棋子各走各的、横放多米诺 vs 竖放多米诺),立刻跳出 Nim / SG 框架,进入不公平博弈(见本文第二节)。 - 第二关(看终局胜负):最后走一步的人是赢(Normal)还是输(Misère)?
如果是 Misère Play,切记不能盲套普通 SG 值或镜像模仿!只有纯 Anti-Nim(或单堆巴什等温顺博弈)能用“中局照常、残局改留奇数个1”的 SJ 法则;一旦带拆堆或复杂图转移,必须手算小状态 DP 或查反常商结构。 - 第三关(看棋盘几何):有没有一键秒杀的对称配对或策略盗取?
先花 5 秒扫一眼棋盘有没有中心对称(圆桌硬币、环形排布)、两半镜像(等长双堆、条带劈中点)或可逆抵消(加石子、后退步、偶数台阶)。能一招对称锁死就绝不写递推式。 - 第四关(看子游戏耦合):能否拆成多个互不干扰的独立组件(析取和)?
- 若独立(每步只改一个组件,或把一个组件劈成两个独立子组件):直接上 Sprague-Grundy + XOR 核武器!在草稿纸上用 \(\operatorname{mex}\) 写出前 \(12\text{–}16\) 项观察公式或周期(牢记 Kayles 前周期 \(71\) 的教训,要靠归纳证明而不是拍脑袋猜)。
- 若耦合(一次动多堆、两堆同步减、上限依赖上一步):立刻检索经典不变量家族(Moore 按位模 \(k+1\)、威佐夫 Beatty 射线、斐波那契 Zeckendorf 分解),否则写小规模记忆化 DP 找 \(\mathcal{P}\) 态规律。
- 第五关(动手验证与找具体招式):
判定 \(\mathcal{N}\) 态之后,不要只停在“先手赢”,务必核实找出来的目标步满足所有合法性约束(例如普通 Nim 要挑含 \(S\) 最高位的堆确保 \(a_i \oplus S < a_i\);Lasker’s Nim 记得检查拆堆分支;威佐夫要核对减大堆、减小堆、双堆同减三条射线)。
全系列常见小游戏速查表
| 规则特征 | 代表游戏 | 必胜判定(\(\mathcal{P}\) 态 = 后手胜) |
|---|---|---|
| 单堆每次取 \(1\text{–}k\) 颗 | 巴什博弈 | \(n \equiv 0 \pmod{k+1}\) |
| 单堆每次取集合 \(S\) | 减法博弈 | 倒推 \(\mathcal{P}/\mathcal{N}\) 必进入周期 |
| 多堆单堆任取 | 标准 Nim / Poker Nim / Northcott | \(a_1 \oplus \dots \oplus a_m = 0\) |
| 多堆每次最多动 \(k\) 堆 | Moore’s \(\text{Nim}_k\) | 二进制每一列之和均被 \(k+1\) 整除 |
| 多组件任意正常公平博弈 | 减法组合 / Lasker / Kayles / Green Hackenbush | \(g(G_1) \oplus \dots \oplus g(G_m) = 0\) |
| 多堆单堆任取,拿最后一颗输 | Anti-Nim(Misère Nim) | 全 \(\le 1\) 时有奇数个
1;否则异或为 \(0\) |
| 台阶上硬币每次左推一级 | 阶梯 Nim / 一维左移硬币 | 仅奇数号台阶异或为 \(0\) |
| 两堆单取或双堆同取 | 威佐夫博弈 | \(a \le b\) 时 \(a = \lfloor (b-a)\phi \rfloor\) |
| 单堆上限为上一步的 \(2\) 倍 | 斐波那契博弈 | \(n\) 本身是斐波那契数(否则取最小 Zeckendorf 项) |
| 翻转正面硬币及左侧任一枚 | Turning Turtles | 所有正面硬币编号(1-indexed)的异或为 \(0\) |
二、超越 Nim:当双方规则不同——红蓝 Hackenbush 与超实数
如果游戏打破了“公平性”,例如桌上插着蓝边和红边:左方(Left,蓝方)只能砍蓝边,右方(Right,红方)只能砍红边,同时还可能混着双方都能砍的绿边(砍断任何边后,不与地面连通的部分全部掉落)。这就是著名的 红蓝绿 Hackenbush。
一旦进入不公平博弈(Partizan Games),只有 \(\mathcal{P}/\mathcal{N}\) 两种胜负标签彻底不够用了,因为局面可能天然偏袒某一方。每个局面必然落入四种结果类(Outcome Classes)之一:
- \(\mathcal{L}\)(正值,\(G > 0\)):无论谁先走,左方(蓝方)必胜;
- \(\mathcal{R}\)(负值,\(G < 0\)):无论谁先走,右方(红方)必胜;
- \(\mathcal{P}\)(零值,\(G = 0\)):谁后走谁赢(与公平博弈的 \(\mathcal{P}\) 一致);
- \(\mathcal{N}\)(模糊值,\(G \parallel 0\),与 \(0\) 不可比):谁先走谁赢(与公平博弈的 \(\mathcal{N}\) 一致)。
John Horton Conway 在 1976 年的奠基著作 On Numbers and Games(以及随后与 Berlekamp、Guy 合著的 Winning Ways, 1982)中做了一件令整个数学界震惊的事:他把任意不公平博弈写成递归对
\[ G = \{ G^L \mid G^R \}, \]
其中 \(G^L\) 是左方走一步能到达的局面集合,\(G^R\) 是右方走一步能到达的局面集合。令人瞠目结舌的是,这套纯粹从下棋规则长出来的代数结构,竟然自然衍生出了全部实数、二进有理数、无穷大、无穷小(超实数 Surreal Numbers),并且把 Nimber \(*n\) 稳稳囊括进同一套加法体系里!
图 2|红蓝绿 Hackenbush 与超实数加法。
地面上一根纯蓝边 B 记作 \(\{0 \mid \} =
+1\)(代表蓝方净赚 \(1\) 步免费操作);纯红边
R 记作 \(\{\mid 0\} =
-1\);下蓝上红的 BR 中,蓝方砍底变 \(0\)、红方砍顶留蓝变 \(+1\),故 BR \(= \{0 \mid 1\} =
+\frac{1}{2}\)!
检验一下这个“半步优势(\(+\frac{1}{2}\))”是不是硬凑出来的比喻:把两根
BR(各值 \(+\frac{1}{2}\))和一根
R(值 \(-1\))摆在同一张桌上做析取和:
\[ \text{BR} + \text{BR} + \text{R} = \frac{1}{2} + \frac{1}{2} - 1 = 0. \]
仓库文章同目录的暴力 DP 脚本 exam_verify.py
实测结果:Combo ('BR', 'BR', 'R'): sum=0, DP outcome=Prev wins (0)!无论是蓝方先手还是红方先手,先走的人必输——两根
BR 恰好精准抵消掉红方一整步的优势!
再往这张和为 \(0\)
的桌子上插一根双方都能砍的绿边
G(记作 \(\{0 \mid 0\} = *1\)):
\[ \text{BR} + \text{BR} + \text{R} + \text{G} = 0 + *1 = *1 \parallel 0. \]
结果立刻从“后手胜”翻成“先手胜”(因为无论蓝方还是红方先走,直接砍掉那根绿边,就把精确等于 \(0\) 的残局丢给对方了!)。而如果在 \(*1\) 上加上任何正数(哪怕是小到 \(1/1024\) 的蓝方微弱优势),蓝方都会必胜——换言之,Nimber \(*1\) 是一个既不大于 \(0\)、又不小于 \(0\)、却夹在所有正负实数之间的一阶模糊无穷小(Infinitesimal)!
这就是整个组合博弈论的宏大谱系:
Bouton (1901) Nim 异或 -> Sprague (1935) / Grundy (1939) 公平博弈压缩为 *n
-> Grundy-Smith (1956) & Plambeck (2005) 反常商代数
-> Conway (1976) & Berlekamp-Conway-Guy (1982) 不公平博弈与超实数 {G^L | G^R}
三、为什么不是所有小游戏都有简单公式?复杂性与开放问题
学完前面这些优雅的公式,很容易产生一种错觉:“是不是只要数学功底够深,任何有限双人完全信息小游戏都能推出像 Nim 异或那样的 \(O(n)\) 闭式解?”
答案是否定的。计算复杂性理论在 1978 年就为组合博弈论划下了一道坚硬的铁幕。
复杂性边界:从 \(O(n)\) 到 PSPACE 完全
Thomas J. Schaefer 在 1978 年发表于 Journal of Computer and System Sciences 的里程碑论文 On the complexity of some two-person perfect-information games 中证明:即便是最简洁、完全公平、正常规则的图上小游戏——广义地理游戏(Generalized Geography)(在有向图上沿边移动一枚棋子,不能重复经过已访问顶点,无路可走者输)——判定先手是否必胜也是 PSPACE 完全(PSPACE-complete) 问题!
请分清两个容易混淆的事实:
- 数学存在性:广义地理游戏有限、公平、无平局,因此它完全满足 Zermelo 定理和 Sprague-Grundy 定理——每个状态确实都有唯一确定的 SG 值;
- 计算可行性:状态里必须记录“哪些顶点已经被访问过”,整个状态 DAG 的节点数高达 \(O(|V| \cdot 2^{|V|})\) 指数级!除非 \(\mathrm{P} = \mathrm{PSPACE}\),否则不存在多项式时间算法能算出一般图上的 SG 值。
类似地,真实棋类往往比这更庞大:跳棋(Checkers)由 Jonathan Schaeffer 团队在 Science(2007, Checkers Is Solved)上历经 18 年弱解为“双方最优下法必和”,依赖高达 \(3.9 \times 10^{13}\) 状态的残局数据库与启发式搜索剪枝,而不是靠一条闭式公式。
组合博弈论中三个至今未解的开放问题
即便回到规则只有一句话的极简取石子/画线小游戏,数学界仍有大量悬而未决的难题(完整清单见 Richard Guy & Richard Nowakowski 持续维护的 Unsolved Problems in Combinatorial Games 以及 Aaron Siegel 的标准教材 Combinatorial Game Theory, AMS 2013):
- Grundy’s Game 的 SG
序列到底是不是最终周期的?
如 第 03 篇 所述,把一堆石子拆成两堆不等非空堆的 Grundy’s Game,被 Winning Ways 猜想最终进入周期。Achim Flammenkamp 已将计算推进至超过 \(2^{35}\)(约 \(3.43 \times 10^{10}\))项,仍未发现周期,且稀疏异常值仍在不规则出现。 - \(3 \times n\)
Chomp 的显式必胜步公式是什么?
第 01 篇 用策略盗取三行就证明了任意 \(m \times n > 1\) 的 Chomp 先手必胜,但连 \(3 \times n\) 三行巧克力的必胜着法结构至今没有封闭公式(Doron Zeilberger 2001 给出了渐近形态猜想与自动机分析,仍未完全闭合)。 - 一般反常八进制游戏(Misère Octal
Games)的判定边界:
Plambeck(2005)的 Misère Quotients 成功驯服了一批具有有限商幺半群的狂野反常游戏,但像 Misère Kayles 的兄弟游戏或诸多八进制规则(如0.6)产生的是无限商代数,目前仍缺乏统一算法判定其任意和局的胜负。
四、全系列综合通关测验(10 题,共 100 分)
关掉笔记,拿一张空白草稿纸独立完成下面 10 道题,再展开
<details> 核对思路并给自己打分(70
分及格,85 分以上说明你已经具备“牌桌秒杀 +
面试抗压”的完整反杀能力)。所有题目均已由仓库同目录的
exam_verify.py 核验。
第一档:桌游秒杀(每题 8 分,共 32 分)
第 1 题(8 分):快算巴什变体
桌上 \(50\) 颗石子,每人每次取 \(1\) 到 \(6\) 颗,取走最后一颗者胜。先手还是后手必胜?若是先手,第一步拿几颗?
参考解答(第 1 题)
周期 \(k + 1 =
7\),\(50 = 7 \times 7 +
1\),余数为 \(1 \neq
0\)。
先手必胜,第一步拿走 \(1\) 颗(留下 \(49\) 颗进入 \(\mathcal{P}\)
态),此后每轮与对手凑齐 \(7\) 颗。
第 2 题(8 分):四堆标准 Nim 实战
标准 Nim 局面 (9, 12, 15, 22)。算清异或和
\(S\),判断胜负,并给出全部必胜第一步。
参考解答(第 2 题)
二进制拆分:
- \(9 = (01001)_2\)
- \(12 = (01100)_2\)
- \(15 = (01111)_2\)
- \(22 = (10110)_2\)
异或和 \(S = 9 \oplus 12 \oplus
15 \oplus 22 = (11100)_2 = 28 \neq
0\),先手必胜。
最高 1 位是 16,只有第 4 堆 \(22\) 包含位
16。目标值 \(22
\oplus 28 = (10110)_2 \oplus (11100)_2 = (01010)_2 =
10\)。
唯一必胜步:将 22 减到
10(拿走 \(12\) 颗),留下
(9, 12, 15, 10)。
第 3 题(8 分):Anti-Nim 双局面辨析
反常 Nim(拿走最后一颗石子者输),分别判断下面两个局面的胜负,若是先手胜则写出必胜第一步:
- (a)
(1, 1, 4, 4) - (b)
(1, 1, 1, 4)
参考解答(第 3 题)
- (a)
(1, 1, 4, 4):存在 \(\ge 2\) 堆大于 \(1\),且异或和 \(1 \oplus 1 \oplus 4 \oplus 4 = 0\),因此是 \(\mathcal{P}\) 态(后手必胜)! - (b)
(1, 1, 1, 4):恰好只有一堆大于 \(1\),进入唯一残局分叉点!已有 \(3\) 个1(奇数),因此先手必胜,只需把4全部清空为0,留下(1, 1, 1, 0)(奇数个1)逼死对手!
第 4 题(8 分):三堆减法博弈
每堆每次只能拿 \(S = \{1, 2,
5\}\) 颗石子,正常规则。局面为
(6, 9, 13),求各堆 SG
值、总异或和及至少两种必胜第一步。
参考解答(第 4 题)
先求单堆 SG 表:\(g(0)=0,
g(1)=1, g(2)=2\);\(g(3) =
\operatorname{mex}\{g(2), g(1)\} = 0\);\(g(4) = \operatorname{mex}\{g(3),
g(2)\} = 1\);\(g(5) =
\operatorname{mex}\{g(4), g(3), g(0)\} =
2\)……归纳发现周期为 \(3\),\(g(n) = n \bmod
3\)(因为 \(1, 2,
5 \not\equiv 0 \pmod 3\))!
查 (6, 9, 13) 的 SG
值:[0, 0, 1],总异或 \(= 1 \neq
0\),先手必胜!
共有 5
种必胜第一步(任答出两种即满分):
- 动第 3 堆(降 SG
1 -> 0):13 -> 12(拿 \(1\) 颗); - 或者动前两堆(升 SG
0 -> 1!):6 -> 4(拿 \(2\) 颗)、6 -> 1(拿 \(5\) 颗)、9 -> 7(拿 \(2\) 颗)、9 -> 4(拿 \(5\) 颗)!(注意:虽然单堆 SG 变大了,但在多堆和里使总异或从 \(1\) 变成 \(0\),完全合法!)
第二档:规则魔改(每题 10 分,共 40 分)
第 5 题(10 分):阶梯 Nim 实战
5 级阶梯 Nim,台阶 \(1\text{–}5\) 上的硬币数分别为
(5, 12, 7, 100, 3)。谁必胜?写出全部必胜第一步。
参考解答(第 5 题)
忽略偶数阶 12 和
100,只看奇数阶 (5, 7, 3)。
异或和 \(S = 5 \oplus 7 \oplus 3 =
2 \oplus 3 = 1 \neq
0\),先手必胜!
\(S = 1\) 只有最低位为
1,三个奇数阶 5, 7, 3
都是奇数(全含位 1),因此有 3
种必胜第一步(各自往下推 \(1\) 枚硬币即可):
- 从台阶 1 推 \(1\)
枚到地板 0(
5 -> 4); - 从台阶 3 推 \(1\)
枚到台阶 2(
7 -> 6); - 从台阶 5 推 \(1\)
枚到台阶 4(
3 -> 2)。
第 6 题(10 分):威佐夫博弈精准找冷态
威佐夫博弈局面为 (11, 17)(已知 \(\phi \approx
1.618034\))。判断胜负并找出必胜第一步。
参考解答(第 6 题)
差值 \(k = 17 - 11 =
6\)。计算 \(a_6 = \lfloor 6
\times 1.618034 \rfloor = \lfloor 9.708 \rfloor =
9\),对应冷态为 \((9, 9 +
6) = (9, 15)\)。
因为当前较小堆 \(11 >
9\),故 (11, 17) 是 \(\mathcal{N}\)
态(先手必胜)!
唯一必胜步:沿对角线从两堆同时拿走
\(11 - 9 = 2\)
颗,直达冷态
(9, 15)!(也可顺手验算单堆减法:\(11\) 在 \(k=7\) 号冷态 \((11, 18)\) 中而 \(17 < 18\) 够不到;\(17\)
不在任何小冷态左/右端:冷态表 \((0,0),(1,2),(3,5),(4,7),(6,10),(8,13),(9,15),(11,18)\),所以
\((9, 15)\)
确实是唯一解!)
第 7 题(10 分):斐波那契博弈开局
一堆 \(n = 40\) 颗石子的斐波那契博弈(首步不可全拿,此后不超过上一步 \(2\) 倍)。先手必胜还是后手必胜?如果是先手胜,第一步拿几颗?如果对手接着拿了 \(2\) 颗,你的第二步该拿几颗?
参考解答(第 7 题)
斐波那契数列:\(1, 2, 3, 5, 8,
13, 21, 34, 55, \dots\)。
贪心写 \(40\) 的 Zeckendorf
分解:\(40 = 34 + 5 +
1\)(各项互不相邻,不是单个斐波那契数)。
- 先手必胜,第一步拿走最小项 \(1\) 颗(剩下 \(39 = 34 + 5\),对手上限 \(2 \times 1 = 2 < 5\))。
- 如果对手接着拿走 \(2\) 颗,剩下 \(37 = 34 + 3\)(此时对手把 \(5\)-区块打成了 \(3\),你的上限是 \(2 \times 2 = 4 \ge 3\))!把 \(37\) 写成 \(34 + 3\),最小 Zeckendorf 项是 \(3\) 颗,正好在你的上限 \(4\) 以内——你直接拿走 \(3\) 颗,精准把 \(34\)(斐波那契数!)留给对手,且对手上限 \(6 < 34\),稳赢!
第 8 题(10 分):Lasker’s Nim 逼出拆堆杀招
在 Lasker’s Nim(每步可从一堆拿走至少 \(1\)
颗,或把一堆拆成两非空堆)中,当前局面为
(2, 5, 7)。 提示:回忆 第 03
篇 中 Lasker’s Nim 的公式(\(4k+3\) 与 \(4k+4\)
互换)。请问先手能不能靠“只拿石子不拆堆”获胜?写出全部必胜第一步!
参考解答(第 8 题)
查 Lasker’s Nim SG 值:\(g(0..8) = [0, 1, 2, 4, 3, 5, 6, 8,
7]\)。
所以 (2, 5, 7) 的 SG 值为
[2, 5, 8],总异或 \(S
= 2 \oplus 5 \oplus 8 = 15 \neq
0\),先手必胜!
最高位是 8,只有第 3 堆 7(\(g(7) = 8\))包含位
8。我们需要把堆 7 变成目标 SG
\(= 8 \oplus 15 = 7\)!
- 只拿石子行不行?绝对不行! 从
7拿石子只能变成0..6,它们的 SG 值集合是 \(\{0, 1, 2, 4, 3, 5, 6\}\)——刚好缺了 \(7\)! - 必须拆堆! 检查把
7劈成两堆的所有三种拆法:7 -> 1 + 6:\(g(1) \oplus g(6) = 1 \oplus 6 = 7\)(胜!)7 -> 2 + 5:\(g(2) \oplus g(5) = 2 \oplus 5 = 7\)(胜!桌面变成对称的(2, 2, 5, 5)!)7 -> 3 + 4:\(g(3) \oplus g(4) = 4 \oplus 3 = 7\)(胜!)
这道题完美展示了为什么拆堆动作能制造出“纯拿石子绝无可能抵达”的 SG 值。
第三档:对称构造与超越 Nim(每题 14 分,共 28 分)
第 9 题(14 分):环形 Kayles(Ring Kayles)秒杀证明
把 \(n = 10\)
枚硬币首尾相连摆成一个圆环(\(n \ge
3\))。两人轮流拿走圆环上任意 \(1\) 枚硬币,或任意 \(2\)
枚相邻硬币,拿走最后一枚者胜。
如果朋友让你选先手或后手,你该选哪边?请给出对任意
\(n \ge 3\)
都成立的通用必胜策略(不需要背任何 Kayles SG 表!)。
参考解答(第 9 题)
果断选择后手,对任意 \(n \ge 3\) 后手 100%
必胜!
思路(纯几何对称破局,完美呼应第 01 篇练习 5):
- 无论先手第 1 步在圆环上拿走 \(1\) 枚还是相邻 \(2\) 枚硬币,原本封闭的圆环都会被咬开一个缺口,瞬间退化成一条直线排列的 \(m\) 枚硬币(其中 \(m = n - 1 \ge 2\) 或 \(m = n - 2 \ge 1\))。
- 轮到后手面对一条长为 \(m\) 的直线,直接使出 第
01 篇练习 5 的必杀技:
- 若 \(m\) 为奇数,拿走直线最正中那 \(1\) 枚;
- 若 \(m\) 为偶数,拿走直线最正中相邻的 \(2\) 枚。
- 这一刀把直线劈成左右两段完全等长、互不干扰的独立直线!此后无论先手在左段拿什么,后手都在右段做完全镜像操作,稳收最后一枚!
(以 \(n = 10\)
为例:若先手拿 \(1\)
枚剩长为 \(9\)
的线,后手拿正中第 \(5\)
枚拆成 (4, 4);若先手拿 \(2\) 枚剩长为 \(8\) 的线,后手拿正中 \(2\) 枚拆成
(3, 3)。)
第 10 题(14 分):红蓝绿 Hackenbush 超实数综合判断
地面上插着 5
根独立的红蓝枝条:BR、BR、B、R、R(字符顺序从地面向上,B
为蓝方专砍,R 为红方专砍)。
- (a) 计算这 5 根枝条的总超实数值,并判断谁必胜;
- (b) 如果在这 5
根枝条旁边再插一根双方都能砍的单节绿边
G(值 \(*1\)),胜负结论如何变化?先手第一步该砍哪条边?
参考解答(第 10 题)
- (a) 逐根赋值:
BR\(= +\frac{1}{2}\),B\(= +1\),R\(= -1\)。
总值 \(= \frac{1}{2} + \frac{1}{2} + 1 - 1 - 1 = 0\)。
因为总值严格等于 \(0\),该局面属于 \(\mathcal{P}\) 态(后手必胜)——无论是蓝方先手还是红方先手,先走的人必输! - (b) 加上单节绿边
G后,总值变为 \(0 + *1 = *1 \parallel 0\),属于 \(\mathcal{N}\) 态(先手必胜)!
无论当前轮到蓝方还是红方,第一步直接砍掉那根绿边G,就把精确等于 \(0\) 的残局交给对手,稳操胜券。
考后核验与补漏指南
运行
python post/combinatorial-games/05-field-manual-and-beyond/exam_verify.py
可一键交叉核验第 1–10 题全部结果与 Hackenbush
暴力博弈树结论。若某档失分,按下面对应关系回查即可:
- 第 1、9 题失分 → 回看 01|P/N 态、倒推法与对称模仿
- 第 2 题失分 → 回看 02|Nim 与异或的直觉
- 第 4、8 题失分 → 回看 03|Sprague-Grundy 定理与 mex
- 第 3、5、6、7 题失分 → 回看 04|Anti-Nim、阶梯、威佐夫与斐波那契
参考资料
核心论文
- Schaefer, T. J. (1978). On the complexity of some two-person perfect-information games. Journal of Computer and System Sciences, 16(2), 185–225.
- Plambeck, T. E. (2005). Taming the wild in impartial combinatorial games. Integers, 5, #G5.
- Schaeffer, J., Burch, N., Björnsson, Y., Kishimoto, A., Müller, M., Lake, R., Lu, P., & Sutphen, S. (2007). Checkers is solved. Science, 317(5844), 1518–1522.
经典教材与著作
- Conway, J. H. (1976). On Numbers and Games. Academic Press (2nd ed., A K Peters, 2001).
- Berlekamp, E. R., Conway, J. H., & Guy, R. K. (1982). Winning Ways for Your Mathematical Plays (Vols. 1–4, 2nd ed., A K Peters, 2001–2004).
- Siegel, A. N. (2013). Combinatorial Game Theory. Graduate Studies in Mathematics, Vol. 146, American Mathematical Society.
- 仓库文章同目录的
exam_verify.py:红蓝 Hackenbush 暴力博弈树与全 10 道综合考题核验脚本。
返回 组合博弈系列总览
源码下载
本文相关源码已整理,共 1 个文件。
文章导航
读完这篇,下一步读什么
优先读同系列或同问题的下一篇,把单篇消费变成主题集群。
【组合博弈】04|那些专门坑人的变种:Anti-Nim、阶梯 Nim、威佐夫与斐波那契
对手发现你懂异或后最爱改的五种阴招:拿最后一颗算输(Anti-Nim 与 Misere Kayles 反例)、阶梯移硬币、两堆同步取(威佐夫黄金分割)、动态 2 倍上限(斐波那契 Zeckendorf)与翻硬币游戏,附暴力 DP 全量核验与 6 道练习。
【组合博弈】系列总览:从 Nim 到 Sprague-Grundy,看穿取石子小游戏的必胜法则
系统拆解 Nim 及其经典变种的组合博弈论原理:从 P/N 态倒推、对称模仿、二进制异或配对,到 Sprague-Grundy 定理、Anti-Nim、阶梯 Nim、威佐夫、斐波那契博弈与红蓝 Hackenbush,配套图解、Python 核验脚本与分级练习。
【组合博弈】02|Nim 与异或的直觉:为什么二进制按位相加能支配石子堆?
拒绝把 Nim 异或背成黑盒魔法:通过 2 的幂筹码配对直觉证明 Bouton 定理,给出 3 秒牌桌口算必胜步方法,并用同一套不变量一次打通 Poker Nim、Northcott 棋盘与 Moore's Nim_k,附 Python 验证与 6 道练习。
【组合博弈】03|万能降维武器:Sprague-Grundy 定理与 mex 的真正含义
只要游戏有限、公平且最后一步胜,任意状态都严格等价于一个特定大小的 Nim 堆。本文从博弈和与 mex 定义出发,用图解拆透 SG 等价性证明,通吃多堆减法、拆堆游戏(Lasker's Nim、Kayles)与 Green Hackenbush,附 Python 计算器与 6 道练习。