饭桌上有人抓一把硬币放在面前:“20 枚硬币,每次拿 1 到 3 枚,谁拿走最后一枚谁赢,你先还是我先?”
如果你顺着直觉往前想:“我拿 2 枚剩 18,他要是拿 3 枚剩 15,我再拿……”不出三轮,分支已经炸成几十条路径,大脑直接过载;对手却像开了透视挂一样,无论你拿几枚都能稳稳收走最后一颗。
被这类小游戏反复拿捏,根本原因不在算力不够,而在方向搞反了。组合博弈论(Combinatorial Game Theory, CGT)看穿小游戏的第一步,是把整棵博弈树反过来:不从开局往下猜,而从必死的终局往回贴标签。
本文解决三件事:
- 把一类“有唯一必胜方”的小游戏框定清楚,用倒推法(Backward Induction)给每个状态贴上 \(\mathcal{P}\) / \(\mathcal{N}\) 标签。
- 用这套标签工具直接拆解巴什博弈(Bash Game)和任意减法博弈(Subtraction Game),不再死背取模公式。
- 掌握两把不用算任何数字就能秒杀对手的武器:对称模仿(Tweedledum-Tweedledee)与策略盗取(Strategy Stealing),并指出策略盗取的构造性局限。
一、先定边界:我们讨论的是哪一类游戏
不是所有双人游戏都存在“先手必胜或后手必胜”的确定结论(例如石头剪刀布依赖随机混合策略,德州扑克有隐藏手牌)。本系列前四篇聚焦于组合博弈论里最经典的一类模型——有限、公平、正常规则博弈(Finite Impartial Normal-Play Games),它满足五条明确假设:
- 双人轮流行动:两人交替操作,不存在同时出手。
- 完全信息且无随机性:棋盘完全公开,不掷骰子、不抽盲牌。
- 有限终止(Ending Condition):无论双方怎么走,游戏总在有限步内结束,不可能陷入无限循环。
- 公平性(Impartial):在任意给定局面 \(x\),先手和后手可用的合法走法集合完全相同(只取决于局面,不取决于“轮到谁”)。取石子、翻硬币都属于公平博弈;象棋、围棋因红黑/黑白各走各子,属于不公平博弈(Partizan Games),我们在 第 05 篇 再专门讨论。
- 正常规则(Normal Play):轮到谁走时如果已经无路可走(到达终局),则该玩家判负——换言之,走出最后一步的人获胜。反过来,如果规定“走出最后一步的人判负”,称为反常规则(Misère Play),我们会在 第 04 篇 重点拆解。
在上述前三条假设下,Zermelo 定理(Zermelo, 1913;更一般形式见 Neumann & Morgenstern 1944)保证了一个铁律:由于不存在平局且必然在有限步内终止,任意局面要么存在先手必胜策略,要么存在后手必胜策略,二者必居其一,绝无第三种可能。
这意味着只要规则落在这个框里,输赢在开局那一刻就已经被数学写死了——剩下的只是谁先看穿局面属于哪一类。
二、P 态与 N 态:把博弈树变成有向无环图
把每个合法局面画成一个节点,把每一步合法操作画成一条有向边 \(x \to y\)。由于游戏满足有限终止条件,这张状态转移图里绝对不可能出现有向环,它是一张有向无环图(DAG)。
接下来只做一件事:给图里的每个节点贴上两枚标签之一。
- \(\mathcal{P}\) 态(Previous-player winning position,后手必胜 / 必败态):站在这个局面、轮到自己走的人,只要对手不犯错就必输;刚刚把局面推到这里的“上一步玩家(Previous player)”必胜。
- \(\mathcal{N}\) 态(Next-player winning position,先手必胜 / 必胜态):站在这个局面、轮到自己走的人(Next player)只要走对一步,就能稳赢。
初学者最容易把字母记混,记住英文首字母就再也不会错:P = Previous wins(上家赢,所以我惨了),N = Next wins(下家也就是现在的我赢)。
从终局节点开始逆向传播,只需三条公理就能给整张图定性:
- 终局公理:没有任何出边的终局节点一定是 \(\mathcal{P}\) 态(轮到谁面对终局,谁就无路可走直接输掉,所以上家赢)。
- \(\mathcal{N}\) 态公理:如果一个节点至少有一条边指向某个 \(\mathcal{P}\) 态,那么它就是 \(\mathcal{N}\) 态(你只需走那条边,把必败局面丢给对手)。
- \(\mathcal{P}\) 态公理:如果一个节点的所有出边都指向 \(\mathcal{N}\) 态,那么它就是 \(\mathcal{P}\) 态(无论你怎么挣扎,都只能把必胜局面拱手送给对手)。
图 1|有向无环图上的 P/N 倒推三公理。
节点 0 无出边,定为 \(\mathcal{P}\);随后按拓扑逆序依次判定
1 到 6。绿色实线箭头标记所有“从
\(\mathcal{N}\) 态一步打入
\(\mathcal{P}\)
态”的必胜着法。
读图要点:
- 节点
1和2都有边直达0(\(\mathcal{P}\)),因此立即标为 \(\mathcal{N}\)。 - 节点
3的两条出边3 -> 1和3 -> 2全部指向 \(\mathcal{N}\),无处可逃,因此3被钉死为新的 \(\mathcal{P}\) 态。 - 节点
4可以走4 -> 3进入 \(\mathcal{P}\),故4为 \(\mathcal{N}\);节点5的出边指向2和4(全是 \(\mathcal{N}\)),故5又落成 \(\mathcal{P}\)。 - 回到起点
6:它有三条出边3, 4, 5,其中6 -> 3和6 -> 5都直达 \(\mathcal{P}\) 态,都是必胜步;而6 -> 4是一步臭棋(把 \(\mathcal{N}\) 态送给了对手)。
这就是全部秘密:高手赢游戏不是靠算完所有分支,而是盯住图里的
\(\mathcal{P}\)
态锚点。 只要每一步都把局面压回 \(\mathcal{P}\)
态,对手无论怎么走都会被迫滑入 \(\mathcal{N}\)
态,你只需顺着绿色箭头再推回下一个 \(\mathcal{P}\)
态,直到对方撞死在终局 0。
三、拿巴什博弈与减法博弈练手:从手算到周期规律
把上面的倒推法落到文章开头的问题:巴什博弈(Bash Game)——一堆共 \(n\) 颗石子,每次可取 \(1\) 到 \(k\) 颗,取走最后一颗者胜。
取 \(k = 3\),从 \(n = 0\) 往后手工标一遍 \(\mathcal{P}/\mathcal{N}\):
- \(n = 0\):终局,\(\mathcal{P}\)。
- \(n = 1, 2, 3\):都能直接拿完变成 \(0\)(\(\mathcal{P}\)),所以全部是 \(\mathcal{N}\)。
- \(n = 4\):拿 \(1, 2, 3\) 分别剩下 \(3, 2, 1\),全是 \(\mathcal{N}\),无路可逃,所以 \(n = 4\) 是 \(\mathcal{P}\)。
- \(n = 5, 6, 7\):分别拿 \(1, 2, 3\) 就能精准把对手推进 \(4\)(\(\mathcal{P}\)),所以全是 \(\mathcal{N}\)。
- \(n = 8\):只能到达 \(7, 6, 5\)(全是 \(\mathcal{N}\)),所以 \(n = 8\) 是 \(\mathcal{P}\)。
规律一眼浮现:对于单堆取 \(1\text{–}k\) 颗石子,局面 \(n\) 是 \(\mathcal{P}\) 态当且仅当
\[ n \equiv 0 \pmod{k+1}. \]
图 2|巴什博弈(\(k=3\))的周期 \(\mathcal{P}\) 陷阱。 以开局 \(n = 10\) 为例:先手拿 \(2\) 颗将对手压到 \(8\)(\(\mathcal{P}\));此后每当对手拿走 \(t \in \{1, 2, 3\}\) 颗,你固定回应 \(4 - t\) 颗,凑齐一整轮消耗 \(4\) 颗,精准锁死下一个 \(4m\) 陷阱直到清零。
回看开头的“20 枚硬币,每次拿 1 到 3 枚”:因为 \(20 \equiv 0 \pmod{4}\),开局本身就是 \(\mathcal{P}\) 态。所以对方问你“你先还是我先”时,正确答案是大方让对方先拿;对方拿 \(t\) 枚,你拿 \(4-t\) 枚,五轮稳赢。
规则稍微一改:如果只允许拿特定数字呢?
如果对方把规则改成减法博弈(Subtraction Game):每次只能拿走集合 \(S = \{1, 3, 4\}\) 中的某个数量(例如不能拿 \(2\) 颗),模 \(k+1\) 立刻失效。怎么办?别慌,直接按倒推公理把前十几项写出来:
| 剩余石子 \(n\) | \(0\) | \(1\) | \(2\) | \(3\) | \(4\) | \(5\) | \(6\) | \(7\) | \(8\) | \(9\) | \(10\) | \(11\) | \(12\) | \(13\) | \(14\) |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 可达状态 \(n - S\) | \(\varnothing\) | \(\{0\}\) | \(\{1\}\) | \(\{2,0\}\) | \(\{3,1,0\}\) | \(\{4,2,1\}\) | \(\{5,3,2\}\) | \(\{6,4,3\}\) | \(\{7,5,4\}\) | \(\{8,6,5\}\) | \(\{9,7,6\}\) | \(\{10,8,7\}\) | \(\{11,9,8\}\) | \(\{12,10,9\}\) | \(\{13,11,10\}\) |
| 胜负标签 | P | N | P | N | N | N | N | P | N | P | N | N | N | N | P |
观察前 \(15\)
项的标签串:P N P N N N N | P N P N N N N | P ...。
为什么周期一定是 \(7\)?因为每次最多拿 \(4\) 颗,第 \(n\) 项的 \(\mathcal{P}/\mathcal{N}\)
标签只取决于前面连续 \(4\) 项 \((n-1, n-2, n-3, n-4)\)。长度为
\(4\) 的布尔窗口最多只有
\(2^4 = 16\)
种组合,由抽屉原理,任何有限减法集合 \(S\) 的 \(\mathcal{P}/\mathcal{N}\)
序列最终必然进入循环!在这里,n=7..10
对应的 4 元窗口与 n=0..3
完全相同(P N P N),因此从 \(n=0\) 起严格以 \(7\) 为周期循环:
\[ n \in \mathcal{P} \iff n \bmod 7 \in \{0, 2\}. \]
遇到任何陌生的单堆限制取法,哪怕不会任何高阶定理,草稿纸上倒推写出 \(15\) 个字母,就能用抽屉原理把它的周期彻底扒光。
四、不用算数字的两大杀器:对称模仿与策略盗取
很多桌游小把戏根本不需要算取模,对手真正藏起来的武器是几何对称性。
杀器一:对称模仿(Tweedledum-Tweedledee 原则)
核心思想极其直白:如果你能把棋盘划分成两块完全对称、互不干扰的镜像区域,使得对方在左半边走的任何一步,你都能在右半边走出完全对称的一步,那么只要你让对手先动,你永远不会比对手先无路可走——于是你必走最后一步,稳赢。
两个经典场景:
- 圆桌放硬币:一张光滑的圆形桌面,两人轮流平放一枚相同大小的一元硬币,硬币不能重叠也不能伸出桌沿,放不下的人输。
- 反杀策略:要求先手。第一步把硬币精准放在圆心;此后对方在桌面上任意点 \((x, y)\) 放一枚,你就以圆心为对称中心,在 \((-x, -y)\) 放一枚。只要对方的落点合法(不与圆心硬币重叠且在圆内),你的中心对称点就一定合法且不与任何已有硬币冲突(因为棋盘此前保持中心对称,而圆心已被你自己占住,不可能出现“对称点撞上对方刚放的硬币”的情况)。
- 两堆完全一样的石子 \((n,
n)\):如果桌上只有两堆数量相同的石子,每次只能从其中一堆拿任意正整数颗。
- 反杀策略:要求后手。对手从左边拿 \(t\) 颗,你就从右边拿 \(t\) 颗。对称性永远不破,直到你拿走最后一颗。
小心反常规则的陷阱:对称模仿之所以能稳赢,高度依赖“最后一步者胜(Normal Play)”。如果对方把圆桌硬币或双堆石子改成“最后放/拿的人输(Misère Play)”,盲目模仿反而会把自己送进死胡同。我们在 第 04 篇 会用一个令人意外的例子拆穿这个坑。
杀器二:策略盗取(Strategy Stealing)与 Chomp 巧克力
Chomp 是 David Gale(1974)在 The American Mathematical Monthly 上推广的一款著名公平博弈(最早由 Fred Schuh 在 1952 年独立研究过):
- 棋盘是一块 \(m \times n\) 的矩形巧克力(\(m \times n > 1\)),左下角那一格 \((0, 0)\) 涂了毒药。
- 两人轮流选一块尚存的巧克力 \((r, c)\),并吃掉 \((r, c)\) 以及它右上方一整块矩形区域 \(\{(i, j) \mid i \ge r,\ j \ge c\}\)。
- 谁被迫吃掉左下角的毒药块,谁输(等价于正常规则下不允许吃毒药块,无路可走者输)。
试着在 \(4 \times 5\) 的棋盘上找第一步必胜着法,你会发现局面形状瞬间变成千奇百怪的阶梯状,手工算根本无从下手。但数学家只用三句话就证明了:只要棋盘不止 \(1 \times 1\) 一格,Chomp 永远是先手必胜(\(\mathcal{N}\) 态)!
证明用的正是策略盗取(反证法):
- 假设先手试探性地只咬掉最右上角那一格 \((m-1, n-1)\)(记这一步为 \(X\))。
- 情况 A:如果咬完 \(X\) 后剩下的局面已经是 \(\mathcal{P}\) 态,那先手直接靠 \(X\) 就赢了,证毕。
- 情况 B:如果咬完 \(X\) 后不是 \(\mathcal{P}\) 态,那么后手一定存在某一步必胜回应 \(M\),把棋盘变成某个 \(\mathcal{P}\) 态 \(B^*\)。但请注意 Chomp 的咬法规则:无论后手选的是哪一格 \(M\),咬掉 \(M\) 时都会顺带清除掉它右上方的一切格子——其中必然包含最右上角那格 \(X\)!
- 这意味着,先手根本不需要多此一举先咬 \(X\),直接在第 1 回合就咬下 \(M\),得到的棋盘和“先手咬 \(X\)、后手咬 \(M\)”后的结果 \(B^*\) 一模一样!于是先手白白偷走了后手的必胜策略,第 1 步直接把 \(\mathcal{P}\) 态丢给对手。
图 3|\(4 \times 5\) Chomp 的策略盗取证明。 无论后手针对右上角试探步 \(X=(3,4)\) 的必胜回应 \(M\) 在哪里,咬下 \(M\) 都会自然覆盖 \(X\);因此先手可以直接在第 1 步盗走 \(M\)。
策略盗取的边界:知道“必胜”不等于知道“怎么走”
策略盗取最迷人也最令人抓狂的地方在于它是非构造性证明(Non-constructive Proof):它用纯粹逻辑告诉你先手必胜,却压根不告诉你 \(M\) 是哪一格。
对于正方形棋盘 \(n \times
n\) 和两行棋盘 \(2 \times
n\),构造性策略很漂亮(先手咬 \((1,1)\) 把正方形变成对称 L
形,见下文习题 3 的两行策略);但一旦扩展到 \(3 \times n\) 甚至一般矩形 \(m \times
n\),迄今为止数学界依然没有找到闭合的必胜步公式(Zeilberger
2001 研究了 \(3 \times n\)
的渐近结构,但仍无通用闭式解)。对于图 3 中的 \(4 \times 5\) 棋盘,我们的
Python 求解器穷举搜索后给出了唯一必胜首步:咬下 \((2, 2)\),留下的行宽为
(5, 5, 2, 2)。
策略盗取同样是围棋(无贴目、无劫争议的简化版)与六子棋(Hex,由 John Nash 证明)先手不败/必胜的核心论证工具,但它依赖“多走一步不会对自己有害”的单调性前提;一旦某个游戏存在“多占一步反而堵死自己”的局面(如国际象棋中的 Zugzwang 逼迫移子),策略盗取立即失效。
五、用 40 行 Python 暴力验证任意小游戏
遇到规则古怪的小游戏时,千万别用脑子硬扛。写一个通用的记忆化 P/N 倒推求解器,把任意游戏的“状态 \(\to\) 后继状态列表”函数传进去,几毫秒就能把小规模的 \(\mathcal{P}\) 态表与必胜走法全部打出来。
完整脚本见仓库文章同目录的
pn_solver.py,核心函数如下:
from typing import Callable, Iterable, TypeVar
State = TypeVar("State")
def solve_pn(
state: State,
moves_fn: Callable[[State], Iterable[State]],
cache: dict[State, bool] | None = None,
) -> bool:
"""返回 True 表示 N 态(先手胜),False 表示 P 态(后手胜)。"""
if cache is None:
cache = {}
if state in cache:
return cache[state]
for nxt in moves_fn(state):
if not solve_pn(nxt, moves_fn, cache): # 只要存在一步走向 P 态
cache[state] = True
return True
cache[state] = False # 无出边或全部走向 N 态
return False在当前环境运行
python post/combinatorial-games/01-pn-states-and-symmetry/pn_solver.py,实测输出(经删减保留核心验证段):
=== 1. Bash Game (take 1..3) ===
P-positions (0..24): [0, 4, 8, 12, 16, 20, 24]
=== 2. Small DAG Example ===
v=0 -> P (children=[], win_moves=[])
v=1 -> N (children=[0], win_moves=[0])
v=2 -> N (children=[0, 1], win_moves=[0])
v=3 -> P (children=[1, 2], win_moves=[])
v=4 -> N (children=[1, 3], win_moves=[3])
v=5 -> P (children=[2, 4], win_moves=[])
v=6 -> N (children=[3, 4, 5], win_moves=[3, 5])
=== 3. Subtraction {1, 3, 4} ===
P-positions: [0, 2, 7, 9, 14, 16, 21]
=== 4. Chomp 4x5 ===
4x5 Chomp -> N, winning first moves: [(5, 5, 2, 2)]
从单堆石子到 \(4 \times 5\) Chomp,底层执行的全部是同一套 10 行递归逻辑。
六、课后练习(先手算再展开核对)
练习 1(基础):变体巴什博弈
桌上有 \(100\) 颗石子,两人轮流每次取 \(1\) 到 \(5\) 颗,取走最后一颗者胜。先手还是后手必胜?如果是先手胜,第一步应该取几颗?
参考解答与思路(先独立推导再展开)
每次可取 \(1\text{–}5\)
颗,周期为 \(k+1 =
6\),\(\mathcal{P}\)
态是所有 \(6\)
的倍数。
计算 \(100 = 6 \times 16 +
4\),余数不为 \(0\),因此先手必胜。
第一步取走 \(4\)
颗,将局面压到 \(96 = 6
\times 16\)(\(\mathcal{P}\)
态);此后每轮对手取 \(t\)
颗,先手固定补取 \(6 - t\)
颗,稳赢。
练习 2(进阶):不允许拿 \(1\) 颗的减法博弈
桌上有 \(20\) 颗石子,两人轮流每次只能拿走 \(2\)、\(3\) 或 \(5\) 颗(剩余不足 \(2\) 颗时无法行动,判负)。请通过倒推找出 \(n = 0\text{–}20\) 的 \(\mathcal{P}/\mathcal{N}\) 周期,判断 \(n = 20\) 谁必胜并给出必胜第一步。
参考解答与思路(先独立推导再展开)
注意这里有两个终局状态:\(n = 0\) 和 \(n = 1\) 都无法行动,因此都是
\(\mathcal{P}\) 态!
逐项倒推前 \(15\) 项:
- \(0, 1\):\(\mathcal{P}\)
- \(2\)(可减 \(2\) 到 \(0\))、\(3\)(可减 \(2\) 到 \(1\) 或减 \(3\) 到 \(0\))、\(4\)(可减 \(3\) 到 \(1\))、\(5\)(可减 \(5\) 到 \(0\))、\(6\)(可减 \(5\) 到 \(1\)):全部是 \(\mathcal{N}\)
- \(7\):减 \(2, 3, 5\) 得到 \(5, 4, 2\)(全是 \(\mathcal{N}\)),故 \(7\) 为 \(\mathcal{P}\)
- \(8\):减 \(2, 3, 5\) 得到 \(6, 5, 3\)(全是 \(\mathcal{N}\)),故 \(8\) 为 \(\mathcal{P}\)
- 往后从 \(9\) 到 \(13\) 全都能一步打到 \(7\) 或 \(8\)(\(\mathcal{N}\)),\(14, 15\) 再次落回 \(\mathcal{P}\)。
窗口长度 \(5\) 在 \(n=7..11\) 处与 \(n=0..4\) 完全重合,周期为 \(7\):\(\mathcal{P}\) 态为 \(n \bmod 7 \in \{0, 1\}\)(即
\(0, 1, 7, 8, 14, 15, 21, 22,
\dots\))。
因此 \(n = 20\)(\(20 \equiv 6 \pmod 7\))是
\(\mathcal{N}\)
态(先手胜),唯一必胜第一步是拿走 \(5\) 颗,剩下 \(15\) 颗(进入 \(\mathcal{P}\) 态)。
练习 3(构造):\(2 \times 6\) Chomp 的显式必胜法
虽然一般矩形 Chomp 没有简单公式,但两行巧克力 \(2 \times n\) 却有一个能一眼记住的显式必胜法。对于 \(2 \times 6\) 的巧克力(左下角 \((0, 0)\) 有毒),先手第一步应该咬哪一格?之后怎么应对?
参考解答与思路(先独立推导再展开)
先手第一步咬掉最右上角那一格 \((1, 5)\),使两行长度变成
(6, 5)——即上一行恰好比下一行短 \(1\) 格。
此后无论对手怎么咬,先手总能把“上行比下行短 \(1\) 格”的不变量维持下去:
- 若对手咬下一行,使下一行变短为 \(a\)(\(a \le 5\)),先手就咬上一行把它截短到 \(a - 1\);
- 若对手咬上一行,使上一行变短为 \(b\)(\(b \le 4\)),先手就咬下一行把它截短到 \(b + 1\)。
沿着
(6, 5) -> ... -> (2, 1) -> (1, 0),对手最终只能面对仅剩毒药块的
(1, 0) 认输。所有 (k+1, k) 都是
\(2 \times n\) Chomp 的
\(\mathcal{P}\) 态!
练习 4(变体预热):反常巴什博弈(拿最后一颗者输)
一堆石子,每次可取 \(1\) 到 \(4\) 颗,但规则反过来:拿走最后一颗石子的人判负。请问 \(n = 21\) 和 \(n = 24\) 分别是先手胜还是后手胜?必胜步是什么?
参考解答与思路(先独立推导再展开)
换个角度看:只要你把“最后 \(1\)
颗毒药石子”留在桌面上逼对手拿走,你就赢了。所以新的终局必败态不再是
\(n = 0\),而是
\(n =
1\)(轮到面对 \(1\) 颗石子的人必输)。
从 \(n = 1\) 开始每轮凑
\(k + 1 = 5\) 颗:\(\mathcal{P}\) 态为 \(n \equiv 1 \pmod 5\),即 \(1, 6, 11, 16, 21, \dots\)。
- \(n = 21\):\(21 \equiv 1 \pmod 5\),是 \(\mathcal{P}\) 态(后手必胜);
- \(n = 24\):是 \(\mathcal{N}\) 态(先手必胜),第一步取走 \(3\) 颗把 \(21\) 留给对手。
练习 5(对称秒杀):一排格子涂色游戏
一排共 \(n\) 个连续格子(\(n \ge 1\)),两人轮流把任意 \(1\) 个空白格子,或任意 \(2\) 个相邻空白格子涂黑,无法涂色者输。问:当 \(n = 10\) 时谁必胜?当任意 \(n \ge 1\) 时呢?
参考解答与思路(先独立推导再展开)
对任意 \(n \ge 1\),永远是先手必胜,完全不需要算复杂状态!
- 若 \(n\) 为偶数(如 \(n = 10\)):先手第一步涂黑最正中的 \(2\) 个相邻格子(第 \(5\) 和第 \(6\) 格),把棋盘拆成左右两段长度完全相等(各 \(4\) 格)的独立条带;
- 若 \(n\) 为奇数:先手第一步涂黑最正中的 \(1\) 个格子,同样拆成左右两段等长的独立条带。
此后只要对手在左半边涂 \(1\) 格或 \(2\) 格,先手就在右半边做镜像对称涂色,稳稳收下最后一步。(提示:如果棋盘一开始就是多条长度不等的条带,对称法就不够用了,这就是著名游戏 Kayles,我们会在 第 03 篇 用 Sprague-Grundy 定理彻底拿下它。)
参考资料
- Zermelo, E. (1913). Über eine Anwendung der Mengenlehre auf die Theorie des Schachspiels. Proceedings of the 5th International Congress of Mathematicians, 501–504.
- Gale, D. (1974). A curious Nim-type game. The American Mathematical Monthly, 81(8), 876–879.
- Berlekamp, E. R., Conway, J. H., & Guy, R. K. (1982). Winning Ways for Your Mathematical Plays (Vol. 1). Academic Press.
- 仓库文章同目录的
pn_solver.py:P/N 倒推求解器与本篇全量练习核验脚本。
下一篇我们正式正面迎击最经典的“多堆石子”问题:02|Nim 与异或的直觉:为什么二进制按位相加能支配石子堆?。
源码下载
本文相关源码已整理,共 1 个文件。
文章导航
读完这篇,下一步读什么
优先读同系列或同问题的下一篇,把单篇消费变成主题集群。
【组合博弈】02|Nim 与异或的直觉:为什么二进制按位相加能支配石子堆?
拒绝把 Nim 异或背成黑盒魔法:通过 2 的幂筹码配对直觉证明 Bouton 定理,给出 3 秒牌桌口算必胜步方法,并用同一套不变量一次打通 Poker Nim、Northcott 棋盘与 Moore's Nim_k,附 Python 验证与 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 道练习。
【组合博弈】05|实战反杀手册、综合测验与超越 Nim:不对称博弈与开放问题
沉淀遇到陌生小游戏时的 5 步现场诊断协议,越过公平博弈边界介绍红蓝 Hackenbush 与 Conway 超实数、PSPACE 复杂性及 Grundy's Game 等未解难题,并附 10 道覆盖全系列的闭卷综合测验与 Python 核验脚本。