圍棋與數學

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

計算複雜性

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

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

沒有打劫的情況

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

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

日本打劫規則

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

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

禁止全局同形規則

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

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

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

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

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

圍棋特定情形的複雜性

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

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

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

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

合法局面

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

盤面大小 n×n	3n2	合法的比例	${\displaystyle L}$（合法局面）（A094777）[11]
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種選擇，這就意味着博弈樹複雜性為 10³⁶⁰。^[12] 對於理論上可能的棋局數量，包括在實際中不可能下出的棋局，Tromp和Farnebäck分別給出 10⁴⁸⁰ 的下限和 10¹⁷¹⁰ 的上限。^[9] 人們聽到最多的所有可能的棋局數量為 10⁷⁰⁰，^[13] 這個數字是361手棋的簡單排列（361! = 10⁷⁶⁸）得出的。另一個常見的推導是假設每一手棋都有 n 個選擇，總共 L 手棋，那麼棋局總量就是 N^L。就比如在某些職業對局中能夠見到的一局棋400手，按照這種方法算出來就是 361⁴⁰⁰（10¹⁰²³）種可能的棋局。

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

棋盤大小	交叉點數N	N!	平均對局手數L	NL	最長對局手數	棋局數量下限	棋局數量上限
2×2	4	24	3	64		386,356,909,593[14]	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 為最長的棋局長度，N^L 構成了下界。在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	最長棋局

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

參見

• 遊戲複雜度
• 香農數（英語：Shannon number）（國際象棋）