桌游聚会、算法面试、数学竞赛里经常冒出一类看似无害的取石子小游戏:桌上摆着几堆硬币、棋子或巧克力,两人轮流按规则拿走一部分,谁拿走最后一块就赢(或者谁拿走最后一块就输)。多数人面对这类问题都会掉进同一个陷阱——试图往前推演博弈树(“我拿 2 个,如果他拿 3 个我就……”),三步之后分支爆炸,完全被对手牵着鼻子走;即便背过“Nim 用异或”的口诀,只要对方把规则微调半句(例如“最后拿完的算输”“一次最多拿 3 个”“可以把一堆拆成两堆”“只能往左边移”),口诀立刻失效。
这套系列把这类“欺负人”的双人完全信息小游戏拆成一套 5 步通用工具箱。每篇都提供纸笔手算步骤、暗色图解、可运行的 Python 核验脚本与带折叠详解的练习题,目标是让你在牌桌或白板前不再靠猜,而是直接定位不变量、反手构造必胜步。
系列规模:全 5 篇正文 + 本总览索引。全部数值例题、SG 表、变种公式与课后习题答案均已由各篇附带的 Python 脚本与暴力动态规划交叉验证。
一、这个系列要回答的五个问题
为什么往前想三步就会晕,而高手一眼就能判胜负?
因为博弈树应该从终局倒推而不是从开局前推。只要给每个状态贴上“先手必胜(\(\mathcal{N}\))”或“后手必胜(\(\mathcal{P}\))”两枚标签,再结合对称配对与策略盗取,就能在不展开整棵树的情况下直接定性。回答在 01|胜负的底层逻辑。取石子跟二进制异或(\(\oplus\))到底有什么关系?
Bouton 在 1901 年给出的异或公式并不是凭空降临的巧合:把每一堆石子拆成 \(2^k\) 面值的二进制筹码,异或为 \(0\) 等价于“每种面值的筹码都成双配对”。理解筹码配对后,既能 3 秒内口算必胜步,也能自然推广到一次可动 \(k\) 堆的 Moore’s \(\text{Nim}_k\)(按位模 \(k+1\))。回答在 02|Nim 与异或的直觉。规则一改,异或口诀为什么突然不管用?怎么把千奇百怪的新游戏还原回 Nim?
Sprague(1935)与 Grundy(1939)证明了一个统一结论:只要游戏满足有限、公平、正常规则(最后一步赢),任何单组件状态都严格等价于某一个特定大小的 Nim 堆,其大小就是递归计算的 \(\operatorname{mex}\) 值(SG 值)。多个独立组件拼在一起,直接把各组件 SG 值做异或。回答在 03|万能降维武器:Sprague-Grundy。如果对方故意把规则改刁钻——拿最后一颗算输、棋子只能向左推、两堆同时拿、上限跟上一步挂钩——该怎么拆?
拆解必须先分清“破坏了哪条前提”:Anti-Nim 破坏了正常终局,只在进入全 \(1\) 残局的唯一分叉点改口;阶梯 Nim 用偶数阶“镜像抵消”把一半台阶变透明;威佐夫博弈因两堆耦合落到黄金分割射线(Beatty 定理);斐波那契博弈用 Zeckendorf 分解筑起 \(2\times\) 防火墙。同时用 Misère Kayles 的 \((5,5)\) 反例标明 Anti-Nim 规则何时彻底失效。回答在 04|专门坑人的经典变种。遇到从未见过的新小游戏,按什么顺序排查?公平博弈理论的边界在哪里?
给出一套 5 步现场诊断流程图与 10 道综合通关考题,并把视角推到公平博弈之外:当双方可执行动作不同(不公平博弈,如红蓝 Hackenbush),局面值从 Nimber 跃升为 Conway 的超实数 \(\{G^L \mid G^R\}\);同时梳理 PSPACE 完全性与 Grundy’s Game 周期性等至今未解的开放问题。回答在 05|实战反杀手册、综合测验与超越 Nim。
二、篇目依赖关系与推荐阅读路径
flowchart TD
A["01 P/N States & Symmetry"] --> B["02 Nim & XOR Intuition"]
B --> C["03 Sprague-Grundy & mex"]
C --> D["04 Classic Variants (Misere, Staircase, Wythoff, Fib)"]
A --> D
C --> E["05 Field Manual, Surreals & Capstone Exam"]
D --> E
- 零基础系统通关(推荐,完整 5 篇)
01→02→03→04→05。每篇读完先自己做文末练习再展开答案,最后用第 05 篇的 10 道综合题检验是否真正脱敏。 - 只想速成破局(桌游 / 面试救急,3
篇)
01(P/N 与巴什)→02(Nim 三步口算法)→04(Anti-Nim / 阶梯 / 威佐夫 / 斐波那契速查)。 - 算法竞赛 / 工程实现向(3 篇)
02→03(SG 记忆化、拆堆转异或、周期探测、Green Hackenbush 树)→05(复杂性边界与综合测验)。 - 数学结构与理论延伸(3 篇)
03(SG 等价性构造证明)→04(Misère Kayles 反例与 Plambeck 商代数)→05(红蓝 Hackenbush、超实数与开放问题)。
三、目录与每篇看点
- 系列总览(本文)
- 01|胜负的底层逻辑:P/N
态、倒推法与对称模仿
- 看点:Zermelo 有限决定性定理、有向无环图 P/N
倒推三公理、巴什博弈模 \(k+1\) 陷阱、对称模仿(圆桌硬币
/ 偶数堆)、Chomp 巧克力毒块的非构造性策略盗取证明,附
pn_solver.py与 5 道分级练习。
- 看点:Zermelo 有限决定性定理、有向无环图 P/N
倒推三公理、巴什博弈模 \(k+1\) 陷阱、对称模仿(圆桌硬币
/ 偶数堆)、Chomp 巧克力毒块的非构造性策略盗取证明,附
- 02|Nim
与异或的直觉:为什么二进制按位相加能支配石子堆?
- 看点:把石子堆拆成 \(2^k\) 筹码看穿 Bouton
定理、三步口算必胜招式、Poker
Nim(允许往堆里放石子为何不影响胜负)、Northcott
棋盘等价归约、Moore’s \(\text{Nim}_k\) 的按位模 \(k+1\) 推广,附
nim_verify.py与 6 道练习。
- 看点:把石子堆拆成 \(2^k\) 筹码看穿 Bouton
定理、三步口算必胜招式、Poker
Nim(允许往堆里放石子为何不影响胜负)、Northcott
棋盘等价归约、Moore’s \(\text{Nim}_k\) 的按位模 \(k+1\) 推广,附
- 03|万能降维武器:Sprague-Grundy
定理与 mex 的真正含义
- 看点:博弈和 \(G_1 +
G_2\)、\(\operatorname{mex}\)
的构造意义、为什么允许 SG
值“变大”的走法不会破坏等价性(\(G
+ *g(G) \in \mathcal{P}\)
图解证明)、任意减法集合与周期性、拆堆游戏(Lasker’s
Nim、Kayles 与 pre-period \(=71\))、Green Hackenbush
树(Colon Principle),附
sg_lab.py与 6 道练习。
- 看点:博弈和 \(G_1 +
G_2\)、\(\operatorname{mex}\)
的构造意义、为什么允许 SG
值“变大”的走法不会破坏等价性(\(G
+ *g(G) \in \mathcal{P}\)
图解证明)、任意减法集合与周期性、拆堆游戏(Lasker’s
Nim、Kayles 与 pre-period \(=71\))、Green Hackenbush
树(Colon Principle),附
- 04|那些专门坑人的变种:Anti-Nim、阶梯
Nim、威佐夫与斐波那契
- 看点:Misère Nim 的唯一残局分叉(SJ 定理)与 Misère
Kayles \((5,5)\)
失效反例、阶梯 Nim 偶数阶抵消术、威佐夫博弈与黄金分割 Beatty
射线、斐波那契博弈的 Zeckendorf 分解 \(2\times\)
防火墙、翻硬币游戏(Turning Turtles),附
variants_verify.py暴力 DP 核验与 6 道练习。
- 看点:Misère Nim 的唯一残局分叉(SJ 定理)与 Misère
Kayles \((5,5)\)
失效反例、阶梯 Nim 偶数阶抵消术、威佐夫博弈与黄金分割 Beatty
射线、斐波那契博弈的 Zeckendorf 分解 \(2\times\)
防火墙、翻硬币游戏(Turning Turtles),附
- 05|实战反杀手册、综合测验与超越
Nim:不对称博弈与开放问题
- 看点:5 步现场诊断协议流程图、红蓝绿 Hackenbush 与
Conway 超实数入门(\(+1, -1,
+\frac{1}{2}, *\) 的四类结果与加法)、Schaefer PSPACE
完全性边界与 Grundy’s Game 等未解难题,以及 10
道覆盖全系列的闭卷综合测验与
exam_verify.py。
- 看点:5 步现场诊断协议流程图、红蓝绿 Hackenbush 与
Conway 超实数入门(\(+1, -1,
+\frac{1}{2}, *\) 的四类结果与加法)、Schaefer PSPACE
完全性边界与 Grundy’s Game 等未解难题,以及 10
道覆盖全系列的闭卷综合测验与
四、每篇一句话价值
| 篇目 | 一句话价值 |
|---|---|
| 01 | 用 P/N 倒推和对称配对彻底戒掉盲目往前搜索的习惯,先拿下巴什与 Chomp。 |
| 02 | 用二进制筹码配对讲清 Nim 为何是异或,给出 3 秒口算招式与 Moore’s \(\text{Nim}_k\)。 |
| 03 | 证明任何正常公平博弈都能压缩成 SG 值做异或,通吃减法、拆堆与树形砍边。 |
| 04 | 拆穿反常、阶梯、同步取、动态上限四类常见规则魔改,并钉住 SJ 定理的失效边界。 |
| 05 | 沉淀 5 步现场拆招清单、10 题综合通关考,并打开不公平博弈与计算复杂性视野。 |
五、核心参考文献(系列共用)
- Bouton, C. L. (1901–1902). Nim, a game with a complete mathematical theory. Annals of Mathematics, 3(1/4), 35–39.
- Wythoff, W. A. (1907). A modification of the game of Nim. Nieuw Archief voor Wiskunde, 7(2), 199–202.
- Moore, E. H. (1910). A generalization of the game called nim. Annals of Mathematics, 11(2), 93–94.
- 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.
- Grundy, P. M., & Smith, C. A. B. (1956). Disjunctive games with the last player losing. Proceedings of the Cambridge Philosophical Society, 52(3), 527–533.
- Whinihan, M. J. (1963). Fibonacci Nim. The Fibonacci Quarterly, 1(4), 9–13.
- Gale, D. (1974). A curious Nim-type game. The American Mathematical Monthly, 81(8), 876–879.
- 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. Academic Press (2nd ed., A K Peters, 2001–2004).
- 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.
文章导航
读完这篇,下一步读什么
优先读同系列或同问题的下一篇,把单篇消费变成主题集群。
【组合博弈】03|万能降维武器:Sprague-Grundy 定理与 mex 的真正含义
只要游戏有限、公平且最后一步胜,任意状态都严格等价于一个特定大小的 Nim 堆。本文从博弈和与 mex 定义出发,用图解拆透 SG 等价性证明,通吃多堆减法、拆堆游戏(Lasker's Nim、Kayles)与 Green Hackenbush,附 Python 计算器与 6 道练习。
【组合博弈】04|那些专门坑人的变种:Anti-Nim、阶梯 Nim、威佐夫与斐波那契
对手发现你懂异或后最爱改的五种阴招:拿最后一颗算输(Anti-Nim 与 Misere Kayles 反例)、阶梯移硬币、两堆同步取(威佐夫黄金分割)、动态 2 倍上限(斐波那契 Zeckendorf)与翻硬币游戏,附暴力 DP 全量核验与 6 道练习。
【组合博弈】05|实战反杀手册、综合测验与超越 Nim:不对称博弈与开放问题
沉淀遇到陌生小游戏时的 5 步现场诊断协议,越过公平博弈边界介绍红蓝 Hackenbush 与 Conway 超实数、PSPACE 复杂性及 Grundy's Game 等未解难题,并附 10 道覆盖全系列的闭卷综合测验与 Python 核验脚本。
【组合博弈】02|Nim 与异或的直觉:为什么二进制按位相加能支配石子堆?
拒绝把 Nim 异或背成黑盒魔法:通过 2 的幂筹码配对直觉证明 Bouton 定理,给出 3 秒牌桌口算必胜步方法,并用同一套不变量一次打通 Poker Nim、Northcott 棋盘与 Moore's Nim_k,附 Python 验证与 6 道练习。