三人中國跳棋，已被解決

簡而言之

我強解了兩個最小的三人中國跳棋棋盤：每人一顆棋子（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。

六顆棋子在任何執行之前，都需要一個新的範圍評估階段：更強的壓縮、外部記憶體或分散式逆向分析、考慮可達性的索引、更好的成本建模，以及很可能需要的資金或捐贈的運算資源。

求解器如何執行

這次求解是在 148 億個局面上執行的 Rust 逆向分析。它把每個局面換算成序號，放進密集陣列的槽位，按需產生走法，求解四個代表性的強制層，以旋轉推導出另外八個，再把結果打包成本機殘局庫。有四項工程選擇很關鍵。

索引

148 億個值的平面陣列，只有在棋盤能用算術換算成陣列槽位、再換算回來時才行得通。每種排列對應到一個密集序號，走法即時產生：沒有雜湊表，沒有指標，只有對一大塊記憶體做索引算術。

波前

計數器法從終局出發，用全部 32 個核心向外擴散。每個局面帶兩個原子位元組：它的值，以及尚未判定的走法數。走進勝局的走法會立即判定。走進敗局的走法會讓計數器減一。計數器歸零，代表每一著都是壞棋。反向走法不需額外成本，因為這個遊戲沒有吃子且可逆。

對稱

控制結構由十二個強制問題組成：每名玩家的單獨取勝、每個有序玩家對的助推、每名玩家的雙方聯手排除。攪局和棋標籤是單獨層的和棋結果。棋盤的三重旋轉對稱把十二個強制問題摺疊成四個代表；其餘八個透過重新標記得到。我把這次摺疊用在問題組上，而不是用在索引上：求解器每層保留完整的 148 億局面陣列，計算四層而非十二層，與正規形狀態數能省下的倍數相同，都是三倍。鏡射不是有效的對稱，因為它會把固定的行棋順序 A→B→C 反轉成 A→C→B。

我在執行前就發現了這一點，方法是在單顆棋子棋盤上測試兩種摺疊：六重對稱（旋轉加鏡射）破壞了解值；只用三重旋轉則保持不變。

計算執行

每個強制層在求解時的原子陣列約 30 GB；完成的層會丟掉計數器，只保留一位元組的值陣列，所以最後四層加在一起約佔 60 GB。這項工作是分散的原子寫入，所以合適的機器是大型 CPU 主機，而非 GPU。我租了一台 Hetzner CCX53：32 vCPU、128 GB RAM，有足夠餘裕把波前陣列留在記憶體中而不必換頁。

這次執行也需要一些維運配套：為每個代表層建立檢查點、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 原始殘局庫由線上局面瀏覽器提供，也以壓縮後的發行檔案公開；公開的儲存庫包含求解器、驗證工具、靜態例證與局面瀏覽器程式碼。

結語

加入第三名玩家後，「誰會贏」不再是局面本身的屬性。已經輸掉的玩家仍能決定贏家。能計算的是權力的分布：誰能強制自己獲勝，誰需要夥伴，誰只能替別人選出勝利者。

兩個已解的開局相差七個數量級，結論卻一致。和棋在三顆棋子時出現，但從不出現在對稱的起始局面。

參考資料：

Sturtevant，〈On Strongly Solving Chinese Checkers〉（Advances in Computer Games，2019）：本文延伸的兩人版求解。作者 PDF。
線上三人殘局庫局面瀏覽器：對完整三顆棋子殘局庫做精確查詢。
brianhliou/chinese-checkers-3p：Rust 求解器、驗證工具、局面瀏覽器與公開的可重現說明。
殘局庫檔案 v1：壓縮後的殘局庫檔案與清單檔。