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

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

💡 原文中文,约5900字,阅读约需14分钟。
📝

内容提要

本系列共五篇,总览取石子类双人完全信息组合博弈:以P/N态倒推、Nim异或、Sprague-Grundy定理与mex值将各类变种归约为Nim求解,并介绍Anti-Nim、阶梯Nim、威佐夫、斐波那契等变种,最后给出五步诊断流程、超实数与复杂性边界;每篇附Python核验脚本和练习题。

🔎

延伸解读

从“往前推”到“倒推贴标签”的思维转换

文章指出多数人面对取石子游戏会陷入往前推演博弈树的陷阱,三步后分支爆炸。系列的核心方法是从终局倒推,给每个状态贴“先手必胜(N)”或“后手必胜(P)”标签,再结合对称配对与策略盗取直接定性。这种转换把指数级搜索变成局部判断,是后续异或、SG值等工具的基础。读者可先掌握P/N倒推三公理,再进入具体变种。

异或口诀为何失效:前提被破坏时先找分叉点

文章强调Nim异或公式依赖正常终局等前提,规则微调后口诀立刻失效。拆解变种的关键是分清破坏了哪条前提:Anti-Nim只改变终局,仅在进入全1残局的唯一分叉点改口;阶梯Nim用偶数阶镜像抵消;威佐夫博弈因两堆耦合落到黄金分割射线。这种“先定位前提破坏点”的思路,比死记公式更能应对新规则。

SG定理的适用边界与反例警示

Sprague-Grundy定理将满足有限、公平、正常规则的单组件状态等价为Nim堆,多个独立组件直接异或。但文章特别用Misère Kayles的(5,5)反例标明Anti-Nim规则何时彻底失效,说明SG框架并非无条件适用。读者应记住:先检查游戏是否满足定理前提,再决定是否套用mex与异或,否则可能得出错误结论。

按目标选阅读路径,避免陷入理论细节

系列提供四条路径:零基础按01到05系统通关;桌游或面试救急可读01、02、04速查;算法竞赛向侧重02、03、05的SG记忆化与复杂性边界;数学理论延伸则关注03的等价性证明、04的反例与05的超实数。读者可根据自身需求选择,不必每篇都精读,但每篇的Python脚本和练习题是核验理解的关键工具。

❓

Q&A

为什么在取石子游戏中,从开局往前推演博弈树容易晕,而高手能一眼判断胜负?

因为博弈树应该从终局倒推,而不是从开局前推。给每个状态贴上“先手必胜(N)”或“后手必胜(P)”标签,结合对称配对与策略盗取,就能在不展开整棵树的情况下直接定性。

Nim游戏中,异或(XOR)为什么能决定胜负?

把每堆石子拆成2^k面值的二进制筹码,异或为0等价于每种面值的筹码都成双配对。Bouton在1901年给出的异或公式正是基于这种配对思想,因此能快速口算必胜步。

Sprague-Grundy定理如何将各种取石子游戏统一归约为Nim?

Sprague和Grundy证明:只要游戏满足有限、公平、正常规则(最后一步赢),任何单组件状态都等价于一个特定大小的Nim堆,其大小是递归计算的mex值(SG值)。多个独立组件拼合时,将各组件SG值异或即可。

当规则改为“拿最后一颗算输”时,Nim的异或策略如何调整?

这是Anti-Nim(Misère Nim)变种。它破坏了正常终局条件,但只需在进入全1残局的唯一分叉点调整策略:若所有堆大小均为1,则根据堆数奇偶决定胜负;否则仍按正常Nim异或策略,但需避免留给对手全1残局。

遇到一个从未见过的取石子小游戏,应该按什么步骤排查必胜策略?

系列给出5步现场诊断流程:1. 确认游戏是否有限、公平、正常规则;2. 尝试用P/N态倒推或对称配对;3. 若可分解为独立组件,计算各组件SG值并异或;4. 识别是否属于已知变种(如Anti-Nim、阶梯Nim等);5. 若规则破坏公平性,考虑超实数等扩展理论。

公平组合博弈理论的边界在哪里?有哪些未解难题?

边界包括:当双方可执行动作不同(不公平博弈,如红蓝Hackenbush),局面值需用Conway超实数表示;计算复杂性上,许多公平博弈是PSPACE完全的;此外,Grundy's Game的周期性等仍是开放问题。

🏷️

标签

➡️

继续阅读