【组合博弈】02|Nim 与异或的直觉:为什么二进制按位相加能支配石子堆?

【组合博弈】02|Nim 与异或的直觉:为什么二进制按位相加能支配石子堆?

💡 原文中文,约11800字,阅读约需29分钟。
📝

内容提要

本文阐述Nim取石子游戏中“异或和为零则后手必胜”的原理:将每堆石子按二进制拆为2的幂次筹码,异或和为零即每种面值筹码成对出现,构成镜像对称。文章给出Bouton定理的三步证明,并提供三步口算必胜走法,还说明Poker Nim、Northcott棋盘游戏和Moore's Nim_k等变种可由同一不变量统一处理,并用Python暴力DP验证。

🔎

延伸解读

二进制配对:异或为零的物理意义

文章将每堆石子拆成2的幂次筹码,异或和为零意味着每种面值的筹码总数均为偶数,形成镜像配对。这解释了为何(3,5,6)虽无相等堆却后手必胜。关键杠杆是“最大位压制一切低位”:对手打破平衡后,你总能在唯一一堆中消去最高奇数位并翻转低位,且净减少石子数,保证回复合法。

Bouton定理的三步证明逻辑

证明依赖P/N态三公理:终局异或为零;从零态走一步必破坏平衡(因修改一堆导致异或非零);从非零态取最高位d,选含该位的堆a_i,令a_i' = a_i ⊕ S,可证a_i' < a_i且新异或为零。这提供了构造性必胜策略,而非仅判定胜负。

变种统一:不变量与可逆走法

Poker Nim允许放回石子,但对手加料时可原路撤销,胜负不变;Northcott棋盘游戏将空格数视为石子堆,后退等价于放回,前进等价于拿走;Moore's Nim_k一次可动k堆,平衡条件变为各二进制位列和模k+1为零。三者均通过维护不变量和可逆步抵消来统一处理。

实战口算与验证要点

三步口算:算异或和S(划对子)、找S最高位2^d、选含该位的堆a_i并减至a_i⊕S。注意并非所有堆都能变小,如练习3中19不含最高位8,硬算会需加石子不合法。文章用Python暴力DP对Moore's Nim_2的1296个状态全量对拍,公式与DP零误差,增强结论可信度。

❓

Q&A

为什么Nim游戏中判断胜负要用异或,而不是普通的加法或减法?

因为异或运算(无进位二进制加法)能检查每种二进制位(2的幂次)上的筹码总数是否为偶数。将每堆石子拆成二进制筹码后,异或和为零意味着所有面值的筹码都成对出现,形成镜像对称,后手可以模仿先手保持平衡。

Bouton定理的内容是什么?它如何证明?

Bouton定理指出:在正常规则的Nim游戏中,异或和S=0时后手必胜(P态),S≠0时先手必胜(N态)。证明分三步:1) 终局所有堆为0时S=0;2) 从S=0走任意一步必使S'≠0;3) 从S≠0出发,总能找到一步使S'=0(取最高位1的堆,将其减至a_i⊕S)。

在Nim游戏中,给定一个局面,如何快速找到必胜的第一步?

三步口算:1) 计算所有堆的异或和S;2) 找到S的最高位1(2^d),并选一堆二进制中包含该位的堆a_i;3) 计算目标a_i' = a_i ⊕ S,从该堆拿走a_i - a_i'颗。例如(7,11,14,20)的S=22,最高位16只在20中,20⊕22=2,故从20拿18颗。

Poker Nim允许放回石子,为什么胜负判定和普通Nim一样?

因为放回石子是一种可逆走法:如果对手往某堆放回m颗,你可以立即拿走同样的m颗,恢复原状。这样对手无法通过放回石子改变异或和为零的平衡状态,最终仍会因无法行动而输。

Northcott棋盘游戏如何转化为Nim?

将每行白棋和黑棋之间的空格数视为一堆石子。向对方移动棋子减少空格相当于取走石子;向后移动增加空格相当于放回石子(Poker Nim)。因此计算所有行空格数的异或和,非零则先手必胜。

Moore's Nim_k中,一次可以动最多k堆,胜负条件是什么?

将每堆石子写成二进制,对每个二进制位分别求和(十进制),若每个位的和都能被k+1整除,则后手必胜;否则先手必胜。例如k=2时,需所有位和模3为0。

🏷️

标签

➡️

继续阅读