Gobblet Gobblers 的完全解

摘要

Gobblet Gobblers 是一种大棋子可覆盖小棋子的井字棋变体，现已被解决：先手 13 着取胜。

求解方式是对全部 531,557,711 个可达局面做一次逆向遍历；非终局局面中只有 208,563 个是和棋。

所有小号和大号的首着都胜，所有中号首着都负，因为中号是对手仍能覆盖的最大棋子。

深度来自叠放机制。去掉覆盖后，游戏缩减到 140 万个局面，最深的胜局只有 10 着。

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 缓存的前向极小化极大假定每个局面只有一个值，但在三次重复规则下，一个局面的值取决于到达它的路径：同一个盘面在第三次出现时是和棋，在第一次出现时仍是活的。每个局面缓存一个值是不可靠的。（这就是图历史交互问题。）

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

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

// 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 个非终局局面同时放在内存里。局面到编号的映射用了自制的开放寻址表，以省掉哈希表每条目都要带的指针开销（在 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 上。