几乎每个被取石子游戏虐过的人,都听过一句让人一头雾水的结论:“把每堆石子的数量按位异或(XOR),结果不为 \(0\) 就先手赢,等于 \(0\) 就后手赢。”
这句话听起来像纯魔法:桌上摆着实实在在的三堆硬币 \((3, 5, 6)\),拿石子做的是十进制减法,凭什么和计算机底层的二进制异或扯上关系?只要没想通这层直觉,你就会一直处于“背得住公式、算不对走法、规则一变就傻眼”的状态。
本文把这层窗户纸彻底捅破:
- 用二进制筹码镜像配对解释为什么 Nim 的平衡条件恰好是按位异或为 \(0\)。
- 给出 1901 年 Bouton 定理的完整三步证明与 3 秒牌桌口算必胜步操作指南。
- 展示这个核心不变量如何直接秒杀三个看似毫无关联的变种:Poker Nim(允许往回放石子)、Northcott 棋盘推子,以及一次可以动 \(k\) 堆的 Moore’s \(\text{Nim}_k\)。
一、为什么是二进制异或?把石子拆成 \(2^k\) 面值的筹码
回想 第 01 篇 里的两堆对称游戏 \((n, n)\):如果桌上只有两堆一模一样的石子,后手只需照着先手做镜像操作就必胜。
推广一步:如果有四堆 \((5, 5, 2, 2)\),后手依然必胜——把两个 \(5\) 配成一对,两个 \(2\) 配成一对,对手碰哪一对你就镜像碰同一对的另一半。
那遇到三堆完全不相等的石子 \((3, 5, 6)\) 呢?表面上看没有任何两堆相等,对称性似乎消失了。
现在换一副眼镜:把每一堆石子按二进制拆成面值为 \(4, 2, 1\)(即 \(2^2, 2^1, 2^0\))的整捆筹码:
- 第 1 堆 \(3 = 2 +
1\)(二进制
011):一个2-筹码 + 一个1-筹码; - 第 2 堆 \(5 = 4 +
1\)(二进制
101):一个4-筹码 + 一个1-筹码; - 第 3 堆 \(6 = 4 +
2\)(二进制
110):一个4-筹码 + 一个2-筹码。
把三堆放在一起数一数每种面值的筹码总数:4-筹码有
\(2\)
个,2-筹码有 \(2\) 个,1-筹码有
\(2\) 个!
虽然整堆之间没法配对,但拆开到二进制面值这一层,每一种面值的筹码全都严格成双成对!这就是 \((3, 5, 6)\) 的异或和等于 \(0\) 的真实物理含义:
\[ 3 \oplus 5 \oplus 6 = (011)_2 \oplus (101)_2 \oplus (110)_2 = (000)_2 = 0. \]
按位异或(无进位二进制加法)只干一件事——检查每一列(每一种 \(2^j\) 面值的筹码)的总个数是不是偶数。
图 1|二进制筹码配对视角。 左侧 \((3, 5, 6)\) 在
4、2、1
三个位列上的筹码数全为偶数(\(2,
2, 2\)),处于完全平衡的 \(\mathcal{P}\) 态;右侧 \((3, 5, 7)\) 的
1-筹码多出一个孤立单身汉(总数 \(3\) 为奇数),处于失衡的 \(\mathcal{N}\)
态,先手只需拿走任意一堆里的 1
即可立刻恢复全偶配对。
你可能会追问一句关键的漏洞:“等一下!如果对手从第 3 堆
\(6\) 里只拿走 \(1\) 颗,变成了 \(5 = 4 + 1\),他相当于拆散了一个
2-筹码并凭空变出了一个
1-筹码,这不像直接拿整捆筹码那么简单啊!”
问得非常准。真正让二进制配对成立的数学杠杆,在于“最大位压制一切低位”:无论对手如何拆散低位筹码,只要他在某个最高发生变化的位 \(2^d\) 上打破了偶数平衡,你在回复时总能在唯一一堆里把那个最高的奇数位 \(2^d\) 消掉,同时把下面所有变奇数的低位(\(2^{d-1}, \dots, 2^0\))全部一次翻转调平,而且由于
\[ 2^d > 2^{d-1} + 2^{d-2} + \dots + 2^1 + 2^0 = 2^d - 1, \]
哪怕把下面所有低位全从 0 翻成
1(往这堆里补低位筹码),净结果依然是严格减少了这堆石子的数量!
这意味着你的回复永远是合法的“只拿不放”。
二、Bouton 定理(1901):三步严格证明
哈佛大学数学家 Charles L. Bouton 在 1901–1902 年的 Annals of Mathematics 论文 Nim, a game with a complete mathematical theory 中首次给出完整定理(论文顺便正式命名了 “Nim” 这个名字):
Bouton 定理:在正常规则的 \(m\) 堆 Nim 游戏 \((a_1, a_2, \dots, a_m)\) 中,令异或和(亦称 Nim-sum)为 \[ S = a_1 \oplus a_2 \oplus \dots \oplus a_m. \] 该局面为 \(\mathcal{P}\) 态(后手必胜)当且仅当 \(S = 0\);为 \(\mathcal{N}\) 态(先手必胜)当且仅当 \(S \neq 0\)。
套用 第 01 篇 的三条 \(\mathcal{P}/\mathcal{N}\) 公理,只需验证三件极其干净的事实,定理就彻底封死:
- 终局验证:所有堆都为 \(0\) 时,\(0 \oplus 0 \oplus \dots \oplus 0 = 0\),落在 \(S = 0\) 集合中。
- 从 \(S = 0\)
走任意一步,必然到达 \(S' \neq
0\)(无路可逃):
假设当前 \(a_1 \oplus \dots \oplus a_m = 0\),玩家只能修改其中唯一一堆,把 \(a_i\) 严格减小为 \(a_i' < a_i\)。由于异或满足消去律,新异或和为 \[ S' = S \oplus a_i \oplus a_i' = 0 \oplus a_i \oplus a_i' = a_i \oplus a_i'. \] 因为 \(a_i' \neq a_i\),必然有 \(a_i \oplus a_i' \neq 0\)。任何从平衡态出发的合法走法都必定打破平衡。 - 从 \(S \neq 0\)
出发,必然存在至少一步合法走法使 \(S' =
0\)(必有杀招):
设 \(S\) 在二进制下的最高1位位于第 \(d\) 位(即位权为 \(2^d\))。因为全盘所有堆在这一位异或出1,说明至少有一堆(实际有奇数堆)的二进制第 \(d\) 位也是1。任选其中一堆 \(a_i\),令目标新数量为 \[ a_i' = a_i \oplus S. \] 检查两件事:- 是否合法(严格变小)?高于第 \(d\) 位的所有位上 \(S\) 全是
0,所以 \(a_i'\) 与 \(a_i\) 在高位完全一致;在第 \(d\) 位上,\(a_i\) 是1而 \(S\) 是1,异或后 \(a_i'\) 的第 \(d\) 位变成0!因此无论第 \(d-1\) 到第 \(0\) 位怎么变,\(a_i'\) 一定严格小于 \(a_i\)(且非负)。拿走 \(a_i - a_i'\) 颗完全合法。 - 新局面是否平衡?新异或和为 \[ S' = S \oplus a_i \oplus a_i' = S \oplus a_i \oplus (a_i \oplus S) = 0. \]
- 是否合法(严格变小)?高于第 \(d\) 位的所有位上 \(S\) 全是
三条全满足,由有限博弈 \(\mathcal{P}/\mathcal{N}\) 标签的唯一性,证明结束。
三、3 秒牌桌实战:口算必胜招式的标准流程
光知道 \(S \neq 0\) 没用,坐到桌前必须在几秒内报出“从哪一堆拿走几颗”。按下面三步机械执行,绝不出错:
- 算异或和 \(S\):把各堆拆成 \(16, 8, 4, 2, 1\),把成对的 \(2^k\) 直接划掉,剩下落单的加起来就是 \(S\)。
- 盯住 \(S\) 的最高位 \(2^d\):扫一眼所有堆,随便挑一堆二进制里包含 \(2^d\) 的堆 \(a_i\)。
- 算出目标 \(a_i' = a_i \oplus S\):把 \(a_i\) 减到 \(a_i'\)(也就是拿走 \(a_i - a_i'\) 颗)。
来看一个 4 堆实战局面:\((7, 11, 14, 20)\)。
- 第 1 步(划对子算 \(S\)):
- \(7 = 4 + 2 + 1\)
- \(11 = 8 + 2 + 1\)
- \(14 = 8 + 4 + 2\)
- \(20 = 16 + 4\)
- 划对子:两个
8抵消;两个4抵消剩一个4;两个2抵消剩一个2;两个1抵消;剩一个孤单的16。于是 \(S = 16 + 4 + 2 = 22 = (10110)_2\)。
- 第 2 步(找最高位
16):只有第 4 堆 \(20\) 包含16。 - 第 3 步(翻转目标堆):\(a_4' = 20 \oplus 22 = (10100)_2
\oplus (10110)_2 = (00010)_2 = 2\)。
从第 4 堆拿走 \(20 - 2 = 18\) 颗,局面变成 \((7, 11, 14, 2)\),异或归零。
图 2|3 步找到必胜着法。 最高位
16 锁定目标堆 20;将其与 \(S=22\) 异或得到 \(2\),相当于从 20
中撤掉 16 和 4、补回
2,净减少 \(18\)
颗石子,使五列比特数全部变偶(0, 2, 2, 4, 2)。
速算小技巧:如果桌面只有 \(3\) 堆 \((a, b, c)\) 且你已经算完 \(a \oplus b = t\),根本不用再算总异或 \(S\)——只要 \(t < c\),直接把 \(c\) 减到 \(t\) 就完了!因为 \((a, b, t)\) 的异或天然等于 \(a \oplus b \oplus (a \oplus b) = 0\)。
四、三个“看起来不是 Nim”的等价变种
一旦你理解了“维护不变量 + 可逆步抵消”,下面三个经常被拿来糊弄人的游戏瞬间全透明。
变种 1:Poker Nim(允许往堆里放回石子!)
规则:和普通 Nim 一样,但双方口袋里各有无限(或有限足够多)的筹码,轮到自己时除了从某堆拿走任意颗石子外,还可以往某堆里放回任意正整数颗石子(但游戏设定防止无限僵持,例如口袋筹码有限)。
直觉会骗你:“对手可以往里加石子破坏我的计划,这游戏肯定变复杂了!”
真相:胜负判定与普通 Nim 完全一模一样,依然是 \(S = 0\) 后手必胜!
为什么?假设你已经把局面压到了 \(S = 0\)。如果对手正常拿石子,你照旧用 Bouton 策略把 \(S\) 压回 \(0\);如果对手耍赖,往第 \(i\) 堆里硬塞进 \(m\) 颗石子——你什么都不用算,立刻伸手把那 \(m\) 颗刚放进去的石子原样拿出来!
在组合博弈论里,这叫可逆走法(Reversible Move):只要你能把对手的“加料”一比一原路撤销,对手永远无法靠加石子改变胜负,他口袋里的筹码总有用光(或放弃加料)的一天。这条“原路撤销”思想极其关键,它将在 第 03 篇 用来证明 Sprague-Grundy 定理,并在 第 04 篇 用来秒杀阶梯 Nim。
变种 2:Northcott 棋盘推子游戏
规则:一个 \(m\) 行 \(n\) 列的棋盘,每一行上各有一枚白棋(在左)和一枚黑棋(在右)。白方只能在同一行水平左右移动白棋,黑方只能左右移动黑棋,棋子不能越过或撞上同行的对方棋子,无法移动者输。
看着像一个不公平的棋盘游戏?其实它就是披了马甲的 Poker Nim!
把第 \(i\) 行白棋和黑棋之间的空格数记作 \(g_i\):
- 如果你把自己的棋子向对方逼近 \(d\) 格,空格数 \(g_i\) 减少 \(d\)——这完全等价于从第 \(i\) 堆拿走 \(d\) 颗石子;
- 如果你把自己的棋子向后撤退 \(d\) 格,空格数 \(g_i\) 增加 \(d\)——这等价于 Poker Nim 里往第 \(i\) 堆放回 \(d\) 颗石子!对手只需同步前进 \(d\) 格把空格重新缩回 \(g_i\),而棋盘宽度有限,你退到墙角就无路可退了。
因此,Northcott 游戏的必胜条件就是把每行两棋之间的空格数异或起来:\(g_1 \oplus g_2 \oplus \dots \oplus g_m \neq 0\) 先手必胜!
变种 3:Moore’s \(\text{Nim}_k\)(一次最多可以动 \(k\) 堆!)
规则:E. H. Moore 在 1910 年的 Annals of Mathematics 短文 A generalization of the game called nim 中把 Nim 推进了一大步——桌上仍有 \(m\) 堆石子,但每回合玩家可以选择 \(1\) 到 \(k\) 个不同的石子堆(\(1 \le k < m\)),从选中的每一堆里各自拿走任意正整数颗石子,取走最后一颗者胜。
当 \(k = 1\) 时就是普通 Nim。现在改成 \(k = 2\)(一次最多同时动 \(2\) 堆),异或显然不够用了:比如 \((3, 3)\) 在普通 Nim 里是后手胜,但在 \(\text{Nim}_2\) 里先手一把把两堆全清空直接秒赢!
怎么把“筹码配对”推广到一次可动 \(k\) 堆?
- \(k = 1\) 时,每次动 \(1\) 堆,所以用 2 堆凑成一对(按位模 \(2\));
- \(k = 2\) 时,每次最多动 \(2\) 堆,要想让对手无论怎么动 \(1\) 堆或 \(2\) 堆都必然打破平衡,就需要 3 堆凑成一组(按位模 \(3\))!
一般结论就是 Moore 定理(1910):
在 \(\text{Nim}_k\) 中,把每一堆石子写成二进制,分别对每一个二进制位列求和(普通十进制加法)。局面是 \(\mathcal{P}\) 态,当且仅当每一个二进制位列的和都能被 \(k + 1\) 整除!
图 3|Moore’s \(\text{Nim}_2\)(\(k=2\),模 \(3\) 平衡)。 局面 \((2, 5, 6, 7)\) 的三个二进制位列之和分别为 \(3, 3, 2\),最低位余 \(2 \neq 0\);先手在同一回合同时将 \(5 \to 4\) 且 \(7 \to 6\),一步把三列和调成 \((3, 3, 0) \equiv (0, 0, 0) \pmod 3\)。
为什么对手从全 \(0
\pmod{k+1}\) 的状态走一步一定破功?因为对手最多只能动
\(k\)
堆,在他动过的最高发生变化的二进制位列上,那些被改变的堆全都从
1 变成了
0(因为每个被改动的堆严格变小,在其最高变化位上只能是
1 -> 0),所以这一列的和减少了 \(r \in \{1, 2, \dots,
k\}\)。一个 \(k+1\)
的倍数减去 \(1\text{–}k\)
之间的数,绝不可能仍是 \(k+1\) 的倍数!
反过来,从非平衡态构造还原步的算法也非常优雅:从最高位往低位扫描,维护一个“已承诺要修改的堆集合 \(C\)”(初始为空,始终保持 \(|C| \le k\)):
- 遇到当前位列的 \(1\) 的个数模 \(k+1\) 余 \(r\)(\(0 \le r \le k\));
- 已在集合 \(C\)
中的堆,因为已经在更高位从
1翻成了0,此时在当前位上可以任意决定改成0还是1(不会破坏变小条件!); - 利用 \(C\)
中已有堆的自由翻转空间,如果不够把余数消掉,再从当前位为
1且不在 \(C\) 中的堆里补选若干堆加入 \(C\) 把它们的当前位翻成0;可以证明整个过程选入 \(C\) 的总堆数永远不超过 \(k\)!
五、Python 交叉验证(含暴力 DP 对拍)
为防止纸笔直觉漏掉边界,我们在仓库文章同目录的
nim_verify.py 中用暴力动态规划对 Moore’s \(\text{Nim}_2\) 的所有 \(6^4 = 1296\)
个状态做了全量对拍,并核验了本文全部例题与习题。执行
python post/combinatorial-games/02-nim-and-xor-intuition/nim_verify.py
的真实输出(经删减)如下:
=== 1. Worked Examples ===
piles=(3, 5, 6) -> XOR=0 (00000), moves=[]
piles=(3, 5, 7) -> XOR=1 (00001), moves=[(0, 3, 2), (1, 5, 4), (2, 7, 6)]
piles=(5, 9, 13) -> XOR=1 (00001), moves=[(0, 5, 4), (1, 9, 8), (2, 13, 12)]
piles=(7, 11, 14, 20) -> XOR=22 (10110), moves=[(3, 20, 2)]
=== 2. Moore's Nim_k Verification ===
Moore's Nim_2 DP vs formula: 1296 states checked, 0 mismatches.
Moore Nim_2 (2, 5, 6, 7): is_P=False, win moves=[(2, 4, 6, 6)]
1296 个四堆状态上,暴力 DP 与 Moore 按位模 3 公式的误差为 0。
六、课后练习(练出 3 秒口算肌肉记忆)
练习 1(热身):三堆基础口算
标准 Nim,局面为 \((4, 7, 10)\)。谁必胜?写出全部必胜第一步。
参考解答与思路(先独立推导再展开)
二进制分解:\(4 =
(0100)_2\),\(7 =
(0111)_2\),\(10 =
(1010)_2\)。
异或和 \(S = 4 \oplus 7 \oplus 10
= (1001)_2 = 9 \neq
0\),先手必胜。
最高 1 位是 8,只有第 3 堆 \(10\) 含有
8,因此唯一必胜招式是将 \(10\) 减到 \(10 \oplus 9 = 3\)(从第 3
堆拿走 \(7\)
颗,留下 \((4, 7,
3)\),验证 \(4 \oplus 7 =
3\))。
练习 2(多解):四堆定位所有必胜步
标准 Nim,局面为 \((6, 9, 12, 15)\)。请问共有几种必胜第一步?全部列出来。
参考解答与思路(先独立推导再展开)
二进制:\(6 =
(0110)_2\),\(9 =
(1001)_2\),\(12 =
(1100)_2\),\(15 =
(1111)_2\)。
逐位异或:
- 位
8:\(0 + 1 + 1 + 1 = 3 \to 1\) - 位
4:\(1 + 0 + 1 + 1 = 3 \to 1\) - 位
2:\(1 + 0 + 0 + 1 = 2 \to 0\) - 位
1:\(0 + 1 + 0 + 1 = 2 \to 0\)
得 \(S = (1100)_2 =
12\)。最高 1 位是
8,共有三堆(\(9, 12, 15\))包含位
8,因此有 3 种必胜第一步:
- 把 \(9\) 变为 \(9 \oplus 12 = 5\)(拿走 \(4\) 颗);
- 把 \(12\) 变为 \(12 \oplus 12 = 0\)(整堆拿光 \(12\) 颗);
- 把 \(15\) 变为 \(15 \oplus 12 = 3\)(拿走 \(12\) 颗)。
练习 3(避坑):为什么不是所有堆都能变小?
标准 Nim,局面为 \((11, 14, 19, 25)\)。计算异或和 \(S\),并判断能否通过修改第 3 堆 \(19\) 来获胜。
参考解答与思路(先独立推导再展开)
二进制:
- \(11 = (01011)_2\)
- \(14 = (01110)_2\)
- \(19 = (10011)_2\)
- \(25 = (11001)_2\)
计算 \(S = 11 \oplus 14 \oplus
19 \oplus 25 = (01111)_2 = 15\)。
注意最高 1 位是
8(不是 16,因为
\(19\) 和 \(25\) 里的两个 16
互相抵消了!)。
检查第 3 堆 \(19 = 16 + 2 +
1\),它的第 8 位是
0,如果硬算 \(19
\oplus 15 = 28 >
19\),需要往堆里加石子,不合法!
真正包含位 8 的是 \(11, 14, 25\),对应的 3
种合法必胜步为:\(11 \to
4\)(拿 \(7\))、\(14 \to 1\)(拿 \(13\))、\(25 \to 22\)(拿 \(3\))。
练习 4(陷阱局):要不要抢先手?
对手摆出四堆 \((3, 8, 12, 7)\) 并假装大方地说:“让你先拿!”你应该接受先手还是让给对方?
参考解答与思路(先独立推导再展开)
立刻识破陷阱!拆分验证:
- \(3 = 2 + 1\)
- \(7 = 4 + 2 + 1\)
- \(8 = 8\)
- \(12 = 8 + 4\)
两个 8、两个 4、两个
2、两个 1 全部精准配对,\(S = 3 \oplus 8 \oplus 12 \oplus 7 =
0\)!
这是标准的 \(\mathcal{P}\)
态,应该果断拒绝先手,让对方先动。
练习 5(棋盘马甲):Northcott 游戏判断
一个 4 行 9 列(列号 0..8)的 Northcott
棋盘,每行白棋(W)和黑棋(B)位置如下:
- 第 1 行:W 在
1,B 在6 - 第 2 行:W 在
2,B 在5 - 第 3 行:W 在
0,B 在8 - 第 4 行:W 在
3,B 在5
先手必胜还是后手必胜?如果先手试图把第 3 行的己方棋子往后退两格拉大间距,后手怎么应对?
参考解答与思路(先独立推导再展开)
计算每行两棋之间的空格数(注意是不含两棋本身,即
col_B - col_W - 1):
- 第 1 行:\(6 - 1 - 1 = 4\)
- 第 2 行:\(5 - 2 - 1 = 2\)
- 第 3 行:\(8 - 0 - 1 = 7\)
- 第 4 行:\(5 - 3 - 1 = 1\)
空格数组为 \((4, 2, 7,
1)\),计算异或和:\(4
\oplus 2 \oplus 7 \oplus 1 = 6 \oplus 6 =
0\),因此后手必胜!
若先手把第 3 行后退 \(2\)
格(相当于 Poker Nim 加回 \(2\) 颗石子),后手只需把第 3
行己方棋子紧跟着前进 \(2\)
格,瞬间把空格数还原回 \(7\),同时把对手又逼近墙角两格。
练习 6(高阶):Moore’s \(\text{Nim}_2\) 一招调平
规则改为每次最多可动 \(2\) 堆(\(\text{Nim}_2\)),当前四堆为 \((4, 5, 6, 7)\)。请问该局面是 \(\mathcal{P}\) 态还是 \(\mathcal{N}\) 态?请找出一种只改动 \(1\) 堆就能获胜的走法,再找出一种同时改动 \(2\) 堆的获胜走法。
参考解答与思路(先独立推导再展开)
列出二进制位列并按列相加:
- \(4 = (100)_2\)
- \(5 = (101)_2\)
- \(6 = (110)_2\)
- \(7 = (111)_2\)
三列之和为 (4, 2, 2),模 \(3\) 余
(1, 2, 2),不全为 \(0\),故为 \(\mathcal{N}\)
态(先手必胜)。
- 只动 \(1\)
堆的妙手:把 \(4 =
(100)_2\) 减为 \(3 =
(011)_2\)(拿走 \(1\) 颗)!第
4位减 \(1\)、第2位加 \(1\)、第1位加 \(1\),三列之和奇迹般地从(4, 2, 2)一步变成(3, 3, 3),全部整除 \(3\)!新局面为 \((3, 5, 6, 7)\)。 - 同时动 \(2\)
堆的走法(例如):将 \(5
\to 2\) 且 \(7 \to
6\),得到 \((4, 2, 6,
6)\),二进制
(100, 010, 110, 110),三列之和为(3, 3, 0),同样全部整除 \(3\)(另两种合法解为 \((4, 5, 1, 5)\) 与 \((4, 5, 5, 1)\))。
参考资料
- Bouton, C. L. (1901–1902). Nim, a game with a complete mathematical theory. Annals of Mathematics, 3(1/4), 35–39.
- Moore, E. H. (1910). A generalization of the game called nim. Annals of Mathematics, 11(2), 93–94.
- Berlekamp, E. R., Conway, J. H., & Guy, R. K. (1982). Winning Ways for Your Mathematical Plays (Vol. 1, Ch. 3). Academic Press.
- 仓库文章同目录的
nim_verify.py:Bouton / Moore’s \(\text{Nim}_k\) 暴力 DP 对拍与全量练习核验脚本。
下一篇我们祭出组合博弈论的终极统一核武器——只要游戏能拆成独立子游戏,不管规则怎么魔改,都能压缩回异或:03|万能降维武器:Sprague-Grundy 定理与 mex 的真正含义。
源码下载
本文相关源码已整理,共 1 个文件。
文章导航
读完这篇,下一步读什么
优先读同系列或同问题的下一篇,把单篇消费变成主题集群。
【组合博弈】03|万能降维武器:Sprague-Grundy 定理与 mex 的真正含义
只要游戏有限、公平且最后一步胜,任意状态都严格等价于一个特定大小的 Nim 堆。本文从博弈和与 mex 定义出发,用图解拆透 SG 等价性证明,通吃多堆减法、拆堆游戏(Lasker's Nim、Kayles)与 Green Hackenbush,附 Python 计算器与 6 道练习。
【组合博弈】01|胜负的底层逻辑:P/N 态、倒推法与对称模仿
戒掉从开局往前推演博弈树的死路:用 Zermelo 有限决定性建立 P/N 态倒推三公理,一次讲透巴什博弈模陷阱、减法博弈周期、圆桌硬币对称模仿与 Chomp 策略盗取证明,附 Python 求解器与 5 道实战练习。
【组合博弈】05|实战反杀手册、综合测验与超越 Nim:不对称博弈与开放问题
沉淀遇到陌生小游戏时的 5 步现场诊断协议,越过公平博弈边界介绍红蓝 Hackenbush 与 Conway 超实数、PSPACE 复杂性及 Grundy's Game 等未解难题,并附 10 道覆盖全系列的闭卷综合测验与 Python 核验脚本。
【组合博弈】系列总览:从 Nim 到 Sprague-Grundy,看穿取石子小游戏的必胜法则
系统拆解 Nim 及其经典变种的组合博弈论原理:从 P/N 态倒推、对称模仿、二进制异或配对,到 Sprague-Grundy 定理、Anti-Nim、阶梯 Nim、威佐夫、斐波那契博弈与红蓝 Hackenbush,配套图解、Python 核验脚本与分级练习。