Gobblet Gobblers 残局库与完全解

Gobblet Gobblers 是带叠子机制的井字棋变体，作为儿童游戏（5 岁以上）出售。我对它做了穷尽求解，并搭建了一个展示双方最佳着法的网页浏览器。先手 13 着取胜。

求解采用逆向分析，覆盖从初始局面可达的每一个局面，共 531,557,711 个。输出是一个残局库，给出任何合法可达局面的准确结果与到结果的距离。

结论	结果
结果	先手胜
从初始局面的取胜距离	13 着
规范化可达局面	531,557,711
和棋局面	208,563 (0.04%)
最深的必胜	23 着

源码： github.com/brianhliou/gobblet-gobblers

独立打开 →

每个合法着法按其真实结果着色：绿色为胜，红色为负。

游戏规则

3×3 棋盘，两名玩家。每人有六枚棋子（两小、两中、两大），开局时六枚都在手中。让自己颜色的三枚棋子连成一线即胜：任意一行、一列或对角线。

你的回合

每回合你做以下两件事之一：

从手中放置一枚棋子到棋盘上，或者
把棋盘上自己的一枚棋子移动到另一格。

两种情况下，棋子要落在空格上，或者吞掉一枚严格更小的棋子（自己的或对手的），覆盖在它上面。只有叠子的顶层可见：只有顶层棋子计入连线，也只有顶层棋子可以被拿起移动。

揭露规则

把一枚棋子移离所在格会露出压在它下面的东西，而这发生在你的棋子落到别处之前。你不能露出对手已经连成的一线并让它留在场上：如果抬起某枚棋子会露出对手的三连，那枚棋子必须重新落在那三格之一并覆盖它。如果它无法到达其中任何一格，这次抬起就是不合法的。

最尖锐的战术就来自这里。一枚棋子可能被牵制：它是唯一压住对手连线的东西，因此不能动。一个叠子携带的历史会在许多着之后仍然限制着走法。当轮到走的一方完全没有合法着法时，它负；当双方都无法取得进展时，棋局因重复而成和棋。

你看不到的部分

实体游戏会隐藏被覆盖的棋子：你不能翻看被吞棋子的下面，所以必须记住那里是什么，实际对局有一部分是记忆游戏。求解假设完全信息：双方都知道每一枚被覆盖的棋子。浏览器出于同样原因展示完整的叠子，让你看到残局库所评估的确切局面。

逆向分析

重复规则排除了显而易见的做法。带 position → outcome 缓存的前向极小化极大假设每个局面只有一个值，但在三次重复规则下，一个局面的值取决于到达它的路径：同一盘面在第三次出现时是和棋，第一次出现时却仍有胜负。每个局面只缓存一个值是不可靠的。（这就是 Graph History Interaction 问题。）

逆向分析从后往前求解整张图，完全不涉及路径。分两个阶段：

用广度优先遍历枚举从初始局面可达的每一个规范化局面，以局面为键。换位会归并成同一个节点。
用反向归纳填值直到不动点。先给终局局面赋初值，然后反复迭代直到不再变化。

// one round over the still-unknown positions
for &pos in &unknown {
    let mut win = false;                  // a move reaches a loss for the opponent
    let mut all_children_decided_win = true;
    for child in moves(pos) {
        match value[child] {
            Loss    => { win = true; break; }
            Unknown => all_children_decided_win = false,
            Win     => {}
        }
    }
    if win                           { set(pos, Win) }
    else if all_children_decided_win { set(pos, Loss) }
    // else leave Unknown: it resolves in a later round, or it's a draw
}

和棋不需要特殊处理。它们就是不动点始终解决不了的局面，卡在双方都无法强求结果的循环里。求解过程中任何地方都没有重复计数器。一个局面恰好在最佳着法只能靠永远重复来避免失败时才是和棋，而这正是未解决集合。这与国际象棋和西洋跳棋残局库背后的方法相同。

结果

从初始局面可达 531,557,711 个规范化局面，初始局面是先手 13 着取胜。在 370,974,636 个非终局局面中，结果几乎平分：185,455,752 个先手胜，185,310,321 个后手胜，只有 208,563 个是和棋（0.04%）。每一个可达局面要么是某一方的必胜，要么是和棋；没有任何局面悬而未决。

值得注意的发现

大多数胜局立刻结束，向 23 着延伸出一条细长尾巴。 在全部局面的 83% 中，轮到走的一方已经有一步当场取胜的着法。再往后，随着距离增加，胜势局面迅速变少，而且几乎无例外地落在奇数着上。这条尾巴收窄到唯一一个 23 着必胜，是全局最深的，只有 9 个局面能到达。

这个最深的胜局尖锐到极致。从这个局面出发，先手有 26 个合法着法，恰好只有一个能保住胜势（把中子从中心叠子上滑开），其余 25 个都会输掉，而取胜仍在 23 着之外。

开局按棋子大小是全有或全无，而且并非单调。 27 个首着中，所有小子和所有大子的放置都胜，但所有中子的放置都负：它把必胜交给了后手。中子是对手仍然能吞掉的最大棋子。用你的大子回应它，从中心出发唯一的取胜应着，你就用一枚永远不会被揭露的棋子占下那一格，中子被埋在下面。大子根本不能被吞；小子不值得用更大的棋子去覆盖。只有中等大小会招来吞吃。

常常只有一个着法能胜。 在 12.7% 的胜势局面中，只有唯一一个着法能保住胜势，其他任何着法都会丢掉。上面那个最深的胜局是极端情形，26 个着法中只有一个能救。

将近四分之一的局面存在被牵制的棋子。 在 22.8% 的局面中，抬起某枚棋子会露出对手的三连，于是揭露规则把它钉在原地。

和棋是残局现象。 208,563 个和棋集中在后期：91% 的和棋局面棋盘上有 12 枚棋子中的至少 8 枚，最常见是 10 枚。它们是双方都能来回挪动却无法强求结果的局面。

实现

完整状态可以装进一个 u64：九格各占六位（小、中、大各自的归属，每个两位）再加一位行棋方。着法占一个字节，撤销占两个，胜负判定是八个预先算好的位掩码。

64 位棋盘编码

求解意味着要把全部 370,974,636 个非终局局面同时放在内存里。局面到 id 的映射用了自制的开放寻址表，以省掉哈希表每条记录都要带的指针开销（在 0.74 装填率下约 6 GB）。不动点迭代在多核上并行运行：每一轮读取上一轮的值并写入下一轮，因此每个局面都在其真实距离上被解决，取胜距离也是最小的。整个求解在一台 14 核笔记本上约需 30 分钟，峰值内存不到 12 GB。

提供查询是第二个问题。表放不进无服务器函数，于是用最小完美哈希把 370,974,636 个规范化键映射到一个稠密区间，没有冲突也不存储键（每个约 3.5 位），再加上每个局面一个字节的到结果距离，总共 531 MB，由一个小型 Rust 服务常驻内存。

Browser (game logic in WebAssembly)
   │  POST /lookup/batch  [canonical keys]
   ▼
Tablebase service (MPH in RAM)
   │  outcome + distance per position
   ▼
Browser colors each move

浏览器用 WebAssembly 运行游戏逻辑，只在需要评估时调用服务。终局局面由它自己判定，因此根本不会查到残局库。

深度从何而来

揭露规则看起来像是深度的来源：一枚作为对手连线唯一遮盖而被牵制的棋子，一次当场输掉的抬起。但它不是。去掉这条规则重新求解，允许任何抬起，几乎什么都没变：同样的 370,974,636 个局面，同样的开局 13 着取胜，最深的胜局只从 23 着略升到 25 着。这条规则塑造了五分之一局面的着法列表，却很少改变结论，因为好的走法本来就会避免露出连线。

叠子才是来源，去掉它便可证明这一点。禁用覆盖重新求解，每枚棋子只能落在空格上，游戏就崩塌了：局面数从 370,974,636 降到 1,433,602，最深的胜局降到 10 着，一个和棋都没有。原因是从来没有棋子被吃掉。吞吃只是覆盖一枚棋子，并不移除它。子力永远不会像吃子把棋盘逐步简化到残局那样变稀，所以一个 3×3 的网格永远安定不下来。动物将棋的深度出自同一处，只是路径不同：被吃的棋子会以打入的形式回到棋盘，所以它的子力也永远不会流失。

先手 13 着取胜。gobblet.brianhliou.com 上的浏览器依据残局库对弈，按真实结果给每个合法着法着色，并标注到结果的距离。求解器在 GitHub 上。