圍棋與數學

圍棋是世界上最流行的遊戲之一。由於其規則優美而簡單，圍棋一直是數學研究的靈感來源。11世紀的中國學者沈括在《夢溪筆談》中估計，圍棋所有可能的局面數量為 10172 左右。近年來，約翰·H·康威在對圍棋的研究中發明了超現實數，並促進了組合博弈論的發展（「圍棋微數字」就是它在圍棋中使用的一個具體示例）。

## 計算複雜性

廣義圍棋是在 n x n 的棋盤上進行的，在廣義圍棋的給定位置確定贏家的計算複雜性主要取決於打劫規則。

圍棋的複雜性「幾乎」是在PSPACE內的，這是因為在對弈的非打劫階段，每一手都是不可逆的，只有通過吃子才有可能出現重複的棋形，使得複雜性提高。

### 沒有打劫的情況

沒有打劫的話，圍棋是PSPACE困難的。這是通過把PSPACE完全的TQBF（真量化布爾公式）簡化到廣義地理，到平面廣義地理，到最高3階的廣義地理，最後簡化到圍棋棋盤位置。

有打劫的圍棋則不在PSPACE中。儘管實際的棋局似乎從沒超出過 $n^2$ 手，但一般而言，沒有人知道圍棋棋局的手數是否有一個多項式上限。如果有的話，圍棋就會是PSPACE完全的。就目前而言，圍棋可能是PSPACE完全，EXPTIME完全，甚至EXPSPACE完全的。

### 日本打劫規則

日本規則只規定了基本的劫，即一手棋下了之後，如果會恢復這手棋下之前的那個棋盤狀態，那麼這手棋是不允許下的。如果重複多手之前的棋盤狀態是允許的，這也就意味著一局棋可以永久循環，如三劫循環，即同時有三個劫，經過12手就可以循環。

在日本打劫規則下，圍棋是EXPTIME完全的。

### 禁止全局同形規則

禁止全局同形規則是說重複出現任何先前棋盤狀態都是不允許的。這是大多數中國和美國規則中使用的打劫規則。

在禁止全局同形規則下圍棋的複雜性類為何，是一個未解決的問題。雖然日本打劫規則下圍棋的複雜性為EXPTIME完全已被證明，但Robson的這個證明中，無論是上界還是下界的EXPTIME完全性的證明，都打破了禁止全局同形規則。

至少現在已知，其複雜性至少是PSPACE困難，因為中對圍棋的PSPACE困難性的證明是不依賴於打劫規則的，或者說即便是沒有打劫規則，也是PSPACE困難的。現在還知道圍棋的複雜性是在EXPSPACE內的。

Robson證明了如果在EXPTIME完全的雙人遊戲的基礎上，加上「禁止全局同形」的規則，遊戲複雜性將會變為EXPSPACE完全。直觀地說，這是因為對加入新規則的遊戲來說，即便是確定一個局面下符合規則的下法，都需要指數級別的空間，因為從開局下到某一局面的長度是有可能達到指數級別的。

因此，廣義西洋棋和西洋跳棋的禁止全局同形版本都是EXPSPACE完全的，因為廣義西洋棋和西洋跳棋都是EXPTIME完全的。不過這個結果不適用於圍棋。

### 圍棋特定情形的複雜性

當棋盤被活子把棋盤分割成若干孤立的區域的時候，圍棋就進入了官子階段，這時每個局部區域都會有一個多項式級別的規範博弈樹。用組合博弈論的話來說，當圍棋分解成具有多項式級別規範博弈樹的子博弈之和時，就會進入官子。

在這個定義下，圍棋的收官是PSPACE困難的。

這可以通過將PSPACE完全的QBF（Quantified Boolean Formula）問題轉換成小型（多項式級別規範博弈樹）圍棋子遊戲的總和來證明。請注意，論文並未證明圍棋是在PSPACE中的，所以就有不是PSPACE完全的可能性。

確定哪一方征子有利是PSPACE完全的，無論是日本打劫規則還是禁止全局同形規則。這一點（PSPACE完全）可以通過模仿QBF證明。

## 合法局面

由於棋盤上每個位置都可以為空、白棋、黑棋三種情況，所以對於邊長為 n 的棋盤總共有 3n2 種可能的局面；但只有一部分是合法的。Tromp和Farnebäck推導了長 m 寬 n 的矩形棋盤的合法局面 $L(m,n)$ 的遞歸公式。在2016年算出了 $L(19,19)$ 的準確數字。他們還發現了一個漸進公式 $L\approx AB^{m+n}C^{mn}$，其中 $A\approx 0.8506399258457145$，$B\approx 0.96553505933837387$，$C\approx 2.975734192043357249381$。據估計，可觀測宇宙包含大約 1080 個原子，遠小於常規圍棋棋盤（m=n=19）上所有可能的合法局面的數目。隨著棋盤變大，合法局面的比例也會降低。

盤面大小 n×n｜3n2｜合法的比例｜$L$（合法局面）（A094777）

1×1｜3｜33.33%｜1

2×2｜81｜70.37%｜57

3×3｜19,683｜64.40%｜12,675

4×4｜43,046,721｜56.49%｜24,318,165

5×5｜847,288,609,443｜48.90%｜414,295,148,741

9×9｜4.43426488243×1038｜23.44%｜1.03919148791×1038

13×13｜4.30023359390×1080｜8.66%｜3.72497923077×1079

19×19｜1.74089650659×10172｜1.20%｜2.08168199382×10170

## 博弈樹複雜性

電腦科學家Victor Allis指出，職業棋士之間對弈一般在150手左右，平均每手約250種選擇，這就意味著博弈樹複雜性為 10360。對於理論上可能的棋局數量，包括在實際中不可能下出的棋局，Tromp和Farnebäck分別給出 10480 的下限和 101710 的上限。

人們聽到最多的所有可能的棋局數量為 10700，這個數字是361手棋的簡單排列（361! = 10768）得出的。另一個常見的推導是假設每一手棋都有 n 個選擇，總共 L 手棋，那麼棋局總量就是 NL。就比如在某些職業對局中能夠見到的一局棋400手，按照這種方法算出來就是 361400（101023）種可能的棋局。

所有可能的對局總數是棋盤大小和手數的函數。雖然大多數棋局都在400手以內，甚至200手都不到，但棋局是有可能更長的。

棋盤大小｜交叉點數N｜N!｜平均對局手數L｜NL｜最長對局手數｜棋局數量下限｜棋局數量上限

2×2｜4｜24｜3｜64｜386,356,909,593｜386,356,909,593

3×3｜9｜3.6×105｜5｜5.9×104

4×4｜16｜2.1×1013｜9｜6.9×1010

5×5｜25｜1.6×1025｜15｜9.3×1020

9×9｜81｜5.8×10120｜45｜7.6×1085

13×13｜169｜4.3×10304｜90｜3.2×10200

19×19｜361｜1.0×10768｜200｜3×10511｜1048｜101048｜1010171

21×21｜441｜2.5×10976｜250｜1.3×10661

所有可能的對局總數可以通過多種方式從棋盤大小估算，有些方式會比另外一些更嚴格。最簡單的，棋盤大小的簡單排列 (N)L，沒有考慮到非法吃子，以及非法的盤面。令 N 為棋盤大小（19×19=361），L 為最長的棋局長度，NL 構成了下界。在Tromp/Farnebäck的論文中給出了更精確的限制。

最長棋局 L (19×19)｜(N)L｜棋局數量的下界｜棋局數量的上界｜注釋

1｜361｜361｜361｜白棋第一手就認輸了，就會有361種棋局，如果忽略掉所有對稱性就是55種。

2｜722｜721｜黑棋在白棋第一手後就認輸了，就會有721種棋局，忽略掉所有對稱性就是189種。

50｜2.1×10126｜7.5×10127

100｜1.4×10249｜5.6×10255

150｜6.4×10367｜4.2×10383

200｜1.9×10481｜3.2×10511

250｜8.2×10587｜2.4×10639

300｜2.8×10684｜7.8×10766

350｜3.6×10760｜1.3×10895

361｜1.4×10768｜1.8×10923｜使用181個黑子和180個白子的最長棋局

400｜n/a｜1.0×101023｜最長職業對局

500｜n/a｜5.7×101278

1000｜n/a｜3.2×102557

4700萬｜n/a｜10108｜3613 手棋

1048｜n/a｜101048｜1010171｜最長棋局

10700 這個數字對於200手以內的所有棋局來說是一種高估，但對361手以內的所有棋局來說是一種低估。而4700萬手的棋，在一秒一手、每天下16個小時的情況下，也要下2¼年（一年有3100萬秒）。

## 參考文獻

- Ph.D. Thesis, MIT.
- Papadimitriou, Christos (1994), Computational Complexity, Addison Wesley.

## 外部連結

- Go and Mathematics
- Number of possible outcomes of a game - article at Sensei's Library