三人中国跳棋已被解决

中国跳棋是在一个六角星上的赛跑。把你的棋子从一个角移到对面的角。没有吃子，没有子力，只有移动与堵塞。

中国跳棋棋盘 — 照片作者 Wesley Fryer, CC BY 2.0，来自维基共享资源。已编辑。

Nathan Sturtevant 在2019年的结果是两人版的基准。他强解了至6×6棋盘、每方六枚棋子的中国跳棋，在已完成的最大规模上覆盖 2,313,100,389,600 个局面。他解出的每个规模都是先手胜，他明确提出的未解目标是6枚棋子的7×7。

三名玩家改变了被求解的对象。一个已经不可能获胜的玩家，仍然可以选择让哪个对手获胜。这样的玩家就是造王者。

我以阶梯方式解出了两个最小的三人棋盘：每人一枚棋子（1,245个可达局面）与每人三枚棋子（14,841,300,390个摆放×行棋方状态）。这里的强解指的是在完整规则模型上的精确残局库，而不是从开局出发的搜索。

从两种开局出发，没有任何玩家能强制自己获胜，任意两人都能强制第三人落败，而且每个玩家都能把胜利交给任一对手。和棋在三枚棋子时首次出现，与 Sturtevant 在两人版中发现的阈值相同，但从对称起始局面出发，单个玩家无法强制和棋。

你可以浏览残局库，阅读求解器与可复现包，或下载压缩的残局库文件。

这个游戏

来看规则而不是求解结果？三人中国跳棋怎么玩介绍了标准121孔棋盘上的摆法、走法与获胜方式。

三名玩家坐在相间的角上，向对面的角赛跑。棋盘由中央六边形加六个三角形角构成。一枚棋子的版本有13个格，能清楚展示布局：

单棋子棋盘布局

彩色圆点是棋子；带底色的描边格是目标区。A 从右上角出发，冲向左下的红色目标区；B 和 C 在同一棋盘上沿各自的对角线行进。三枚棋子的棋盘把每个角扩为三格（共37格），每名玩家有三枚棋子。

棋子可以走到相邻的空格，或者跳过任意相邻的棋子（你自己的或对手的）落到其后的空格，并可连跳，一回合内穿越棋盘。没有任何棋子被吃掉。填满自己的目标角即获胜。

连跳规则很容易被低估。在下面的单棋子棋盘中，C 的一步普通走法搭出了桥。A 随后可以跳过 C 和 B，一回合进入目标区。

连跳序列

为什么三人局中「谁赢」这个问题会失效

两人游戏是零和的：每个局面要么胜、要么负、要么和棋，「已解决」就是一个单一的值。三人游戏打破了这一点。如果 A 已经不可能获胜，那么每一着对 A 自己的得分而言同样糟糕。但这一着仍然能决定是 B 还是 C 获胜。

要计算的对象是控制结构：哪位玩家，单独或与搭档一起，能强制出哪种结果。我在同一张图上计算普通的两人强制表：

单人：一名玩家能否面对另外两人联手强制自己获胜？
助攻：玩家 i 和 j 能否合力强制 j 获胜？
双人封杀：两名玩家能否强制第三人落败？
搅局和棋：一名玩家能否强制重复局面以避免落败？

造王者由这些表推导而来。当 i 能促成 j 获胜而 j 自己无法强制取胜时，玩家 i 就是玩家 j 的造王者。这些强制性问题都是标准的；新的部分在于用这种方式读取一个真实三人游戏的精确残局库。

算法有何不同

逆向分析的基本原语仍是经典的那套。在两人游戏中，每个局面就是一个标量：对行棋方而言是胜、负或和棋。倒推规则很简单：

# Two-player retrograde, schematically.
if any(child is LOSS for child in moves(position)):
    position = WIN
elif all(child is WIN for child in moves(position)):
    position = LOSS
else:
    position = DRAW

在三人局中，「对手获胜」不再是单一结果。如果 A 已经输了，A 或许不在乎是 B 还是 C 获胜，但残局库必须在乎。这个选择就是造王者。

因此我不计算单一的三人值。我在同一张图上计算一整组两人强制性问题：

def can_force(position, max_side, objective):
    if terminal(position):
        return objective_holds(position)

    if position.turn in max_side:
        return any(can_force(child, max_side, objective)
                   for child in moves(position))
    else:
        return all(can_force(child, max_side, objective)
                   for child in moves(position))

真实的求解器把这条规则实现为带环的逆向分析，而非递归：从终局状态出发，沿前驱向后遍历，当某个 MAX 状态有任一子节点为胜时标记为胜，当所有子节点皆为负时标记为负，未决的状态保留为和棋。

can_force(s, {A}, "A wins") 询问 A 能否战胜 B 和 C。can_force(s, {A, B}, "B wins") 询问 A 能否帮助 B 获胜。can_force(s, {A, B}, "C loses") 询问 A 和 B 能否把 C 封死。

和棋问题出自同一次求解。如果 A 无法强制取胜，而对立联盟也无法把 A 逼入终局失败，那么在 Sturtevant 使用、本文沿用的重复局面和棋规则下，该状态对 A 而言是和棋。

一个局面的解值是这些答案的交叠：

entry = {
    "solo":   {A: A_can_force_A_win,
               B: B_can_force_B_win,
               C: C_can_force_C_win},
    "enable": {A_to_B: AB_can_force_B_win,
               A_to_C: AC_can_force_C_win,
               B_to_A: AB_can_force_A_win,
               B_to_C: BC_can_force_C_win,
               C_to_A: AC_can_force_A_win,
               C_to_B: BC_can_force_B_win},
    "pairout": {A: BC_can_force_A_out,
                 B: AC_can_force_B_out,
                 C: AB_can_force_C_out},
    "draw":   {A: A_can_force_draw,
               B: B_can_force_draw,
               C: C_can_force_draw},
}

这就是算法上的差异。两人逆向分析计算一张值表。三人中国跳棋计算若干张普通的逆向分析表，然后把它们的交叠读作控制关系：单人胜、被助攻的胜、双人控制、造王者与搅局和棋。

第1级：一枚棋子

单棋子游戏有1,245个可达局面。一枚棋子无法封死目标区，因此没有和棋。它的作用是校准：小到足以用两种独立方法求解并手工核对。

每个可达局面都归入四类之一：

控制类型	局面数
终局（已有人获胜）	171
单人胜（一名玩家能强制自己获胜）	834
造王者（落败者决定谁赢）	240
搅局和棋	0
可达总数	1,245

可达局面的五分之一已经属于造王者范畴。下面是那240个局面之一，以及由此出发的两种合法选择：

示例造王者局面

轮到 B 行棋，而 B 无法获胜。一着把必胜交给 A；另一着把必胜交给 C。B 已经输了，却仍然决定着这盘棋。

单人强制层在逆向分析第9轮解决。有序的造王者问题跑得更久，到第13轮和第15轮，因为它们要求更具体的结果：不只是「这名玩家能否获胜」，而是「这名玩家能否帮助另一名玩家获胜」。开局结论与三枚棋子的游戏一致：无单人胜，任意一对都能封杀第三人，六种有序造王者关系全部成立。

第2级：三枚棋子

三棋子开局

结果与规模

每人三枚棋子，37格，14,841,300,390 个局面，计入摆放与行棋方。这个计数枚举了角道允许的每一种摆放，而不只是从起始局面可达的局面；这个游戏的可逆性足够强，两者几乎重合，而求解器为它们全部打上标签。这是我能找到的第一个三人中国跳棋棋盘的精确强解。这一说法的范围是刻意限定的：我找到的最接近的既有工作要么是解析性的（三人 Nim），要么是近似且随机的（多人 Can’t Stop），要么是三人 Otrio 的可行性研究。

数量	数值
局面数	14,841,300,390
单人胜 / 负 / 和棋（每名玩家）	950,015,894 / 13,890,307,418 / 956,384

由于三重旋转对称，「每名玩家」这一行对 A、B、C 都相同。从一名玩家的视角来读：在6.4%的局面中，该玩家能面对另外两人联手强制自己获胜。在93.6%的局面中，另外两人能把他封杀。和棋罕见但确实存在。各行之和与局面总数略有出入：有20,694个枚举出的摆放同时填满了两个目标角，这在合法对局中不会出现，求解器把它们标记为非法而非胜、负或和棋。

与第1级相比，三枚棋子改变了规模，却没有改变开局的控制结构：

不变：在两级上，对称起始局面都是纯粹的造王者局面：无单人胜，任意两人都能封杀第三人，六种造王者关系全部成立。
新增：和棋。单个玩家能强制形成永久堵塞，这在一枚棋子时不可能。
更深：单棋子的单人层在9轮内解决；三棋子的单人层跑了53轮，解决量在第10到13轮达到峰值，而不是集中在距离终局一着之处。

开局仍是造王者局面

三棋子开局的评估与单棋子开局完全一样。没有玩家能强制自己获胜。任意两名玩家都能封杀第三人。没有单个玩家能强制和棋。六种有序造王者关系全部成立：A 能把胜利交给 B 或 C，B 能交给 A 或 C，C 能交给 A 或 B。

这种平衡会维持一段时间。从起始局面出发的广度优先搜索发现，直到深度8为止，每个可达局面仍属于造王者类。在深度9，首批非造王者局面出现：在1,906,964个新到达的局面中，41个是单人胜，1个是搅局和棋。其余1,906,922个仍是造王者局面。

下面的小工具展示两个最短的见证局面。不要把它们当作好的开局着法。它们只是残局库标签首次改变的最早可达局面。

两条线路起手相同。B 的早期一着不同，九着之后标签就分道扬镳：

A 的首个单人胜：该局面已变成 A 能强制自己获胜的局面。
A 的首个搅局和棋：该局面已变成 A 仍无法取胜、但能强制重复局面的局面。

这是一个可达性事实，不是关于最佳开局着法的断言。它说明从对称起始局面出发，残局库直到深度9才遇到单人胜或搅局和棋的标签。

和棋与造王者

单棋子棋盘没有任何和棋局面。三棋子棋盘有每名玩家956,384个单人和棋局面，以及整体2,869,152个搅局和棋局面，即某一名玩家能强制重复局面以避免落败。Sturtevant 在两人版中发现了相同的阈值。

按控制结构对全部148亿个局面进行归类：

控制类型	局面数	占比
造王者（无人能强制取胜；由某人选择）	11,988,362,862	80.8%
单人胜（一名玩家能强制自己获胜）	2,814,699,759	19.0%
终局（已有人获胜）	35,368,617	0.24%
搅局和棋（单个玩家能强制和棋）	2,869,152	0.019%
其他	0	0%

最后一行很重要：这些强制性问题对整个游戏做了完整分类，没有留下无法判定的残余。造王者领域占据主导。在每五个局面中有四个，解值的问题是谁来决定，而不是谁会获胜。

两个残局库示例

接下来的两个小工具不是谜题。棋盘在那里，是为了让残局库结果有一个具体局面作依托。状态文字和标签页才是重点。

一个搅局和棋，这类局面只在三枚棋子时才存在：

轮到 C 行棋，但标签描述的是 A 的防守能力。A 没有必胜，而只要 A 保持堵塞循环可用，另外两名玩家也无法把 A 逼入终局失败。这正是对称开局从不提供的选项：一名自己没有胜势的玩家，守住了和棋。

把它当作着法筛选的例子。在「A 对其余两人」的残局库问题下，C 恰好只有一着能把 A 留在和棋区域。C 的大多数其他着法都会让 A 得到更好的结果并强制取得单人胜。在 C 走出保和的一着后，A 有一个应手能保持堵塞循环可用。循环标签页提供了审计轨迹：再走六着之后，相同的棋盘与相同的行棋方重新出现。

一个决定性的造王者局面：

轮到 A 行棋，而 A 无法获胜。这里没有和棋的妙手。一个标签页给 C 带来必胜；另一个给 B 带来必胜。A 已经输了，但 A 仍然选择赢家。

这个残局库把能力与行为分开。它说明什么能被强制，而不假设无所谓的玩家如何打破平局。可以在同一张状态图之上再加一层单独的策略处理：常规的自利、偏好和棋的搅局者，或者像 A 想让 B 赢、B 想让 C 赢、C 想让 A 赢这样的循环偏好。这些处理会把许多造王者局面塌缩为某个具体赢家，但答案将依赖于偏好，而不属于强解的一部分。

另一种扩展改变的是目标本身。本次求解在第一名玩家填满目标区时停止。如果玩家在意拿第二名，游戏就需要一个排名目标，或者一条在第一名产生后继续进行的规则。那将衡量另一回事：不只是谁能获胜，还有第二名的激励如何改变堵塞与造王行为。

第3级：六枚棋子

下一级自然是每人六枚棋子，但棋盘的约定很关键。Sturtevant 已完成的最大结果是两人的 6×6 / 6枚棋子对局菱形区。他明确提出的未解目标是 7×7 / 6枚棋子。对三人而言，可比的六枚棋子目标是那块 7×7 对局区域背后的对称星形几何：73格、三名玩家、每人六枚棋子。

六棋子目标棋盘

参考	玩家数	棋子数	棋盘模型	状态
Sturtevant 6×6	2	6	偶数对局菱形区	已解决
Sturtevant 7×7	2	6	奇数、与星形兼容的对局区域	未解决
本级	3	6	73格三人星形棋盘	未解决

对于那个三人星形棋盘，设置是确定的：

数量	数值
棋盘	73格
棋子数	每名玩家6枚

受角道限制的上界是精确计算的，这里为展示做了取整：

数量	取整数值
受角道限制的摆放×行棋方状态	≈1.30×10²¹
C3规范化状态	≈4.33×10²⁰
相对第2级的增幅	约876亿倍

这些界限来自与第2级相同的角道限制枚举器，而不是简单的「棋子随便放」的计数：每名玩家的六枚棋子被限制在该玩家的两个专属角加上共享的37格中心区，计数按每名玩家在共享中心区放置的棋子数求和。精确的三重旋转对称随后把摆放×行棋方状态除以3。可达性并不会把问题的规模降低几个数量级。中国跳棋无吃子且可逆，在较小的棋盘上，可达部分很快就逼近完整的角道限制空间。

直接放大当前的求解方式是做不到的。第2级的最终残局库为14.84 GB；同样的表示方式在六枚棋子下约为1.3泽字节。第2级的计算跑了7.4小时；仅按规范化状态数相乘就得到数千万机器年，这还没算上更大的分支因子、内存流量、检查点和 I/O。

六枚棋子是未来的工作，起点是新的可行性规划阶段，而不是更长的一次运行：更强的压缩、外存或分布式逆向分析、感知可达性的索引、更好的成本建模，以及很可能需要的资金或捐赠算力。工程问题变得和博弈论问题一样有趣。

求解器如何运行

这次求解是在148亿个局面上用 Rust 做的逆向分析。它把局面编号映射到密集数组槽位，按需生成着法，求解四个代表性强制层，再通过旋转导出其余八个，并把结果打包成本地残局库。有四项工程选择很关键。

索引

148亿个值的扁平数组只有在棋盘能用算术与其数组槽位相互转换时才可行。每种摆放映射到一个密集编号，着法即时生成：没有哈希表，没有指针，只有对一整块内存的索引运算。

波前

计数法从终局向外扩散，跨全部32个核心。每个局面携带两个原子字节：它的值，以及未决着法的计数。走入一个胜局面会立即决定结果。走入一个负局面会让计数减一。计数归零意味着所有着法都很糟。由于游戏无吃子且可逆，反向着法是免费的。

对称

控制结构由十二个强制性问题构成：每名玩家的单人问题、每个有序对的助攻问题、每名玩家的双人封杀问题。搅局和棋标签来自单人层的和棋结果。棋盘的三重旋转对称把十二个强制性问题折叠为四个代表；其余八个通过重新标号得到。我把这次折叠用在问题组上而不是索引上：求解器为每一层保留完整的148亿局面数组，并计算四层而不是十二层，这与规范化状态数所能带来的三倍因子相同。镜像不是有效的对称，因为它会把固定的行棋顺序 A→B→C 反转为 A→C→B。

我在正式运行前就发现了这一点：在单棋子棋盘上测试两种折叠方式，六重对称（旋转加镜像）破坏了解值；单用三重旋转则保持不变。

计算运行

每个强制层的原子数组在求解时约占30 GB；已完成的层会丢弃计数器并保留单字节值数组，因此最后同时保留的四层约占60 GB。工作负载是分散的原子写入，所以合适的机器是大型 CPU 服务器，而不是 GPU。我租了一台 Hetzner CCX53：32 vCPU、128 GB 内存，内存余量足以让波前数组常驻而不换页。

这次运行还需要运维配套：对每个代表层做检查点，SSH 断开后能干净恢复，并逐轮输出进度，让我能确认它在推进而不是在烧租用时间。我在本地构建，把代码传到服务器，在 tmux 下运行，用 htop 观察内存，在拷回打包好的残局库之后销毁机器。最终运行约7.4小时完成，花费几欧元；最终残局库打包为14.84 GB。

验证

我相信这个结果，因为它在大规模运行前通过了小规模检查，运行后又通过了大残局库的检查。

其一，计数模型用 2*C(m²,k)*C(m²-k,k) 精确重现了 Sturtevant 表1的局面数一列，全部八行。这是在信任我自己的星形棋盘计数之前，理解两人版参考结果的门槛。

其二，单棋子的三人游戏小到可以用多种方式穷举求解。两个独立的 Python 逆向分析程序与 Rust 求解器在每个状态上一致。这项对比抓出了一个真实的 bug：第一版 Python 着法生成器允许连跳链回到起点，那实际上是伪装的弃着。禁止之后，各求解器在每名玩家335胜、910负、0和棋上达成一致，并有240个可达的造王者局面。

其三，对称折叠被直接测试。三重旋转保持解值；镜像不保持，因为它反转了固定的 A→B→C 行棋顺序。n=2 的编号器也能对局面做往返转换，并给出预期的4,947,100,130个规范摆放。

最后，打包好的残局库被读回做分析。各控制类型的桶精确加总为14,841,300,390个状态，每名玩家的和棋数按对称与搅局和棋桶相符，上文的开局与深度9见证局面来自残局库查询而非手工标注。完整的14.84 GB 原始残局库由在线浏览器提供服务，并作为压缩的发布资源公开；公开仓库包含求解器、验证框架、静态见证局面和浏览器代码。

结论

加入第三名玩家，「谁赢」就不再是局面的属性。一个已经输了的玩家仍然能决定赢家。你能计算的是权力的分布：谁能强制自己获胜，谁需要搭档，谁只剩下选择别人胜利的余地。

两个已解的开局尽管规模相差七个数量级，结论却一致。和棋在三枚棋子时出现，但从对称起始局面出发从不出现。

在三人局中，一个已被解决的游戏告诉你的是谁来决定，而不只是谁会赢。

资源：

Sturtevant，《On Strongly Solving Chinese Checkers》（Advances in Computer Games，2019）：本文所扩展的两人版求解。作者 PDF。
在线三人残局库浏览器：对完整三棋子残局库的精确查询。
brianhliou/chinese-checkers-3p：Rust 求解器、验证框架、浏览器与公开的可复现说明。
残局库文件 v1：压缩的残局库文件与清单。