圍棋與數學

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

計算複雜性[編輯]

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

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

沒有打劫的情況[編輯]

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

有打劫的圍棋則不在PSPACE中。儘管實際的棋局似乎從沒超出過 $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完全的。不過這個結果不適用於圍棋。

圍棋特定情形的複雜性[編輯]

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

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

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

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

合法局面[編輯]

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

盤面大小 n×n	3^n²	合法的比例	$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×10³⁸	23.44%	1.03919148791×10³⁸
13×13	4.30023359390×10⁸⁰	8.66%	3.72497923077×10⁷⁹
19×19	1.74089650659×10¹⁷²	1.20%	2.08168199382×10¹⁷⁰

博弈樹複雜性[編輯]

電腦科學家 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	N^L	最長對局手數	棋局數量下限	棋局數量上限
2×2	4	24	3	64		386,356,909,593^[14]	386,356,909,593
3×3	9	3.6×10⁵	5	5.9×10⁴
4×4	16	2.1×10¹³	9	6.9×10¹⁰
5×5	25	1.6×10²⁵	15	9.3×10²⁰
9×9	81	5.8×10¹²⁰	45	7.6×10⁸⁵
13×13	169	4.3×10³⁰⁴	90	3.2×10²⁰⁰
19×19	361	1.0×10⁷⁶⁸	200	3×10⁵¹¹	10⁴⁸	10^10⁴⁸	10^10¹⁷¹
21×21	441	2.5×10⁹⁷⁶	250	1.3×10⁶⁶¹

所有可能的對局總數可以通過多種方式從棋盤大小估算，有些方式會比另外一些更嚴格。最簡單的，棋盤大小的簡單排列 (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×10¹²⁶		7.5×10¹²⁷
100	1.4×10²⁴⁹		5.6×10²⁵⁵
150	6.4×10³⁶⁷		4.2×10³⁸³
200	1.9×10⁴⁸¹		3.2×10⁵¹¹
250	8.2×10⁵⁸⁷		2.4×10⁶³⁹
300	2.8×10⁶⁸⁴		7.8×10⁷⁶⁶
350	3.6×10⁷⁶⁰		1.3×10⁸⁹⁵
361	1.4×10⁷⁶⁸		1.8×10⁹²³	使用181個黑子和180個白子的最長棋局
400	n/a		1.0×10¹⁰²³	最長職業對局
500	n/a		5.7×10¹²⁷⁸
1000	n/a		3.2×10²⁵⁵⁷
4700萬	n/a		10^10⁸	361³ 手棋
10⁴⁸	n/a	10^10⁴⁸	10^10¹⁷¹	最長棋局

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

參見[編輯]

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

註釋[編輯]

^ Go Infinitesimals. [2018-04-26]. （原始內容存檔於2017-11-07）.
^ ^2.0 ^2.1 Lichtenstein, David; Sipser, Michael. Go Is Polynomial-Space Hard (PDF). Journal of the ACM. April 1980, 27 (2): 393–401 [2018-04-26]. doi:10.1145/322186.322201. （原始內容存檔 (PDF)於2017-08-08）.
^ ^3.0 ^3.1 Robson, John. The complexity of Go. Proceedings of the IFIP 9th World Computer Congress on Information Processing. 1983: 413–417.
^ ^4.0 ^4.1 Robson, J. Combinatorial games with exponential space complete decision problems. Proceedings of the Mathematical Foundations of Computer Science. 1984: 498–506. doi:10.1007/BFb0030333.
^ Aviezri Fraenkel and D. Lichtenstein. Computing a perfect strategy for n×n chess requires time exponential in n. J. Comb. Th. A. 1981, (31): 199–214. doi:10.1016/0097-3165(81)90016-9.
^ J. M. Robson. N by N checkers is Exptime complete. SIAM Journal on Computing. 1984, 13 (2): 252–267. doi:10.1137/0213018.
^ Wolfe, David. Nowakowski, Richard J. , 編. Go endgames are PSPACE-hard (PDF). More Games of No Chance, Mathematical Sciences Research Institute Publications 42 (Cambridge University Press). 2002: 125–136 [2018-04-26]. （原始內容存檔 (PDF)於2017-08-10）.
^ Crâşmaru, Marcel; Tromp, John. Ladders are PSPACE-Complete. Computers and Games, volume 2063 of Lecture Notes in Computer Science (Springer). 2000. doi:10.1007/3-540-45579-5_16.
^ ^9.0 ^9.1 Tromp, J; Farnebäck, G, Combinatorics of Go, Springer, Berlin, Heidelberg, 2007, ISBN 978-3-540-75537-1, doi:10.1007/978-3-540-75538-8_8
^ https://tromp.github.io/go/legal.html （頁面存檔備份，存於互聯網檔案館） 208 168 199 381 979 984 699 478 633 344 862 770 286 522 453 884 530 548 425 639 456 820 927 419 612 738 015 378 525 648 451 698 519 643 907 259 916 015 628 128 546 089 888 314 427 129 715 319 317 557 736 620 397 247 064 840 935
^ 存档副本 (PDF). [2018-04-26]. （原始內容存檔 (PDF)於2017-10-26）.
^ Allis 1994
^ AGA – top ten reason to play Go
^ Tromp 1999

參考文獻[編輯]

AGA. Top Ten Reasons to Play Go. [2018-04-26]. （原始內容存檔於2012-05-30）.
Allis, Victor. Searching for Solutions in Games and Artificial Intelligence (PDF). Ph.D. Thesis, University of Limburg, Maastricht, The Netherlands. 1994 [2018-04-26]. ISBN 90-900748-8-0. （原始內容 (PDF)存檔於2018-08-20）.
Hearn, Robert A. Games, Puzzles, and Computation (PDF). 2006 [2018-04-26]. （原始內容存檔 (PDF)於2008-05-28）. [Ph.D. Thesis, MIT.]
Johnson, George. To Test a Powerful Computer, Play an Ancient Game. New York Times. 1997-07-29.
Papadimitriou, Christos (1994), Computational Complexity, Addison Wesley.
Tromp, John. Number of 2×2 games with positional superko. 1999 [2018-04-26]. （原始內容存檔於2012-10-26）.
Tromp, John. Number of legal Go positions (up to 19×19). 2005 [2018-04-26]. （原始內容存檔於2016-02-06）.
Tromp, John; Farnebäck, Gunnar. Combinatorics of Go. 2007 [2018-04-26]. （原始內容存檔於2017-01-18）.

外部連結[編輯]

Go and Mathematics
Number of possible outcomes of a game（頁面存檔備份，存於互聯網檔案館） - article at Sensei's Library

[1] Go Infinitesimals. [2018-04-26]. （原始內容存檔於2017-11-07）.

[sipser1980-2] 2.0 ^2.1 Lichtenstein, David; Sipser, Michael. Go Is Polynomial-Space Hard (PDF). Journal of the ACM. April 1980, 27 (2): 393–401 [2018-04-26]. doi:10.1145/322186.322201. （原始內容存檔 (PDF)於2017-08-08）.

[robson1983-3] 3.0 ^3.1 Robson, John. The complexity of Go. Proceedings of the IFIP 9th World Computer Congress on Information Processing. 1983: 413–417.

[robson1984-4] 4.0 ^4.1 Robson, J. Combinatorial games with exponential space complete decision problems. Proceedings of the Mathematical Foundations of Computer Science. 1984: 498–506. doi:10.1007/BFb0030333.

[Fraenkel1981-5] Aviezri Fraenkel and D. Lichtenstein. Computing a perfect strategy for n×n chess requires time exponential in n. J. Comb. Th. A. 1981, (31): 199–214. doi:10.1016/0097-3165(81)90016-9.

[robson1984checkers-6] J. M. Robson. N by N checkers is Exptime complete. SIAM Journal on Computing. 1984, 13 (2): 252–267. doi:10.1137/0213018.

[7] Wolfe, David. Nowakowski, Richard J. , 編. Go endgames are PSPACE-hard (PDF). More Games of No Chance, Mathematical Sciences Research Institute Publications 42 (Cambridge University Press). 2002: 125–136 [2018-04-26]. （原始內容存檔 (PDF)於2017-08-10）.

[8] Crâşmaru, Marcel; Tromp, John. Ladders are PSPACE-Complete. Computers and Games, volume 2063 of Lecture Notes in Computer Science (Springer). 2000. doi:10.1007/3-540-45579-5_16.

[Tromp_and_Farnebäck_2007-9] 9.0 ^9.1 Tromp, J; Farnebäck, G, Combinatorics of Go, Springer, Berlin, Heidelberg, 2007, ISBN 978-3-540-75537-1, doi:10.1007/978-3-540-75538-8_8

[10] ttps://tromp.github.io/go/legal.html （頁面存檔備份，存於互聯網檔案館） 208 168 199 381 979 984 699 478 633 344 862 770 286 522 453 884 530 548 425 639 456 820 927 419 612 738 015 378 525 648 451 698 519 643 907 259 916 015 628 128 546 089 888 314 427 129 715 319 317 557 736 620 397 247 064 840 935

[11] 存档副本 (PDF). [2018-04-26]. （原始內容存檔 (PDF)於2017-10-26）.

[12] Allis 1994

[top_ten-13] AGA – top ten reason to play Go

[14] Tromp 1999

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]