那些专门坑人的变种:Anti-Nim、阶梯 Nim、威佐夫与斐波那契

目录

当你刚学会 第 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. 存在至少一堆大小 \(> 1\),且 \(S \neq 0\);
  2. 所有堆大小都 \(\le 1\),且 \(S = 0\)(即大小为 \(1\) 的堆有偶数个)。

核心直觉只有一句话:只要场上还有至少两堆大于 \(1\),反常 Nim 的打法与普通 Nim 100% 一模一样!唯一需要变招的,只有全场刚刚剩下“恰好一堆大于 \(1\)”的那一瞬间!

普通 Nim 与反常 Nim 在唯一残局分叉点上的策略对照

图 1|Anti-Nim 的唯一残局分叉点。 只要你一直维持 \(S = 0\),场上就不可能出现“恰好一堆 \(> 1\)”(因为唯一大于 \(1\) 的堆在更高比特位上无人配对,异或绝不可能为 \(0\))。所以一定是对手被迫打出“恰好一堆 \(> 1\)”的局面交到你手里!此时你拥有绝对的奇偶控制权——你可以把那个唯一的大堆缩成 0 或缩成 1,精确控制场上最终剩下奇数个 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}\)(后手胜!)

这一组数字同时炸毁了两个直觉陷阱:

  1. 在反常规则下,连完全对称的 (5, 5) 都不一定是后手胜! 先手只需打倒一排最边缘的 \(1\) 个瓶子,把 (5, 5) 变成 (4, 5),就把真正的 \(\mathcal{P}\) 态塞给了对手(因为如果后手在 (5, 5) 里盲目镜像模仿,镜像模仿会让后手自己拿走最后一个瓶子直接自杀!)。
  2. 普通 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 学过的“原路抵消”思想:

阶梯 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\),轮到对手走,只有两种可能:

  1. 对手把 \(m\) 枚硬币从某个奇数阶 \(2k-1\) 推到偶数阶 \(2k-2\):
    由于偶数阶是透明垃圾桶,这一步在奇数阶视角里就是从第 \(2k-1\) 堆标准地拿走了 \(m\) 颗石子!你按普通 Nim 的 Bouton 策略,从某个奇数阶推走相应数量的硬币到它下面的偶数阶,立刻把奇数阶异或再次归零。
  2. 对手把 \(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)\)。每回合有两种合法走法:

  1. 从任意一堆中取走任意正整数颗石子;
  2. 从两堆中同时取走相同数量 \(d \ge 1\) 颗石子。

拿走最后一颗者胜(也可以等价地想象成国际象棋棋盘上的一枚皇后,从坐标 \((a, b)\) 每次只能向左、向下、或向左下 \(45^\circ\) 对角线走任意格,先走到原点 \((0, 0)\) 者胜)。

因为允许两堆同时减 \(d\),两堆不再是独立析取和,SG 异或不能直接拆分两堆。我们按 第 01 篇 的思路,把对称的 \((a, b)\)(不妨设 \(a \le b\))中所有 \(\mathcal{P}\) 态(Wythoff 称之为冷态 Cold Positions)从小到大手工列出来:

前 \(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. \]

威佐夫博弈在 25x25 网格上的所有 P 态分布与黄金分割射线(matplotlib 生成)

图 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\):

  1. 算差值 \(k = b - a\),再算 \(a^* = \lfloor k \times 1.618034 \rfloor\);
  2. 若 \(a = a^*\):就是 \(\mathcal{P}\) 态(后手必胜);
  3. 若 \(a > a^*\):两堆同时拿走 \(a - a^*\) 颗,一步沿对角线落入冷态 \((a^*, a^* + k)\)!
  4. 若 \(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\) 颗石子。

动态上限让状态空间变成二维 (剩余石子 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. \]

斐波那契博弈 n=20 的 Zeckendorf 分解与 2 倍上限防火墙图解

图 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\) 走一遍全流程,你就能一眼看透证明的精髓:

  1. 先手拿走最小项 \(F_3 = 2\),剩下 \(13 + 5 = 18\),并把对手的上限锁死在 \(2 \times 2 = 4\)。
  2. 因为 \(4 < 5\),对手绝对不可能一把吞光 \(5\)-区块,更别说摸到后面的 \(13\)-区块!
  3. 所以从对手视角看,他被迫在一个独立的、大小为 \(F_5 = 5\) 的斐波那契子游戏里先手行动(且上限 \(< 5\))。由归纳法,既然 \(F_5 = 5\) 本身是个 \(\mathcal{P}\) 态,你一定能成为亲手收掉 \(5\)-区块最后一颗石子的人!
  4. 还有一个精妙细节:当你收掉 \(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\)-区块以内!
  5. 接着对手又被迫在 \(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\) 也翻一面(正面变反面、反面变正面都可以)。所有硬币都变成反面时游戏结束,最后操作者胜。

乍看之下翻两枚硬币会互相影响,但用二进制视角一秒破案:

结论无比简洁: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):只有一堆 \(> 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):差值 \(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\),不是冷态,先手必胜!三种必胜步分别对应“同时减、只减小堆、只减大堆”三个方向:
    1. 两堆同时减 \(6\):\((10, 13) \to (4, 7)\)(命中 \(k = 3\) 号冷态);
    2. 只把 \(10\) 减到 \(8\):\((10, 13) \to (8, 13)\)(命中 \(k = 5\) 号冷态,因为 \(\lfloor 5\phi \rfloor = 8,\ 8+5=13\));
    3. 只把 \(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\):\(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 规则时的安全守则?

参考解答与思路(先独立推导再展开)
  1. 镜像为什么失效:在正常规则下,镜像模仿保证后手走出全盘最后一步从而获胜;但在反常规则下,走出最后一步的人判负,镜像反而会让后手自毁。纯 Anti-Nim 之所以 (2, 2) 仍为后手胜,是因为 Nim 堆能一步从任意大小精确调整到 0 或 1,后手可以在终局前安全破镜;而 Kayles 每次最多只打倒相邻 \(2\) 个瓶子并强行拆排,缺乏这种自由调控能力,导致 (4, 5) 已经是 \(\mathcal{P}\) 态,先手在 (5, 5) 中打掉最边缘 \(1\) 个瓶子变成 (4, 5) 即可致胜。
  2. 两条安全守则:
    • 第一,对称镜像法默认只适用于 Normal Play,Misère Play 必须重新核验终局破镜能力;
    • 第二,Bouton 的反常 Nim 法则(SJ 定理)不能直接套到任意带拆堆的狂野游戏上,必须验证该游戏是否温顺或用 DP / Misère Quotients 核对。

参考资料

现在你已经攒齐了拆解公平博弈的全部硬武器。最后一篇我们将沉淀一张5 步现场诊断流程图,带你越过 Nim 边界看一眼红蓝不公平博弈与超实数、PSPACE 复杂性与未解难题,并用 10 道全系列闭卷通关考题帮你彻底验收:05|实战反杀手册、综合测验与超越 Nim。

源码下载

本文相关源码已整理,共 1 个文件。

打开下载目录 →

文章导航

分类入口
algorithms
标签入口
#combinatorial-game-theory#misere-nim#staircase-nim#wythoff#fibonacci-nim#turning-turtles#zeckendorf

读完这篇,下一步读什么

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


By .