三人中國跳棋，已被解決
中國跳棋是一場橫越六角星的競速。把你的棋子從一個尖角移到對面的尖角。沒有吃子，沒有子力，只有移動與阻擋。
.jpg){kind=link}
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,245 個可達局面。一顆棋子無法封死目標區，所以沒有和棋。它的作用是校準：小到可以用兩種獨立方法求解並手動核對。
每個可達局面都歸入以下四類之一：
| 控制類型 | 局面數 |
|---|---|
| 終端（有人已獲勝） | 171 |
| 單獨勝（一位玩家逼出自己的勝利） | 834 |
| 造王者（敗方決定勝者） | 240 |
| 攪局和棋 | 0 |
| 可達局面總數 | 1,245 |
棋盤上五分之一的可達局面已經屬於造王者領域。以下是那 240 個局面之一，加上由此出發的兩種合法選擇：
輪到 B 行棋，而 B 無法獲勝。一種走法把必勝交給 A；另一種把必勝交給 C。B 已經輸了，卻仍決定整局的結果。
單獨逼迫層在逆向分析第 9 輪解決完畢。有序的造王者問題跑得更久，到第 13 輪與第 15 輪，因為它們要求更具體的結果：不只是「這位玩家能否獲勝」，而是「這位玩家能否幫助另一位玩家獲勝」。開局的結論與三子遊戲一致：沒有單獨勝，任一對玩家都能排除第三人，六組有序造王者關係全部成立。
第二階：三顆棋子
結果與規模
每人三子，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 個列舉出的擺放同時填滿了兩個目標尖角，這在合法對局中不會出現，求解器把它們標為非法，而不是勝、負或和。
與第一階相比，三顆棋子改變了規模，卻沒有改變開局的控制結構：
- 不變：對稱起始局面在兩階都是純粹的造王者局面：沒有單獨勝，任兩人可逼出第三人，六組造王者關係全部成立。
- 新增：和棋。單獨一位玩家能逼出永久封鎖，這在一子版不可能發生。
- 更深：一子的單獨層在 9 輪內解決；三子的單獨層跑了 53 輪，解決量的高峰落在第 10 至 13 輪，而不是距終端一著之處。
開局仍是造王者局面
三子開局的評估結果與一子開局完全相同。沒有玩家能逼出自己的勝利。任兩位玩家能逼出第三人。沒有單獨玩家能逼出和棋。六組有序造王者關係全部成立：A 能把勝利交給 B 或 C，B 能交給 A 或 C，C 能交給 A 或 B。
這種平衡維持了一段時間。從起始局面做廣度優先搜尋發現，到第 8 層為止的每個可達局面仍屬造王者類。到了第 9 層，首批非造王者局面出現：在 1,906,964 個新到達的局面中，41 個是單獨勝，1 個是攪局和棋。其餘 1,906,922 個仍是造王者。
下方的小工具展示兩個最短的見證。不要把它們當成好的開局下法。它們只是殘局庫標記首次改變的可達局面。
兩條路線的開頭相同。B 的早期一著不同，九著之後標記就分歧了：
- A 的首個單獨勝：局面已變成 A 能逼出自己勝利的局面。
- A 的首個攪局和棋：局面已變成 A 仍無法獲勝，但能逼出重複局面。
這是可達性的事實，不是關於最佳開局下法的論斷。它說的是從對稱起始局面算起，殘局庫直到第 9 層才遇到單獨勝或攪局和棋的標記。
和棋與造王者
一子棋盤沒有任何和棋局面。三子棋盤有每位玩家 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 贏這類循環偏好。這些處理會把許多造王者局面收斂到特定勝者，但答案將取決於偏好，而不是強解的一部分。
另一種延伸則改變目標本身。本次求解在第一位玩家填滿目標區時停止。如果玩家在意拿第二名，遊戲就需要排名式的目標，或是在首位勝者出現後仍繼續的規則。那會衡量另一件事：不只是誰能贏，而是第二名的誘因如何改變封鎖與造王。
第三階：六顆棋子
下一階自然是每人六子，但棋盤慣例很重要。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²⁰ |
| 相對第二階的增幅 | 約 876 億倍 |
這些界限來自第二階所用的同一套通道受限列舉器，而不是「棋子可在任何位置」的原始計數：每位玩家的六顆棋子被限制在該玩家的兩個私有角落加上共用的 37 格中央區，計數則對每位玩家放進共用中央區的棋子數量求和。接著，精確的三重旋轉對稱把擺放×輪次狀態除以 3。可達性不會把問題縮小好幾個數量級。中國跳棋沒有吃子且可逆，而在較小的棋盤上，可達比例很快就逼近整個通道受限空間。
直接把目前的解法放大是做不到的。第二階最終殘局庫是 14.84 GB；同樣的表示法在六子時大約會是 1.3 ZB。第二階的計算執行花了 7.4 小時；只按正規化狀態數相乘就得出數千萬機器年，還沒算進更大的分支度、記憶體流量、檢查點與 I/O。
六子屬於未來工作，起點是新的範圍界定階段，而不是跑得更久：更強的壓縮、外部記憶體或分散式逆向分析、考慮可達性的索引、更好的成本模型，以及很可能需要的資金或捐贈的運算資源。工程問題會變得和賽局理論問題一樣有意思。
求解器如何執行
這次求解是以 Rust 撰寫、涵蓋 148 億個局面的逆向分析。它把局面編號到密集陣列的槽位，按需產生著法，求解四個代表性的逼迫層，再由旋轉推導出其餘八層，並把結果打包成本地殘局庫。有四項工程決策至關重要。
索引
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，〈論強解中國跳棋〉（Advances in Computer Games，2019）：本文延伸的兩人版求解。作者 PDF。
- 線上三人殘局庫局面瀏覽器：對完整三子殘局庫做精確查詢。
- brianhliou/chinese-checkers-3p：Rust 求解器、驗證框架、局面瀏覽器與公開的可重現性說明。
- 殘局庫檔案 v1：壓縮的殘局庫檔案與清單。