系列总览:从 Nim 到 Sprague-Grundy,看穿取石子小游戏的必胜法则

目录

桌游聚会、算法面试、数学竞赛里经常冒出一类看似无害的取石子小游戏:桌上摆着几堆硬币、棋子或巧克力,两人轮流按规则拿走一部分,谁拿走最后一块就赢(或者谁拿走最后一块就输)。多数人面对这类问题都会掉进同一个陷阱——试图往前推演博弈树(“我拿 2 个,如果他拿 3 个我就……”),三步之后分支爆炸,完全被对手牵着鼻子走;即便背过“Nim 用异或”的口诀,只要对方把规则微调半句(例如“最后拿完的算输”“一次最多拿 3 个”“可以把一堆拆成两堆”“只能往左边移”),口诀立刻失效。

这套系列把这类“欺负人”的双人完全信息小游戏拆成一套 5 步通用工具箱。每篇都提供纸笔手算步骤、暗色图解、可运行的 Python 核验脚本与带折叠详解的练习题,目标是让你在牌桌或白板前不再靠猜,而是直接定位不变量、反手构造必胜步。

系列规模:全 5 篇正文 + 本总览索引。全部数值例题、SG 表、变种公式与课后习题答案均已由各篇附带的 Python 脚本与暴力动态规划交叉验证。

一、这个系列要回答的五个问题

  1. 为什么往前想三步就会晕,而高手一眼就能判胜负?
    因为博弈树应该从终局倒推而不是从开局前推。只要给每个状态贴上“先手必胜(\(\mathcal{N}\))”或“后手必胜(\(\mathcal{P}\))”两枚标签,再结合对称配对与策略盗取,就能在不展开整棵树的情况下直接定性。回答在 01|胜负的底层逻辑。

  2. 取石子跟二进制异或(\(\oplus\))到底有什么关系?
    Bouton 在 1901 年给出的异或公式并不是凭空降临的巧合:把每一堆石子拆成 \(2^k\) 面值的二进制筹码,异或为 \(0\) 等价于“每种面值的筹码都成双配对”。理解筹码配对后,既能 3 秒内口算必胜步,也能自然推广到一次可动 \(k\) 堆的 Moore’s \(\text{Nim}_k\)(按位模 \(k+1\))。回答在 02|Nim 与异或的直觉。

  3. 规则一改,异或口诀为什么突然不管用?怎么把千奇百怪的新游戏还原回 Nim?
    Sprague(1935)与 Grundy(1939)证明了一个统一结论:只要游戏满足有限、公平、正常规则(最后一步赢),任何单组件状态都严格等价于某一个特定大小的 Nim 堆,其大小就是递归计算的 \(\operatorname{mex}\) 值(SG 值)。多个独立组件拼在一起,直接把各组件 SG 值做异或。回答在 03|万能降维武器:Sprague-Grundy。

  4. 如果对方故意把规则改刁钻——拿最后一颗算输、棋子只能向左推、两堆同时拿、上限跟上一步挂钩——该怎么拆?
    拆解必须先分清“破坏了哪条前提”:Anti-Nim 破坏了正常终局,只在进入全 \(1\) 残局的唯一分叉点改口;阶梯 Nim 用偶数阶“镜像抵消”把一半台阶变透明;威佐夫博弈因两堆耦合落到黄金分割射线(Beatty 定理);斐波那契博弈用 Zeckendorf 分解筑起 \(2\times\) 防火墙。同时用 Misère Kayles 的 \((5,5)\) 反例标明 Anti-Nim 规则何时彻底失效。回答在 04|专门坑人的经典变种。

  5. 遇到从未见过的新小游戏,按什么顺序排查?公平博弈理论的边界在哪里?
    给出一套 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

三、目录与每篇看点

  1. 系列总览(本文)
  2. 01|胜负的底层逻辑:P/N 态、倒推法与对称模仿
    • 看点:Zermelo 有限决定性定理、有向无环图 P/N 倒推三公理、巴什博弈模 \(k+1\) 陷阱、对称模仿(圆桌硬币 / 偶数堆)、Chomp 巧克力毒块的非构造性策略盗取证明,附 pn_solver.py 与 5 道分级练习。
  3. 02|Nim 与异或的直觉:为什么二进制按位相加能支配石子堆?
    • 看点:把石子堆拆成 \(2^k\) 筹码看穿 Bouton 定理、三步口算必胜招式、Poker Nim(允许往堆里放石子为何不影响胜负)、Northcott 棋盘等价归约、Moore’s \(\text{Nim}_k\) 的按位模 \(k+1\) 推广,附 nim_verify.py 与 6 道练习。
  4. 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 道练习。
  5. 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 道练习。
  6. 05|实战反杀手册、综合测验与超越 Nim:不对称博弈与开放问题
    • 看点:5 步现场诊断协议流程图、红蓝绿 Hackenbush 与 Conway 超实数入门(\(+1, -1, +\frac{1}{2}, *\) 的四类结果与加法)、Schaefer PSPACE 完全性边界与 Grundy’s Game 等未解难题,以及 10 道覆盖全系列的闭卷综合测验与 exam_verify.py。

四、每篇一句话价值

篇目 一句话价值
01 用 P/N 倒推和对称配对彻底戒掉盲目往前搜索的习惯,先拿下巴什与 Chomp。
02 用二进制筹码配对讲清 Nim 为何是异或,给出 3 秒口算招式与 Moore’s \(\text{Nim}_k\)。
03 证明任何正常公平博弈都能压缩成 SG 值做异或,通吃减法、拆堆与树形砍边。
04 拆穿反常、阶梯、同步取、动态上限四类常见规则魔改,并钉住 SJ 定理的失效边界。
05 沉淀 5 步现场拆招清单、10 题综合通关考,并打开不公平博弈与计算复杂性视野。

五、核心参考文献(系列共用)

文章导航

分类入口
algorithms
标签入口
#combinatorial-game-theory#nim#sprague-grundy#mex#wythoff#fibonacci-nim#hackenbush#game-theory

读完这篇,下一步读什么

优先读同系列或同问题的下一篇,把单篇消费变成主题集群。


By .