当你刚学会 第 03 篇 的 Sprague-Grundy 定理,满怀信心准备上桌反杀,对手往往会笑眯眯地补一句:
- “咱们玩反的,谁拿走最后一颗谁输!”
- “石子不能凭空拿走,只能一级级往左推!”
- “两堆可以同时拿走一样多!”
- “每次拿的数量不能超过上一个人刚拿的两倍!”
很多人刚建立的自信瞬间崩塌,觉得每个变种都要死记一套孤立的偏门公式。其实不然——这些变种之所以让 SG 异或“不好使”,只是因为各自精准破坏了前面五大前提里的某一条。看清被破坏的是哪条前提,就能立刻对症下药:
| 经典变种 | 破坏了哪条标准前提 | 核心破局武器 |
|---|---|---|
| Anti-Nim(反常 Nim) | 破坏“正常终局”→ 最后一步判负 | 中局完全照玩普通
Nim,仅在唯一残局分叉点改留奇数个
1 |
| 阶梯 Nim(Staircase Nim) | 破坏“各堆独立”→ 拿走变流入下一级 | 偶数阶抵消术:只算奇数阶异或,偶数阶全当缓冲桶 |
| 威佐夫博弈(Wythoff) | 破坏“单堆独立”→ 允许两堆同步减 \(d\) | Beatty 定理 + 黄金分割射线:冷态 \((\lfloor k\phi \rfloor, \lfloor k\phi^2 \rfloor)\) |
| 斐波那契博弈(Fibonacci Nim) | 破坏“无记忆性”→ 上限依赖上一步 \(2t\) | Zeckendorf 分解:永远取走最小斐波那契项,构筑 \(2\times\) 防火墙 |
| 翻硬币(Turning Turtles) | 表面多子联动,实则线性叠加 | 单个正面独立等价于 \(*i\),翻转两枚等价于异或翻转 |
一、Anti-Nim(反常 Nim):只改最后一步,以及 SJ 定理的致命误区
规则:与普通 Nim 完全相同,唯一区别是拿走最后一颗石子的人判负(Misère Play)。
直觉容易走两个极端:要么以为“把胜负反过来(异或等于 \(0\) 先手赢)就行”,结果在 \((1, 1)\) 上就撞墙(拿一颗剩一颗,先手赢,但 \(1 \oplus 1 = 0\),确实反了!再看 \((2, 2)\):先手拿成 \((2, 1)\),后手直接拿光大堆留 \((0, 1)\) 逼死先手,还是后手赢!并没有反!);要么觉得反常规则完全无规律。
Bouton 在 1901 年的原论文里就已经顺手给出了反常 Nim 的完整定理(后在算法竞赛圈常被称为 SJ 定理,对应 Sprague / Bouton 的反常判据):
Misère Nim 判定法则(Bouton 1901):设各堆大小为 \((a_1, \dots, a_m)\),异或和 \(S = a_1 \oplus \dots \oplus a_m\)。先手必胜(\(\mathcal{N}\) 态)当且仅当满足下列二者之一:
- 存在至少一堆大小 \(> 1\),且 \(S \neq 0\);
- 所有堆大小都 \(\le 1\),且 \(S = 0\)(即大小为 \(1\) 的堆有偶数个)。
核心直觉只有一句话:只要场上还有至少两堆大于 \(1\),反常 Nim 的打法与普通 Nim 100% 一模一样!唯一需要变招的,只有全场刚刚剩下“恰好一堆大于 \(1\)”的那一瞬间!
图 1|Anti-Nim 的唯一残局分叉点。
只要你一直维持 \(S =
0\),场上就不可能出现“恰好一堆 \(> 1\)”(因为唯一大于 \(1\)
的堆在更高比特位上无人配对,异或绝不可能为 \(0\))。所以一定是对手被迫打出“恰好一堆
\(>
1\)”的局面交到你手里!此时你拥有绝对的奇偶控制权——你可以把那个唯一的大堆缩成
0 或缩成
1,精确控制场上最终剩下奇数个
1,逼对手收走最后一颗。
手算两个残局分叉立刻通透:
- 面对
(1, 1, 5):已有 \(2\) 个1,再把5缩成1,留下(1, 1, 1)(\(3\) 个1,奇数),对手拿第 1 颗、你拿第 2 颗、对手被迫拿第 3 颗输! - 面对
(1, 1, 1, 5):已有 \(3\) 个1,把5直接清空成0,留下(1, 1, 1, 0)(\(3\) 个1,奇数),对手必输!
警报:千万别把 Anti-Nim 法则乱套到其他反常博弈上!
很多二手题解写着一句流传极广的错误结论:“对于任意反常公平博弈(Misère Play),算出每个子游戏的普通 SG 值,全 \(\le 1\) 时看异或为 \(0\),否则看异或非 \(0\)。”
这是数学上的假命题!
下面用我们在仓库文章同目录的 variants_verify.py
里暴力 DP 实测出的 Misère
Kayles(反常保龄球瓶) 现场打脸:
回想 第 03 篇 的 Kayles(打倒 \(1\) 个或相邻 \(2\) 个瓶子),现在改成打倒最后一个瓶子的人输。单排 \(4\) 个和 \(5\) 个瓶子的普通 SG 值分别是 \(g(4) = 1,\ g(5) = 4\)。来看两个局面:
| Misère Kayles 局面 | 普通 SG 值 | 异或和 | 盲套 SJ 法则预测 | 暴力 DP 真实胜负 |
|---|---|---|---|---|
(5, 5)(两排完全一样!) |
\((4, 4)\) | \(0\) | \(\mathcal{P}\)(后手胜) | \(\mathcal{N}\)(先手胜!) |
(4, 5) |
\((1, 4)\) | \(5\) | \(\mathcal{N}\)(先手胜) | \(\mathcal{P}\)(后手胜!) |
(1, 5) |
\((1, 4)\) | \(5\) | \(\mathcal{N}\)(先手胜) | \(\mathcal{P}\)(后手胜!) |
这一组数字同时炸毁了两个直觉陷阱:
- 在反常规则下,连完全对称的
(5, 5)都不一定是后手胜! 先手只需打倒一排最边缘的 \(1\) 个瓶子,把(5, 5)变成(4, 5),就把真正的 \(\mathcal{P}\) 态塞给了对手(因为如果后手在(5, 5)里盲目镜像模仿,镜像模仿会让后手自己拿走最后一个瓶子直接自杀!)。 - 普通 SG 值无法决定一般反常博弈的析取和! Grundy 与 Smith 在 1956 年的经典论文 Disjunctive games with the last player losing 中最早揭示了反常析取和的病态复杂性;Conway(1976)在 On Numbers and Games 中证明 SJ 法则只对一类叫作 Tame Games(温顺博弈) 的极窄子类成立,而 Kayles 属于 Wild Games(狂野博弈)。直到 2005 年,Thane Plambeck 在 Integers 发表 Taming the wild in impartial combinatorial games,提出反常商代数(Misère Quotients),才为大量狂野反常游戏建立了局部的交换幺半群理论。
所以记住边界:SJ 法则对纯 Anti-Nim(及已证温顺的博弈)100% 精确;一旦规则带有拆堆或其他复杂转移且改为“最后一步输”,严禁直接套用普通 SG + SJ 法则。
二、阶梯 Nim(Staircase Nim):把一半台阶变成“隐形垃圾桶”
规则:有编号 \(1, 2, \dots, n\) 的 \(n\) 级台阶以及最底部的地板(编号 \(0\))。每级台阶上放着若干枚硬币 \(a_i\)。两人轮流从任意一级台阶 \(i \ge 1\) 上拿走任意正整数枚硬币,放到紧挨着的下一级台阶 \(i - 1\) 上;落到地板 \(0\) 的硬币退出游戏。无法移动者输。
乍看之下每步移动都在往下一堆里“加石子”,各堆强耦合,似乎无从下手。结果答案简单到离谱:
阶梯 Nim 定理:阶梯 Nim \((a_1, a_2, \dots, a_n)\) 完全等价于只保留所有奇数号台阶 \((a_1, a_3, a_5, \dots)\) 的普通 Nim!所有偶数号台阶上的硬币数量不管是一枚还是一亿枚,统统忽略不计!
为什么偶数台阶可以彻底无视?只需运用我们在 Poker Nim 学过的“原路抵消”思想:
图 2|阶梯 Nim 的偶数阶抵消术。 以
[4, 7, 2, 9, 5] 为例,仅看蓝色/橙色奇数台阶
(4, 2, 5),异或为 \(4
\oplus 2 \oplus 5 = 3 \neq 0\)。先手将第 5 阶上的
\(3\) 枚硬币推到第 4
阶,奇数台阶立刻变成
(4, 2, 2)(异或归零)。
假设你已经把所有奇数阶的异或和压成了 \(0\),轮到对手走,只有两种可能:
- 对手把 \(m\)
枚硬币从某个奇数阶 \(2k-1\)
推到偶数阶 \(2k-2\):
由于偶数阶是透明垃圾桶,这一步在奇数阶视角里就是从第 \(2k-1\) 堆标准地拿走了 \(m\) 颗石子!你按普通 Nim 的 Bouton 策略,从某个奇数阶推走相应数量的硬币到它下面的偶数阶,立刻把奇数阶异或再次归零。 - 对手把 \(m\)
枚硬币从某个偶数阶 \(2k\)
推到奇数阶 \(2k-1\)(企图往你的奇数
Nim 堆里塞石子破坏平衡):
你二话不说,立刻把这 \(m\) 枚刚掉进奇数阶 \(2k-1\) 的硬币,原封不动地继续往下推一级到偶数阶 \(2k-2\)!
效果如何?奇数阶 \(2k-1\) 先 \(+m\) 再 \(-m\),所有奇数阶硬币数纹丝未动,异或依然为 \(0\)! 而那 \(m\) 枚硬币严格往下掉了两级,更接近地板 \(0\),对手绝不可能无限折腾下去。
顺手收割一个马甲:一维棋盘向左移币(Coins on a Strip)
桌上一排编号从左到右为 \(1, 2, \dots, L\) 的格子,放着 \(m\) 枚硬币,每人轮流选一枚硬币向左移动任意格(不能越过或撞上左边相邻的硬币),无路可走者输。
把硬币从右往左两两配对,计算相邻两枚硬币之间的空隙距离:每向右移动(其实不能右移,只能左移)一枚硬币 \(d\) 格,它左边的空隙减 \(d\),右边的空隙加 \(d\)——这和“把 \(d\) 颗石子从台阶 \(i\) 移到台阶 \(i-1\)”完全同构!只需从最右边那枚硬币开始按空隙编号为台阶 \(1, 2, 3, \dots\),立刻化为阶梯 Nim!
三、威佐夫博弈(Wythoff’s Game):黄金分割与 Beatty 射线
荷兰数学家 Willem Abraham Wythoff 在 1907 年提出了 Nim 的经典双堆耦合变体:
规则:桌上只有两堆石子 \((a, b)\)。每回合有两种合法走法:
- 从任意一堆中取走任意正整数颗石子;
- 从两堆中同时取走相同数量 \(d \ge 1\) 颗石子。
拿走最后一颗者胜(也可以等价地想象成国际象棋棋盘上的一枚皇后,从坐标 \((a, b)\) 每次只能向左、向下、或向左下 \(45^\circ\) 对角线走任意格,先走到原点 \((0, 0)\) 者胜)。
因为允许两堆同时减 \(d\),两堆不再是独立析取和,SG 异或不能直接拆分两堆。我们按 第 01 篇 的思路,把对称的 \((a, b)\)(不妨设 \(a \le b\))中所有 \(\mathcal{P}\) 态(Wythoff 称之为冷态 Cold Positions)从小到大手工列出来:
- 第 \(0\) 个冷态:\((0, 0)\)。
- 第 \(1\) 个冷态:所有 \((0, *), (*, 0), (d, d)\) 都能一步打到 \((0, 0)\),所以 \(1\) 不能配 \(0\) 或 \(1\),最小未出现的数是 \(1\),配 \(1 + 1 = 2 \implies (1, 2)\)。
- 第 \(2\) 个冷态:最小还没在任何冷态里出现过的正整数是 \(3\),而差值 \(0, 1\) 已经被 \((0,0)\) 和 \((1,2)\) 占掉了(若新冷态差值也是 \(1\),就能走对角线打到 \((1,2)\)!),所以新差值必须取 \(2 \implies (3, 5)\)。
- 依此类推:第 \(k\)
个冷态 \((a_k, b_k)\)
满足两条极其简洁的构造律:
- \(a_k\) 是此前所有 \((a_0, b_0), \dots, (a_{k-1}, b_{k-1})\) 中从未出现过的最小正整数(即 \(a_k = \operatorname{mex}\{a_0, b_0, \dots, a_{k-1}, b_{k-1}\}\));
- \(b_k = a_k + k\)。
前 \(10\) 组冷态为: \[(0, 0),\ (1, 2),\ (3, 5),\ (4, 7),\ (6, 10),\ (8, 13),\ (9, 15),\ (11, 18),\ (12, 20),\ (14, 23).\]
令人惊叹的是,这条 \(\operatorname{mex}\) 构造出来的序列竟然有精确闭式解!依靠 Beatty 定理(若两个无理数 \(\alpha, \beta > 1\) 满足 \(\frac{1}{\alpha} + \frac{1}{\beta} = 1\),则集合 \(\{\lfloor k\alpha \rfloor\}_{k \ge 1}\) 与 \(\{\lfloor k\beta \rfloor\}_{k \ge 1}\) 恰好不重不漏地划分全部正整数 \(\mathbb{Z}^+\)),取黄金分割数 \(\phi = \frac{1 + \sqrt{5}}{2} \approx 1.6180339887\),它恰好满足 \(\phi^2 = \phi + 1\) 以及 \(\frac{1}{\phi} + \frac{1}{\phi^2} = 1\)!于是:
\[ a_k = \lfloor k\phi \rfloor, \qquad b_k = \lfloor k\phi^2 \rfloor = \lfloor k\phi \rfloor + k = a_k + k. \]
图 3|威佐夫博弈的二维冷态地图(由仓库同目录的
variants_verify.py 暴力 DP
核验生成)。 所有橙色 \(\mathcal{P}\)
态精准地贴在斜率为 \(\phi \approx
1.618\) 和 \(1/\phi \approx
0.618\) 的两条黄金射线上。图中红色箭头标出了从 \((10, 13)\) 沿对角线同时拿走
\(6\) 颗直击冷态 \((4, 7)\) 的必胜招式。
威佐夫实战 2 秒判断法
给定两堆 \((a, b)\),先排成 \(a \le b\):
- 算差值 \(k = b - a\),再算 \(a^* = \lfloor k \times 1.618034 \rfloor\);
- 若 \(a = a^*\):就是 \(\mathcal{P}\) 态(后手必胜);
- 若 \(a > a^*\):两堆同时拿走 \(a - a^*\) 颗,一步沿对角线落入冷态 \((a^*, a^* + k)\)!
- 若 \(a < a^*\):说明 \((a, b)\) 在射线的左上方,只减大堆 \(b\)(或只减小堆 \(a\))即可横竖命中 \(a\) 所在的冷态对——例如 \((10, 13)\) 除了对角线到 \((4, 7)\),还可以只把 \(10 \to 8\) 命中 \((8, 13)\),或只把 \(13 \to 6\) 命中 \((6, 10)\)!
四、斐波那契博弈(Fibonacci Nim):Zeckendorf 分解与 \(2\times\) 防火墙
规则(Robert E. Gaskell 发明,Michael J. Whinihan 1963 年在 The Fibonacci Quarterly 证明):桌上只有一堆 \(n \ge 2\) 颗石子。
- 第 1 步先手可以拿走 \(1\) 到 \(n - 1\) 颗(不能第一手一把全拿光);
- 此后每一步,玩家至少拿 \(1\) 颗,但最多不能超过对手上一步所拿数量的 \(2\) 倍(即 \(1 \le t \le 2 t_{\text{prev}}\));
- 拿走最后一颗石子者胜。
动态上限让状态空间变成二维
(剩余石子 n, 当前上限 cap),普通单堆周期法失效。但答案干净得不可思议:
Whinihan 定理(1963):在斐波那契博弈中,初始局面 \(n\) 是 \(\mathcal{P}\) 态(后手必胜),当且仅当 \(n\) 本身是一个斐波那契数(\(2, 3, 5, 8, 13, 21, 34, 55, 89, \dots\))!
若 \(n\) 不是斐波那契数,先手必胜,且必胜策略只有一句话:把 \(n\) 写成 Zeckendorf 分解(不相邻斐波那契数之和),每次精准拿走其中最小的那一项!
什么是 Zeckendorf 定理(Lekkerkerker 1952;Zeckendorf 1972)?任意正整数都可以唯一地写成若干个互不相邻的斐波那契数之和(贪心法即可算出:每次减去不超过当前值的最大斐波那契数)。例如:
\[ 20 = 13 + 5 + 2 = F_7 + F_5 + F_3. \]
图 4|\(n = 20\) 的 Zeckendorf 防火墙。 之所以“拿走最小项 \(2\)”一定能锁死对手,核心在于斐波那契数的不相邻性质:如果两项下标至少隔 \(2\)(例如 \(F_3 = 2\) 和 \(F_5 = 5\)),恒有
\[ F_{k+2} = F_{k+1} + F_k > 2 F_k. \]
跟着 \(n = 20 = 13 + 5 + 2\) 走一遍全流程,你就能一眼看透证明的精髓:
- 先手拿走最小项 \(F_3 = 2\),剩下 \(13 + 5 = 18\),并把对手的上限锁死在 \(2 \times 2 = 4\)。
- 因为 \(4 < 5\),对手绝对不可能一把吞光 \(5\)-区块,更别说摸到后面的 \(13\)-区块!
- 所以从对手视角看,他被迫在一个独立的、大小为 \(F_5 = 5\) 的斐波那契子游戏里先手行动(且上限 \(< 5\))。由归纳法,既然 \(F_5 = 5\) 本身是个 \(\mathcal{P}\) 态,你一定能成为亲手收掉 \(5\)-区块最后一颗石子的人!
- 还有一个精妙细节:当你收掉 \(5\)-区块的最后一颗时,你最后这一手拿的石子数 \(t_{\text{last}}\) 会不会太大,导致 \(2 t_{\text{last}} \ge 13\) 让对手一把抄了 \(13\)-区块的老家?不会! 因为你在 \(5\)-区块里每次只拿最小 Zeckendorf 项,最后一步至多拿 \(F_3 = 2 < 5 / 2\),所以给对手留下的上限 \(2 t_{\text{last}} \le 4 < 13\),依然牢牢锁在 \(13\)-区块以内!
- 接着对手又被迫在 \(F_7 = 13\) 里先手挨打,最终你稳稳拿走全盘最后一颗石子!
如果开局本身就是斐波那契数(例如 \(n = 21\)),先手如果拿得太大(\(\ge 21/3 = 7\),如拿 \(8\) 颗剩 \(13\)),后手上限为 \(16 \ge 13\) 直接一把全拿光秒杀;如果先手拿得小(\(< 7\),如拿 \(3\) 颗剩 \(18 = 13 + 5\)),他相当于把非斐波那契数的后继拆解权送给了后手,后手照上述策略拿走最小项(在上限允许范围内)稳赢!
五、翻硬币家族代表:Turning Turtles(翻乌龟)
最后看一类常出现在智力题和竞赛里的翻硬币游戏(Berlekamp–Conway–Guy Winning Ways 第 14 章专门收录了整套翻硬币家族),以最经典的 Turning Turtles 为例:
规则:一排 \(n\) 枚硬币从左到右编号为 \(1, 2, \dots, n\),各自朝上(正面 H)或朝下(反面 T)。每回合选一枚正面朝上的硬币 \(i\) 把它翻成反面,并且可选地挑它左边任意一枚硬币 \(j < i\) 也翻一面(正面变反面、反面变正面都可以)。所有硬币都变成反面时游戏结束,最后操作者胜。
乍看之下翻两枚硬币会互相影响,但用二进制视角一秒破案:
- 把每一枚正面朝上的硬币 \(i\) 单独看作一个大小为 \(i\) 的 Nim 堆(\(*i\)),整排硬币的值就是所有正面所在编号的异或和: \[ S = \bigoplus_{\text{coin } i \text{ is H}} i. \]
- 只翻硬币 \(i\)(H\(\to\)T):等价于把 Nim 堆 \(i\) 直接清空成 \(0\)(异或变化 \(\oplus i\))。
- 同时翻硬币 \(i\)(H\(\to\)T)和它左边的硬币 \(j < i\):
- 若 \(j\) 原来是反面 T,翻成正面 H \(\implies\) 相当于把堆 \(i\) 缩小成了堆 \(j\)(异或变化 \(\oplus i \oplus j\));
- 若 \(j\) 原来是正面 H,翻成反面 T \(\implies\) 相当于把堆 \(i\) 和堆 \(j\) 同时清空——而因为 \(j \oplus j = 0\),它引起的异或变化同样恰好是 \(\oplus i \oplus j\)!
结论无比简洁:Turning Turtles 严格等价于普通 Nim,每枚正面朝上的硬币 \(i\) 就是一个大小为 \(i\) 的 Nim 堆! 当 \(S \neq 0\) 时,找到包含 \(S\) 最高位的正面硬币 \(i\),令 \(j = i \oplus S < i\):若 \(j = 0\) 则只翻硬币 \(i\);若 \(j > 0\) 则同时翻转硬币 \(i\) 和硬币 \(j\)(不管 \(j\) 原本是正是反!),异或瞬间归零!
六、五种变种的暴力 DP 全量核验
上述五套闭式定理(含 Misère Kayles
反例)全部在仓库文章同目录的 variants_verify.py
中与无公式暴力 DP 进行了全量对拍。运行
python post/combinatorial-games/04-classic-variants/variants_verify.py
的真实输出:
Misere Nim DP vs formula: 2401 states checked, 0 mismatches.
Staircase Nim DP vs formula: 256 states checked, 0 mismatches.
Wythoff DP vs Beatty formula on [0..40]^2: 1681 states checked, 0 mismatches.
Fibonacci Nim DP vs Zeckendorf on n=2..80: 79 states checked, 0 mismatches.
Turning Turtles DP vs XOR on 8 coins: 256 states checked, 0 mismatches.
=== Misere Kayles Counterexample to SJ Theorem ===
Misere Kayles (5, 5): normal SG=(4, 4), XOR=0, SJ predicts P, actual=N
Misere Kayles (4, 5): normal SG=(1, 4), XOR=5, SJ predicts N, actual=P
Misere Kayles (1, 5): normal SG=(1, 4), XOR=5, SJ predicts N, actual=P
七、课后练习(专治各种规则魔改)
练习 1(Anti-Nim):残局分叉速判
反常 Nim(拿最后一颗者输),分别判断下列三个局面的胜负,若是先手胜则写出必胜步:
- (a)
(1, 1, 5) - (b)
(1, 1, 1, 5) - (c)
(2, 4, 6)
参考解答与思路(先独立推导再展开)
- (a)
(1, 1, 5):只有一堆 \(> 1\),先手控制奇偶!把5缩为1,留下(1, 1, 1)(奇数个1),先手必胜。 - (b)
(1, 1, 1, 5):只有一堆 \(> 1\),把5直接拿光成0,留下(1, 1, 1, 0)(奇数个1),先手必胜。 - (c)
(2, 4, 6):存在 \(\ge 2\) 堆大于 \(1\),且异或和 \(2 \oplus 4 \oplus 6 = 0\),因此是 \(\mathcal{P}\) 态(后手必胜)!无论先手怎么走都会破坏 \(S = 0\),后手一直维持 \(S = 0\) 直到先手被迫打出“仅剩一堆 \(> 1\)”时收尾反杀。
练习 2(阶梯 Nim):识别 100 颗硬币的烟雾弹
6 级阶梯 Nim(从台阶 1 到台阶 6 的硬币数)为
(3, 10, 6, 8, 5, 100),第 6 阶堆着整整 \(100\)
枚硬币。先手必胜还是后手必胜?如果对手第一步把第 6 阶的
\(47\) 枚硬币推到第 5
阶,该怎么回应?
参考解答与思路(先独立推导再展开)
屏蔽所有偶数台阶(第 2、4、6 阶的 10, 8, 100
全是烟雾弹!),只看奇数台阶(第 1、3、5
阶):(3, 6, 5)。
计算异或:\(3 \oplus 6 \oplus 5 =
5 \oplus 5 = 0\)!
因此开局是 \(\mathcal{P}\)
态(后手必胜)。当先手把 \(47\) 枚硬币从第 6
阶(偶)推到第 5 阶(奇)时,后手只需把那 \(47\) 枚硬币立刻从第 5
阶继续推到第 4 阶(偶),奇数阶瞬间恢复
(3, 6, 5),稳操胜券。
练习 3(威佐夫):黄金射线实战
在威佐夫博弈中(已知 \(\phi \approx 1.618034\)):
- (a) 局面
(12, 20)是先手胜还是后手胜? - (b) 局面
(10, 13)是先手胜还是后手胜?找出全部 3 种必胜第一步。
参考解答与思路(先独立推导再展开)
- (a)
(12, 20):差值 \(k = 20 - 12 = 8\)。计算 \(\lfloor 8 \times 1.618034 \rfloor = \lfloor 12.944 \rfloor = 12\),恰好等于较小堆 \(12\)!所以(12, 20)是第 \(8\) 号冷态,后手必胜。 - (b)
(10, 13):差值 \(k = 13 - 10 = 3\),\(\lfloor 3\phi \rfloor = 4 < 10\),不是冷态,先手必胜!三种必胜步分别对应“同时减、只减小堆、只减大堆”三个方向:- 两堆同时减 \(6\):\((10, 13) \to (4, 7)\)(命中 \(k = 3\) 号冷态);
- 只把 \(10\) 减到 \(8\):\((10, 13) \to (8, 13)\)(命中 \(k = 5\) 号冷态,因为 \(\lfloor 5\phi \rfloor = 8,\ 8+5=13\));
- 只把 \(13\) 减到 \(6\):\((10, 13) \to (10, 6)\),即 \((6, 10)\)(命中 \(k = 4\) 号冷态,因为 \(\lfloor 4\phi \rfloor = 6,\ 6+4=10\))。
练习 4(斐波那契博弈):三道快问快答
斐波那契数列表:\(1, 2, 3, 5, 8, 13, 21, 34, 55, 89, \dots\)。判断下列三个初始石子数谁必胜,并写出先手必胜第一步:
- (a) \(n = 34\)
- (b) \(n = 50\)
- (c) \(n = 100\)
参考解答与思路(先独立推导再展开)
- (a) \(n = 34\):\(34\) 本身是斐波那契数(\(F_9 = 34\)),后手必胜!
- (b) \(n = 50\):贪心做 Zeckendorf 分解:\(50 = 34 + 13 + 3\)(均不相邻)。先手必胜,第一步拿走最小项 \(3\) 颗(对手上限 \(6 < 13\))。
- (c) \(n = 100\):贪心分解:\(100 = 89 + 8 + 3\)(均不相邻)。先手必胜,第一步拿走最小项 \(3\) 颗(对手上限 \(6 < 8\))。
练习 5(翻硬币):Turning Turtles 定位翻转
一排 \(8\) 枚硬币(编号
\(1\text{–}8\)),当前只有第
2、第 5、第 8
枚正面朝上(其余反面)。请问先手必胜还是后手必胜?如果是先手胜,应该翻哪两枚硬币?
参考解答与思路(先独立推导再展开)
计算正面编号的异或和:\(S = 2
\oplus 5 \oplus 8 = (0010)_2 \oplus (0101)_2 \oplus (1000)_2
= (1111)_2 = 15 \neq
0\),先手必胜!
\(S\) 的最高位是
8,只有硬币 8 包含位
8。算出目标编号 \(j =
8 \oplus 15 = 7 < 8\)。
因此先手把第 8 枚硬币(正面 \(\to\) 反面)和第 7
枚硬币(反面 \(\to\)
正面)同时翻转!翻转后正面朝上的硬币变成
[2, 5, 7],异或和 \(2
\oplus 5 \oplus 7 = 0\),对手落入必败态!
练习 6(反例辨析):为什么不能对 Misère Kayles 盲套 SJ 定理?
在 Misère Kayles 中,两排完全对称的 (5, 5)
为什么不是后手必胜?从这一反例中能得出哪两条使用 Anti-Nim
规则时的安全守则?
参考解答与思路(先独立推导再展开)
- 镜像为什么失效:在正常规则下,镜像模仿保证后手走出全盘最后一步从而获胜;但在反常规则下,走出最后一步的人判负,镜像反而会让后手自毁。纯
Anti-Nim 之所以
(2, 2)仍为后手胜,是因为 Nim 堆能一步从任意大小精确调整到0或1,后手可以在终局前安全破镜;而 Kayles 每次最多只打倒相邻 \(2\) 个瓶子并强行拆排,缺乏这种自由调控能力,导致(4, 5)已经是 \(\mathcal{P}\) 态,先手在(5, 5)中打掉最边缘 \(1\) 个瓶子变成(4, 5)即可致胜。 - 两条安全守则:
- 第一,对称镜像法默认只适用于 Normal Play,Misère Play 必须重新核验终局破镜能力;
- 第二,Bouton 的反常 Nim 法则(SJ 定理)不能直接套到任意带拆堆的狂野游戏上,必须验证该游戏是否温顺或用 DP / Misère Quotients 核对。
参考资料
- 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.
- 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.
- Conway, J. H. (1976). On Numbers and Games. Academic Press.
- Plambeck, T. E. (2005). Taming the wild in impartial combinatorial games. Integers, 5, #G5.
- 仓库文章同目录的
variants_verify.py:五大变种暴力 DP 对拍、Misère Kayles 反例核验与图 3 重绘脚本。
现在你已经攒齐了拆解公平博弈的全部硬武器。最后一篇我们将沉淀一张5 步现场诊断流程图,带你越过 Nim 边界看一眼红蓝不公平博弈与超实数、PSPACE 复杂性与未解难题,并用 10 道全系列闭卷通关考题帮你彻底验收:05|实战反杀手册、综合测验与超越 Nim。
源码下载
本文相关源码已整理,共 1 个文件。
文章导航
读完这篇,下一步读什么
优先读同系列或同问题的下一篇,把单篇消费变成主题集群。
【组合博弈】05|实战反杀手册、综合测验与超越 Nim:不对称博弈与开放问题
沉淀遇到陌生小游戏时的 5 步现场诊断协议,越过公平博弈边界介绍红蓝 Hackenbush 与 Conway 超实数、PSPACE 复杂性及 Grundy's Game 等未解难题,并附 10 道覆盖全系列的闭卷综合测验与 Python 核验脚本。
【组合博弈】03|万能降维武器:Sprague-Grundy 定理与 mex 的真正含义
只要游戏有限、公平且最后一步胜,任意状态都严格等价于一个特定大小的 Nim 堆。本文从博弈和与 mex 定义出发,用图解拆透 SG 等价性证明,通吃多堆减法、拆堆游戏(Lasker's Nim、Kayles)与 Green Hackenbush,附 Python 计算器与 6 道练习。
【组合博弈】系列总览:从 Nim 到 Sprague-Grundy,看穿取石子小游戏的必胜法则
系统拆解 Nim 及其经典变种的组合博弈论原理:从 P/N 态倒推、对称模仿、二进制异或配对,到 Sprague-Grundy 定理、Anti-Nim、阶梯 Nim、威佐夫、斐波那契博弈与红蓝 Hackenbush,配套图解、Python 核验脚本与分级练习。
【组合博弈】01|胜负的底层逻辑:P/N 态、倒推法与对称模仿
戒掉从开局往前推演博弈树的死路:用 Zermelo 有限决定性建立 P/N 态倒推三公理,一次讲透巴什博弈模陷阱、减法博弈周期、圆桌硬币对称模仿与 Chomp 策略盗取证明,附 Python 求解器与 5 道实战练习。