六子棋是和棋:首度公開的解法
簡而言之
- 六子棋已被強解:結果是和棋,解涵蓋全部 42,372,745 個可達局面。這是首度公開的解法。
- 十六種首著落子全都是和棋,但對應手的考驗不同:先下在角點,十五種應手中有八種會輸;先下在邊中點,則沒有一種會輸。
- 只有 8% 的局面是和棋。其餘局面中,已有一方處於勝勢。
- 整個殘局庫放得進記憶體,在筆電上約一分鐘就能解完,也能在你的網頁瀏覽器中執行。
Morris 棋是三連棋類的統稱。你先把棋子放到由線構成的棋盤上,再沿線移動;自己的三顆棋子占滿一條標記線,就形成三連,可以吃掉對手一顆棋子。把對手的棋子減到三顆以下,你就贏了。
九子棋是其中最有名的一種,解出至今已超過三十年:Ralph Gasser 在 1993 年強解了它,雙方最佳著法下是和棋;Gévay 與 Danner 則在 2014 年算出整個家族的擴充解。
六子棋用的是同一個棋盤,只是拿掉了最外圈;它出現在每一份 morris 變體清單上,卻不在解棋論文裡。
打開雙方最佳著法局面瀏覽器 → 對著殘局庫走任何一條變化:每一著都依雙方最佳著法下的結果上色,綠色為勝,灰色為和棋,紅色為負。尺寸切換鈕可在每方四子、五子、六子之間切換。
這個遊戲
六子棋的棋盤是兩個同心正方形,由四條邊中點上的線相連:共 16 個點,沒有對角線。它就是九子棋棋盤拿掉外層正方形後的樣子。
每位玩家有六顆棋子。先是落子階段,雙方輪流把棋子放在空點上;十二顆全部放下後,進入移動階段,棋子可以滑到相鄰的空點。自己的三顆棋子占滿一條標記線(任一正方形的邊)就形成三連;每完成一個三連,就能吃掉一顆不在三連中的敵方棋子,除非敵方棋子全都在三連中。棋子少於三顆,或輪到你卻無法移動時,你就輸了。
我解的是不允許飛子的標準規則:只剩三顆棋子的一方仍然一次只走一步。飛子(只剩三顆的一方可以跳到任何空點)會改變著法樹;另外單獨求解後,結果同樣是和棋,所以這個結論在兩種規則下都成立。
結果
六子棋已被強解:殘局庫存有每個可達局面的值,所以從任何局面都能走出最佳著法。我從已結束的局面出發,在整個棋局範圍內逆向推算,建出這個殘局庫。
開局是和棋,白方十六種首著落子全都能守住和棋。
| 指標 | 數值 |
|---|---|
| 可達局面 | 42,372,745 |
| 勝 / 和 / 負(以行棋方計) | 23,392,364 / 3,459,385 / 15,520,996 |
同一個棋盤在棋子較少時也是和棋:
| 每方棋子數 | 可達局面 | 開局 |
|---|---|---|
| 4 | 4,111,151 | 和棋 |
| 5 | 17,844,721 | 和棋 |
| 6 | 42,372,745 | 和棋 |
這是首度公開的解法,但無法證明是史上第一。學術研究(Gasser 1996;Gévay 與 Danner 2014)裡沒有六子棋,開源解棋程式 Malom 與 Sanmill 也沒有;它們涵蓋九子棋、十二子棋、Lasker Morris 以及 Morabaraba,但不含六子棋。所以我公開了殘局庫與解棋程式,讓任何人都能查核。
全部 4200 萬個局面都放得進記憶體,所以在筆電上約一分鐘就能解完,不需要外部儲存。三個獨立的解棋程式對結果一致,四子與五子變體的結果也彼此相符;如果有更小的已解 morris 變體,它能提供的交叉驗證也就是這樣。
主要發現
沒有哪個開局是壞著,但應手是一場考驗。先下在邊中點,對手十五種應手全都仍是和棋。先下在角點,十五種中有八種會輸。在外圈角點落子後,分界沿著兩圈劃開:外圈其餘各點為和棋,整個內圈都是負。
和棋是一條窄路。這盤棋從一開始就是和棋,但和棋局面很少:4200 萬個中只有 350 萬個,約 8%。其餘 92% 的局面中,已有一方處於勝勢或敗勢。
這個家族以對角線劃分。六子棋和九子棋、Lasker Morris 一樣是和棋。唯一先手勝的 Morabaraba,也是唯一加入斜線三連的變體。
九子棋被解出了嗎?
是的,而且已經超過三十年。Ralph Gasser 強解了九子棋:雙方最佳著法下是和棋,1993 年在一份 ETH 技術報告中公布,1996 年寫成 Solving Nine Men’s Morris 收錄於 Games of No Chance。兩個年份都有人引用;1993 年是解出的年份,1996 年是論文。
Gévay 與 Danner 後來在 2014 年算出整個家族的超強解與擴充解,開源解棋程式 Malom 與 Sanmill 則涵蓋九子棋、十二子棋與 Lasker Morris。
六子棋原本是那塊空缺。補上之後,這個家族的現況如下:
| 變體 | 結果 | 首次解出 |
|---|---|---|
| 三子棋 | 先手勝 | 民間流傳 |
| 六子棋 | 和棋 | Liou,2026 |
| 九子棋 | 和棋 | Gasser,1993 |
| Lasker Morris | 和棋 | Stahlhacke,2003 |
| Morabaraba | 先手勝 | Gévay,2015 |
每個變體的結構化紀錄,連同引用來源與複雜度數字,都收在 solved-games。
結語
六子棋是和棋,它的殘局庫小到能放進記憶體、整份發佈,所以上面的局面瀏覽器能在你的網頁瀏覽器中執行完整的解。九子棋大了數千倍,需要一片一片地求解;從零重現它已知的和棋結果,是這個引擎的下一個目標,這比較像是規模問題,而非新結果。
參考資料:
- 六子棋局面瀏覽器:對著殘局庫走任何變化,每一著都標上勝、負或和棋。
- game-solver:逆向分析解棋程式與 morris 外掛,殘局庫以發行檔案提供。
- solved-games:已被解決的遊戲的結構化登錄庫,這項結果已加入其中。
- Gasser,Solving Nine Men’s Morris(Games of No Chance,1996):規模更大的同系遊戲。
- Gévay 與 Danner,Calculating Ultra-Strong and Extended Solutions for Nine Men’s Morris, Morabaraba, and Lasker Morris(2014)。