数学游戏工坊 · 豆芽棋 Sprouts 篇 ｜九章格数学 PhiloMath

豆芽棋圃 · Sprouts

一点三命，一笔生芽；线不许交叉，笔落不下者负。

工坊站点

第 16 站

豆芽数 n

—

已画曲线

—

剩余命数

—

本局上限

—

🌱 豆芽棋圃

点一个点，再点一个点，棋圃就替您把这笔线画好（走哪个面、绕行的细处由棋圃最优安排）——您要决定的是连哪两点。

— — — —

您的笔棋圃的笔开局点制胜笔（棋圃取胜的最后一笔）触屏：直接点两个芽点即可连笔

本关说明

开局豆芽—

胜负规则—

交接后已画—

您这边的局面—

着法记录

还没有落笔。

🔍 局面分析

把当前局面交给引擎做完整搜索：谁必赢、还能撑多久、有没有更好的连法。

裁决

轮到—

轮到方是否必胜—

最长剩余手数—

可行着法（去重后）—

已搜索局面数—

总步数界（Conway 1967）

从 n 个点出发的任意一局，总步数 m 满足 2n ≤ m ≤ 3n−1。

本局 n—

下界 2n—

上界 3n−1—

着法谱（本局面）

切到本页自动列出。

提示

点上面的「提示」按钮或这里，棋圃会把一条制胜连法的两个端点圈成红色。

📖 规则与数学

Sprouts（豆芽棋）1967 年由 Michael Stewart Paterson 与 John Conway 提出，同年由 Martin Gardner 在《Scientific American》介绍给大众。

规则

开局有 n 个点，每点有 3 条命。
每步画一条曲线，把两个点连起来（可以连同一个点，成环）。
线上自动生出一颗新芽（新点），新点只有 1 条命。
曲线两端各耗所在点 1 条命；两端同点（自环）则耗 2 条命。
曲线不许自交、不许与已有曲线交叉、不许穿过任何点。
无命可用的点不能再连。画不出线的一方输。
普通规则：画最后一笔者胜。末手为负（misère）：画最后一笔者负。

为什么线上必有新点

曲线把所在的那个面切开，新点就落在切口上；切开之后这个点的两条新命指向两侧，恰好只有 1 条能继续用——所以新生点永远只有 1 条命。

总步数界

每步总命数净减 1：新点 +1 命，两端 −2 命。开局共 3n 命，末局每点至少留 1 命（否则那一步还能再画），故 2n ≤ m ≤ 3n−1。n=2 时恰为 4 或 5 步，本工坊引擎已穷举复核。

谁先手必胜

n = 1先手负

n = 2先手负

n = 3先手胜（Conway 1964）

n = 4, 5先手胜（Mollison）

n = 11先手胜（Applegate–Jacobson–Sleator 计算机证）

一般猜想（至今未证）：先手必胜 ⟺ n ≡ 3, 4, 5 (mod 6)；其余 n ≡ 0, 1, 2 时后手必胜。

本工坊算了什么

n=1、n=2 的全部局面（n=2 共 1915 个有标签状态）在本机穷举，普通与末手为负两种规则一并算出。
n=3 只做残局直接搜索（最多 4 手的收束局），逐局面给出精确胜负。
曲线的走面、绕行细处由棋圃最优安排；您要决定的是连哪两点。