combinatorial-game-theory 标签归档

共 6 篇文章 · 返回首页

【组合博弈】03|万能降维武器:Sprague-Grundy 定理与 mex 的真正含义

只要游戏有限、公平且最后一步胜,任意状态都严格等价于一个特定大小的 Nim 堆。本文从博弈和与 mex 定义出发,用图解拆透 SG 等价性证明,通吃多堆减法、拆堆游戏(Lasker's Nim、Kayles)与 Green Hackenbush,附 Python 计算器与 6 道练习。

【组合博弈】04|那些专门坑人的变种:Anti-Nim、阶梯 Nim、威佐夫与斐波那契

对手发现你懂异或后最爱改的五种阴招:拿最后一颗算输(Anti-Nim 与 Misere Kayles 反例)、阶梯移硬币、两堆同步取(威佐夫黄金分割)、动态 2 倍上限(斐波那契 Zeckendorf)与翻硬币游戏,附暴力 DP 全量核验与 6 道练习。

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

系统拆解 Nim 及其经典变种的组合博弈论原理:从 P/N 态倒推、对称模仿、二进制异或配对,到 Sprague-Grundy 定理、Anti-Nim、阶梯 Nim、威佐夫、斐波那契博弈与红蓝 Hackenbush,配套图解、Python 核验脚本与分级练习。