要点

  • 我强解了两个最小的三人中国跳棋棋盘：每人一枚棋子（1,245 个局面）和每人三枚棋子（148 亿个局面）。两人版本已解到 6×6，三人版本此前没有结果。
  • 从开局看，没有玩家能强制取胜，任意两名玩家都能强制第三方落败，每名玩家都能把胜利交给任一对手。
  • 每五个局面中有四个，无法取胜的玩家仍能决定谁赢。
  • 和棋在三枚棋子时首次出现，与两人版本相同。求解在一台租用的 32 核机器上用了 7.4 小时，14.84 GB 的残局库已上线，可以浏览。

中国跳棋是一场横跨六角星的竞速。把你的棋子从一个角移到对面的角。没有吃子，没有子力，只有移动和封堵。

中国跳棋棋盘
摄影： Wesley Fryer, CC BY 2.0，来自 Wikimedia Commons。有修改。

Nathan Sturtevant 2019 年的结果是两人版本的基准。他强解了中国跳棋，最大到每方六枚棋子的 6×6 棋盘，在已完成的最大规模上覆盖 2,313,100,389,600 个局面。他解出的每种规模都是先手胜，他提出的待解目标是六枚棋子的 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 轮，而不在离终局一着的地方。

开局仍是造王者局面

三枚棋子开局的评估结果与一枚棋子的开局完全相同，且没有哪名玩家能从这里单独强制和棋。

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

下面的组件展示了两个最短的例证。不要把它们当成好的开局走法。它们只是残局库标签发生变化的第一批可达局面。

两条线的开头相同。B 早期的一步不同，九着之后标签分开：

  • A 的首个单独取胜：局面变成了 A 能强制自己取胜。
  • A 的首个搅局和棋：局面变成了 A 仍无法取胜，但能强制局面重复。

和棋与造王者

一枚棋子的棋盘上没有和棋局面。三枚棋子的棋盘上有每名玩家 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 ZB（泽字节）。第 2 级的计算用了 7.4 小时；只按规范化状态数相乘，就得到数千万机器年，这还没算更大的分支数、内存流量、检查点和 I/O。

六枚棋子需要在任何运行之前先做一轮新的范围评估：更强的压缩、外存或分布式逆向分析、考虑可达性的索引、更好的成本建模，而且很可能需要资金或捐赠的算力。

求解器如何运行

这次求解是用 Rust 写的逆向分析，覆盖 148 亿个局面。它把局面排序映射到稠密的数组槽位，按需生成着法，求解四个代表性的强制层，通过旋转推出另外八层，再把结果打包成本地残局库。有四个工程选择起了作用。

索引

只有当一个棋盘能通过算术运算变成它的数组槽位、再变回来时，一个包含 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 求解器在每个状态上都一致。这次对比发现了一个真实的缺陷：第一版 Python 着法生成器允许连跳回到起点，这其实是变相的停着。禁止之后，各求解器一致得到每名玩家 335 胜、910 负、0 和，以及 240 个可达的造王者局面。

第三，直接测试对称折叠。三重旋转保持求解值；镜像则不行，因为它会反转固定的 A→B→C 行棋顺序。n=2 的排序器也能让局面往返转换，并得到预期的 4,947,100,130 个规范化摆放。

最后，把打包好的残局库读回来做分析。控制类型各类之和精确等于 14,841,300,390 个状态，每名玩家的和棋数按对称性与搅局和棋一类相符，上文的开局和深度 9 例证都来自残局库查询，而不是手工标注。完整的 14.84 GB 原始残局库由在线局面浏览器提供，并作为压缩发布文件公开；公开仓库包含求解器、验证工具、静态例证和局面浏览器代码。

结语

加入第三名玩家，「谁赢」就不再是局面的属性。已经输了的玩家仍能决定胜者。能计算的是力量的分布：谁能强制自己取胜，谁需要伙伴，谁只能去选择别人的胜利。

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

资源：