‹ 返回工坊合集
数学游戏工坊 · 保龄球取子 Kayles 篇 | 九章格数学 PhiloMath

凯尔斯球馆

球道上一排球瓶,每轮击倒 1 根 或 2 根相邻 的瓶,谁击倒最后一根谁赢。凯尔先生的 Grundy 密码,等您来破!
当前球道
★ 1
战胜凯尔先生
0
当前连胜
0
场上球瓶
—

🎳 球道对决

选球道 → 🧑‍🔧摆瓶小工摆瓶 → 您(🧑‍🎓新秀球手)定先手 → 与 🤵凯尔先生对局。规则:每轮选一条球道出手,击倒任意 1 根或2 根相邻的瓶(点瓶选中,再点「出手」)。
🤵凯尔先生球馆老板 · 凯尔斯游戏行家
🧑‍🏫老教练球馆军师 · 掌握「Grundy 异或」口诀
🧑‍🔧摆瓶小工摆瓶官 · 负责随机布置球瓶
🧑‍🎓新秀球手就是您!赢一局记一功
对局状态🎳 摆瓶中
当前球道—
先手新秀球手 🧑‍🎓
轮到谁—
🧑‍🎓 新秀,选谁先出手?

🔬 球道工坊 · 我是摆瓶官

像摆瓶小工一样摆一个局:设球道条数、每道的球瓶数,让老教练告诉您:这个局面对先手是赢是输?必胜第一招该打哪根瓶?
球道条数 = 2 条
各道球瓶数(−/+ 调整,1 ~ 20 瓶)
先手结局预判
—
摆好后点「老教练分析」
小贴士:单条球道永远先手必胜——只要第一球把瓶列从中间劈成两个等长段,然后「镜像」对手的每一手。所以真正有悬念的,是多条球道的组合:这时要比拼各道的 Grundy 值。

📖 球馆旧闻

从 Dudeney 的谜题书到 Sprague–Grundy 理论,还有老教练压箱底的「异或」口诀。

🎳 凯尔先生的球馆

球馆里有一排球瓶,凯尔先生最爱考较来客:每轮您出手,可以击倒任意一根瓶(直球),也可以击倒两根相邻的瓶(双瓶球)——但绝不能碰倒不相邻的两根。击倒的地方留下缺口,瓶列就此断成两段,此后两段各自为政。谁击倒最后一根瓶谁赢。

这个游戏叫 Kayles,名字来自法语 quilles——正是「球瓶」的意思。

📜 1908:Dudeney 的谜题

凯尔斯游戏由英国最伟大的谜题大师 Henry Dudeney(1857–1930)发明,收在他的名著《坎特伯雷谜题集》(The Canterbury Puzzles)第 73 题里。Dudeney 与美国的 Sam Loyd 并称 19 世纪两大谜题家,他喜欢把纯数学藏进小游戏里——凯尔斯就是最经典的一件。

🧮 Sprague–Grundy 定理

凯尔斯是「无偏博弈」:双方走法完全相同,轮到谁无子可动谁就输。这类游戏有统一的理论——每个局面都对应一个整数 Grundy 值(也叫 nimber):

局面必败 ⟺ Grundy 值 = 0。

而一个「拼起来」的局面(比如被击断的两段瓶列、或几条球道),其 Grundy 值就是各部分的按位异或。

🪞 为什么单道先手必胜?

设瓶列长 n。第一手把瓶列从正中劈成两段等长的:n 为奇数就击倒正中间那根,n 为偶数就击倒正中间相邻的两根。此后无论对手在左边怎么打,您就在右边照做同样的一手(镜像策略)。

于是每一轮对手都有得打、而您永远跟得上——最后一根瓶必落在您手里。n≥1 的单道,先手稳赢。

🔢 老教练的 Grundy 表(周期 12!)

单列长度 n 的 Grundy 值 G(n) 满足递推:把这一手拆成左右两段,取它们 Grundy 值的异或,再对所有这些可能取「最小未出现值」(mex)。算出来是这样一串(OEIS A002186):

n : 0 1 2 3 4 5 6 7 8 9 10 11 G(n): 0 1 2 3 1 4 3 2 1 4 2 6 12 : 4 1 2 7 1 4 3 2 1 4 6 7 24 : 4 1 2 8 5 4 7 2 1 8 6 7 36 : 4 1 2 3 1 4 7 2 1 8 2 7 48 : 4 1 2 8 1 4 7 2 1 4 2 7 60 : 4 1 2 8 1 4 7 2 1 8 6 7 72 : 4 1 2 8 1 4 7 2 1 8 2 7 ← 此后周期 12 无限重复

Guy 与 Smith 在 1956 年给出了完整分析,证明这串值从 n=71 起周期为 12——无限长的序列,竟由 12 个数循环讲完。

🧩 与「点格棋」的缘分

凯尔斯不只是一道谜题。在 Dots and Boxes(点格棋)这类经典对局里,残局的「长链」争夺常常可以化简成凯尔斯局面——所以想真正下好点格棋,就得先懂凯尔斯。

这也解释了它为何在组合博弈论教材里长盛不衰。

🌍 变体与远亲

把「2 根相邻」改成「2 根任意」就得到 Dawson's Kayles(八进制博弈 0.07);把胜负条件倒过来(无法出手者赢)是「反规则版」,由业余数学家 William Sibert 于 1973 年解出、1989 年才发表。凯尔斯本体则是八进制博弈 0.77,成为这一类游戏的标杆样本。

🎉

太棒啦!