围棋与数学

围棋是世界上最流行的游戏之一。由于其规则优美而简单，围棋一直是数学研究的灵感来源。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）（国际象棋）