围棋与数学

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