实战反杀手册、综合测验与超越 Nim:不对称博弈与开放问题

目录

前四篇我们分别拆解了 P/N 倒推与对称、Nim 二进制筹码与 Moore’s \(\text{Nim}_k\)、Sprague-Grundy 定理 以及 五大高频规则魔改。但真到桌游局或算法面试白板前,对手不会提前剧透“这道题考阶梯 Nim”——他只会抛出一段口头规则。

这篇收官章做三件事:

  1. 把整套方法论压成一张 5 步现场诊断流程图和一张速查表,让你面对任何陌生小游戏都能在 30 秒内选对锤子。
  2. 走出 Nim 所在的公平博弈小圈子,看清这套理论的边界:不公平博弈(红蓝 Hackenbush 与超实数)、PSPACE 完全性以及组合博弈论中至今悬而未决的开放问题。
  3. 提供一套 10 道闭卷综合测验(满分 100 分),独立做完并对完答案,就能确认自己以后不会再被这类小游戏牵着鼻子走。

一、5 步现场诊断协议:遇到陌生小游戏怎么拆?

拿到一条陌生规则,克制住“先试着推演两步”的冲动,严格按下面五关自顶向下排查:

遇到陌生组合博弈小游戏时的 5 步现场诊断流程图

图 1|组合博弈 5 步现场诊断协议。 每一关都在排除一类大陷阱,避免把正常规则的锤子砸到反常规则或不公平规则的钉子上。

  1. 第一关(看双方权限):是不是公平博弈(Impartial)?
    如果同一局面下,先手和后手的可选动作不同(比如红蓝棋子各走各的、横放多米诺 vs 竖放多米诺),立刻跳出 Nim / SG 框架,进入不公平博弈(见本文第二节)。
  2. 第二关(看终局胜负):最后走一步的人是赢(Normal)还是输(Misère)?
    如果是 Misère Play,切记不能盲套普通 SG 值或镜像模仿!只有纯 Anti-Nim(或单堆巴什等温顺博弈)能用“中局照常、残局改留奇数个 1”的 SJ 法则;一旦带拆堆或复杂图转移,必须手算小状态 DP 或查反常商结构。
  3. 第三关(看棋盘几何):有没有一键秒杀的对称配对或策略盗取?
    先花 5 秒扫一眼棋盘有没有中心对称(圆桌硬币、环形排布)、两半镜像(等长双堆、条带劈中点)或可逆抵消(加石子、后退步、偶数台阶)。能一招对称锁死就绝不写递推式。
  4. 第四关(看子游戏耦合):能否拆成多个互不干扰的独立组件(析取和)?
    • 若独立(每步只改一个组件,或把一个组件劈成两个独立子组件):直接上 Sprague-Grundy + XOR 核武器!在草稿纸上用 \(\operatorname{mex}\) 写出前 \(12\text{–}16\) 项观察公式或周期(牢记 Kayles 前周期 \(71\) 的教训,要靠归纳证明而不是拍脑袋猜)。
    • 若耦合(一次动多堆、两堆同步减、上限依赖上一步):立刻检索经典不变量家族(Moore 按位模 \(k+1\)、威佐夫 Beatty 射线、斐波那契 Zeckendorf 分解),否则写小规模记忆化 DP 找 \(\mathcal{P}\) 态规律。
  5. 第五关(动手验证与找具体招式):
    判定 \(\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)之一:

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\) 稳稳囊括进同一套加法体系里!

红蓝绿 Hackenbush 枝条的超实数赋值与博弈加法示意

图 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) 问题!

请分清两个容易混淆的事实:

类似地,真实棋类往往比这更庞大:跳棋(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):

  1. Grundy’s Game 的 SG 序列到底是不是最终周期的?
    如 第 03 篇 所述,把一堆石子拆成两堆不等非空堆的 Grundy’s Game,被 Winning Ways 猜想最终进入周期。Achim Flammenkamp 已将计算推进至超过 \(2^{35}\)(约 \(3.43 \times 10^{10}\))项,仍未发现周期,且稀疏异常值仍在不规则出现。
  2. \(3 \times n\) Chomp 的显式必胜步公式是什么?
    第 01 篇 用策略盗取三行就证明了任意 \(m \times n > 1\) 的 Chomp 先手必胜,但连 \(3 \times n\) 三行巧克力的必胜着法结构至今没有封闭公式(Doron Zeilberger 2001 给出了渐近形态猜想与自动机分析,仍未完全闭合)。
  3. 一般反常八进制游戏(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(拿走最后一颗石子者输),分别判断下面两个局面的胜负,若是先手胜则写出必胜第一步:

参考解答(第 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 推 \(1\) 枚到地板 0(5 -> 4);
  2. 从台阶 3 推 \(1\) 枚到台阶 2(7 -> 6);
  3. 从台阶 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 劈成两堆的所有三种拆法:
    1. 7 -> 1 + 6:\(g(1) \oplus g(6) = 1 \oplus 6 = 7\)(胜!)
    2. 7 -> 2 + 5:\(g(2) \oplus g(5) = 2 \oplus 5 = 7\)(胜!桌面变成对称的 (2, 2, 5, 5)!)
    3. 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 步在圆环上拿走 \(1\) 枚还是相邻 \(2\) 枚硬币,原本封闭的圆环都会被咬开一个缺口,瞬间退化成一条直线排列的 \(m\) 枚硬币(其中 \(m = n - 1 \ge 2\) 或 \(m = n - 2 \ge 1\))。
  2. 轮到后手面对一条长为 \(m\) 的直线,直接使出 第 01 篇练习 5 的必杀技:
    • 若 \(m\) 为奇数,拿走直线最正中那 \(1\) 枚;
    • 若 \(m\) 为偶数,拿走直线最正中相邻的 \(2\) 枚。
  3. 这一刀把直线劈成左右两段完全等长、互不干扰的独立直线!此后无论先手在左段拿什么,后手都在右段做完全镜像操作,稳收最后一枚!

(以 \(n = 10\) 为例:若先手拿 \(1\) 枚剩长为 \(9\) 的线,后手拿正中第 \(5\) 枚拆成 (4, 4);若先手拿 \(2\) 枚剩长为 \(8\) 的线,后手拿正中 \(2\) 枚拆成 (3, 3)。)

第 10 题(14 分):红蓝绿 Hackenbush 超实数综合判断

地面上插着 5 根独立的红蓝枝条:BR、BR、B、R、R(字符顺序从地面向上,B 为蓝方专砍,R 为红方专砍)。

参考解答(第 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 个文件。

打开下载目录 →

文章导航

分类入口
algorithms
标签入口
#combinatorial-game-theory#hackenbush#surreal-numbers#pspace-complete#open-problems#nim#exam

读完这篇,下一步读什么

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


By .