内容提要
本文介绍Sprague-Grundy定理:用mex递归为每个博弈状态赋予SG值,多组件博弈的胜负由各SG值的异或和是否为零决定,从而将各类公平游戏统一化为Nim。文中讲解定理的证明思路,并分析减法博弈、拆堆博弈(Lasker's Nim、Kayles、Grundy's Game)及Green Hackenbush的冒号原理,附有Python计算器与练习题。
延伸解读
SG 值:不止于胜负标签
文章强调 SG 值比 P/N 二值标签携带更多信息。例如减法博弈 S={1,3,4} 中,n=4 和 n=5 单独都是 N 态,但 SG 值分别为 2 和 3,组合 (4,5) 异或非零先手必胜;而 n=4 和 n=6 的 SG 值同为 2,组合 (4,6) 异或为零后手必胜。这说明 SG 值能精确刻画状态在组合中的等价性,而 P/N 标签无法区分不同 N 态之间的差异。
拆堆游戏:一行公式的统一处理
对于一步将一堆拆成两堆的拆堆游戏,文章指出只需将拆后两子堆的 SG 值异或后放入 mex 集合。Lasker’s Nim 的 SG 序列呈现 4k+3 与 4k+4 互换的规律;Kayles 的 SG 序列直到 n=71 后才进入 12 周期,警示不能仅凭前几项草率下结论;Grundy’s Game 则至今未发现周期,是著名开放问题。这体现了 SG 框架的通用性,也提醒周期检测需谨慎。
Green Hackenbush 与冒号原理
树形 Green Hackenbush 的 SG 值可通过冒号原理递归计算:每个子节点 SG 值加 1 后按位异或。文章用竹竿和分叉树示例说明,长为 L 的竹竿等价于大小为 L 的 Nim 堆,分叉树可合并为等效竹竿。这展示了 SG 定理如何将看似无关的图论游戏转化为 Nim 堆,进一步印证其作为“万能降维武器”的威力。
Q&A
Sprague-Grundy 定理的核心结论是什么?
任何有限、公平、正常规则下的单组件局面 G 都等价于一个大小为 g(G) 的 Nim 堆,其中 g(G) 是 G 的 SG 值。多个组件的析取和是 P 态当且仅当所有组件的 SG 值异或和为 0。
mex 函数在 SG 值计算中起什么作用?为什么这样定义?
mex 返回不在后继状态 SG 值集合中的最小非负整数。这样定义是为了保证在证明 G + *k 为 P 态时,后手能应对对手的三种走法:若对手减小 Nim 堆,后手可在 G 中走到对应 SG 值;若对手使 G 的 SG 值变小,后手可减小 Nim 堆;若对手使 G 的 SG 值变大,后手可利用 mex 定义将 G 的 SG 值降回 k。
如何用 SG 定理分析减法博弈?例如每次只能拿 1、3 或 4 颗石子。
先计算单堆的 SG 值序列。对于 S={1,3,4},SG 值周期为 7,循环节为 [0,1,0,1,2,3,2]。多堆局面的胜负由各堆 SG 值的异或和决定:非零则先手必胜,为零则后手必胜。
拆堆游戏(如 Lasker's Nim、Kayles、Grundy's Game)的 SG 值如何计算?
拆堆时,一步操作将一堆拆成两堆 a 和 b,后继局面的 SG 值为 g(a) ⊕ g(b)。因此计算 SG 值时,需要将所有可能的拿石子后的 SG 值以及所有拆堆后的异或值放入 mex 集合中。
Green Hackenbush 的冒号原理是什么?如何计算树形结构的 SG 值?
冒号原理指出,对于树形 Green Hackenbush,节点 u 的 SG 值等于其所有子节点 c_i 的 (g(c_i)+1) 的异或和。即 g(u) = ⊕ (g(c_i)+1)。叶子节点 SG 值为 0。整片森林的总 SG 值为各棵树 SG 值的异或和。
Kayles 游戏的 SG 序列有什么特殊性质?
Kayles 的 SG 序列在前 70 项看起来没有规律,但从 n=71 开始进入严格的 12 周期循环。最后一个反常点是 n=70(g(70)=6 而 g(82)=2)。这提醒我们不要仅凭前几项就草率下结论。