迷你圍棋之奧妙（一）：二路圍棋

03-31

　　常規的圍棋盤縱橫十九道，變化無窮。十九路以下的小棋盤，常見的有九路、十三路等。小棋盤常用於新手入門的教學，常為資深棋迷忽視。然而，小棋盤上也有奇異的妙趣，以及超乎想像的繁多變化。本系列邀請各位讀者走進小棋盤的世界。

　　日前，某圍棋教育機構被曝「長期使用二路棋盤」教育小朋友入門，遭業內人士一致口誅筆伐。二路棋盤如下圖，一共只有４個交叉點。

讀者即使不太了解圍棋，大概也會覺得「這實在是太簡單了」。用二路棋盤教棋固然是不負責任的圈錢行為，怎麼批判都不為過。但是，二路棋盤像看上去的那麼簡單么？請問，二路棋盤，無貼目，在現行中國規則下，雙方最優解對應什麼結果？

好像沒有什麼稀奇的，黑走一步，白走對角，就雙活了嘛。

所以結果是和棋咯？「等等，要是黑棋繼續走……」

黑棋固然先送死了兩兄弟，但棋局神奇地可以繼續下去。五步棋以後，似乎又回到了最初的起點，只是棋盤旋轉了90°而已。如此看來，棋局可以無限循環下去。如果是日本規則，棋局確實可以無限循環下去。不過，黑棋走了半天，送死三個兄弟，又吃回三個敵人，在日本規則下做了無用功。因此日本規則下的最優解就是在兩步棋以後不動了，和棋。

但是，中國規則有禁循環（也稱禁全同）一條，使得結果變得完全不同。所謂禁循環，就是不允許走出重複的局面[1]。2乘2棋盤上的局面數是有限的，因此棋局不能無限進行下去。研究涉及禁循環的問題，最嚴謹的辦法是把所有局面列舉出來。二路棋盤有4個交叉點，每個交叉點可能有{空、黑、白}三種狀態，因此共有3x3x3x3=81種局面。但沒有氣的局面是非法的，共24種，列舉如下：

合法的局面尚有57種，可以用下圖概括。

上圖中，旋轉或鏡面對稱的局面被分為一組，且用箭頭指示各局面間「一步到達」的關係。注意，旋轉或鏡面對稱的局面並不等同，因為禁循環規則下走到對稱的局面並不犯規。

圖中表示遊戲樹的方法，在圖論中被稱為有向圖（Directed Graph）；每個局面是一個頂點（node），連接頂點的箭頭稱為邊（edge）。一局棋從空枰出發，走了若干步以後終止；這對應上圖中從空枰頂點出發的一條道路（path）。禁循環規則等價於棋局對應的道路不能重複經過某個節點。這樣的路徑又稱簡單道路。

問題來了，這張圖上共有多少條簡單道路呢？換句話說，在中國規則下，二路棋盤共有多少種可能的棋局呢？答案是驚人的386356909593種，也就是三千八百六十三億種。荷蘭科學家、圍棋愛好者John Tromp藉助程序窮舉計數，解答了這一問題。

有讀者可能會反駁，這三千多億種棋局中，絕大多數都是無用的、真實的棋手不可能會這麼走的。確實如此嗎？我們回到本文開頭的問題：二路棋盤中國規則下的最優結果。答案不是和棋，而是黑勝一子！驚喜不驚喜？意外不意外？

結果如圖：黑二子，白一子，黑勝一子。事實上，如果是上帝的左右手互搏，棋局只需要進行這三手就可以宣告結束。如果白棋繼續抵抗，則黑棋至少可以保全勝利果實。下圖是一種可能的進程：

至此白棋不能繼續，否則重複了第三圖。白棋被迫停招，黑棋繼續如下：

至此黑棋可以選擇停招，而白棋也不能繼續，否則重複上面倒數第二圖。兩棄終局，黑棋仍以一子勝。

篇幅所限，筆者只能舉出萬千變化中的一種。黑白雙方仍有不計其數的其它選擇，以人力難以窮盡。另一位荷蘭圍棋愛好者、軟體工程師Erik van der Werf 藉助自編程序MIGOS暴力搜索[2]，確認了黑勝一子的結果。

二路棋盤上還有一個未解問題：在禁循環規則下，最長的一局棋長度是多少? John對此做了一些實驗，曾經找到過長達40手的棋局，但不能確認其是否為最長。可以證明的是，不存在長度57手，也就是遍歷所有合法局面的一局棋。對於有向圖，遍歷所有頂點的道路又稱哈密頓道路（Hamiltonian Path）。利用程序尋找哈密頓道路的計算成本較高。不過，我們可以用純邏輯推理解決本題。對於二路棋盤的遊戲樹，如果存在哈密頓道路，則這條道路串聯57個節點，恰好有56條邊。

再次觀察二路棋盤的完整遊戲樹。注意第一行第二類局面

和第三行第一類局面

，它們合起來只能走向

和

兩類局面，共八個。前面的十個局面合起來本應至少指向九個其它局面，否則不能構成哈密頓道路的一部分，實際上它們至多只指向八個。因此，該圖中不存在哈密頓道路，即不存在遍歷所有局面的一盤棋。

至於最長的二路棋局究竟有多長，就交給有興趣的讀者去嘗試了。

（本系列剩餘部分計劃涵蓋３＼４＼５＼６＼７路棋盤、不規則小棋盤、9路棋盤以及13路棋盤，但暫時不會公開發布，須等待本系列與本專欄其它部分文章集結出版後再發布。）

參考文獻：J. Tromp & G. Farnerback, Combinatorics of Go

此處採用最嚴格的PSK表述。禁循環另有較寬鬆的SSK規則，即禁止使對方重複面對其曾經面對的局面。中國規則禁循環一條的表述較含糊，有PSK和SSK兩種解釋。
窮舉小棋盤圍棋是Erik van der Werf博士論文的一部分。