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 快取的前向 minimax 假設每個局面只有單一數值，但在三次重複的規則下，一個局面的值取決於抵達它的路徑：同樣的盤面，若是第三次出現就是和棋，若是第一次出現則還活著。每個局面只快取一個值是不可靠的。（這就是 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 上。