解出 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 棋盤，兩位玩家。每位玩家有六枚棋子（兩小、兩中、兩大），開局時六枚全在手中。只要在任一橫列、直行或斜線上露出自己顏色的三子連線即獲勝。
你的回合
每回合你做以下兩件事之一：
- 放置一枚手中的棋子到棋盤上，或
- 移動盤上一枚自己的棋子到另一格。
無論哪一種，棋子都必須落在空格，或者吞掉（gobble）一枚嚴格更小的棋子（自己或對手的）並蓋住它。只有疊層最上面那枚可見：只有最上面的棋子計入連線，也只有最上面的棋子能被拿起移動。
揭露規則
把一枚棋子移離它所在的格子，會露出壓在它底下的東西，而這發生在你的棋子落到別處之前。你不能露出對手已完成的連線又放任不管：如果拿起某枚棋子會露出對手的三子連線，那枚棋子就必須落回那三格之一並蓋住它。若它無法到達其中任何一格，這次拿起就是不合法的。
最尖銳的戰術正是由此而生。一枚棋子可能被牽制：它是唯一蓋住對手連線的棋子，因此動不了。一個疊層承載著歷史，會在許多著之後仍限制著法。當輪到走的一方完全無合法著法時，它輸；當雙方都無法取得進展時，因重複而和棋。
你看不到的部分
實體遊戲會隱藏被蓋住的棋子：你不可以偷看被吞掉的棋子，所以必須記住底下是什麼，實際對局部分是記憶遊戲。本次求解假設完全資訊：雙方都知道每一枚被蓋住的棋子。局面瀏覽器同樣顯示完整疊層，讓你能看到殘局庫評估的確切局面。
逆向分析
重複規則排除了最直覺的做法。帶有 position → outcome 快取的前向 minimax 假設每個局面只有一個值，但在三次重複的規則下，一個局面的值取決於抵達它的路徑：同一個盤面在第三次出現時是和棋，在第一次出現時卻仍有勝負。每個局面只快取一個值是不可靠的。（這就是圖歷史交互作用問題。）
逆向分析則反向求解整張圖，完全不涉及路徑。分兩個階段：
- 以廣度優先掃描列舉從起始局面可達的每一個標準化局面，以局面為索引鍵。換位會收斂為同一個節點。
- 以反向歸納填值直到不動點。先給終局局面設定初值，然後反覆迭代直到沒有任何變化。
// 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：九格各六個位元（小、中、大各有擁有者，每個兩位元）加上一個行棋方位元。著法佔一個位元組，還原佔兩個，勝利判定則是八個預先算好的位元遮罩。
求解意味著要把全部 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 上。