围棋与数学

围棋是世界上最流行的游戏之一。由于其规则优美而简单，围棋一直是数学研究的灵感来源。11世纪的中国学者沈括在《梦溪笔谈》中估计，围棋所有可能的局面数量为 10172 左右。近年来，約翰·H·康威在对围棋的研究中发明了超現實數，并促进了的发展（“围棋微数字”就是它在围棋中使用的一个具体示例）。

计算复杂性

广义围棋是在 n x n 的棋盘上进行的，在广义围棋的给定位置确定赢家的计算复杂性主要取决于打劫规则。

围棋的复杂性“几乎”是在PSPACE内的，这是因为在对弈的非打劫阶段，每一手都是不可逆的，只有通过吃子才有可能出现重复的棋形，使得复杂性提高。

没有打劫的情况

没有打劫的话，围棋是PSPACE困难的。 这是通过把PSPACE完全的TQBF（真量化布尔公式）简化到，到平面广义地理，到最高3阶的广义地理，最后简化到围棋棋盘位置。

有打劫的围棋则不在PSPACE中。尽管实际的棋局似乎从没超出过  手，但一般而言，没有人知道围棋棋局的手数是否有一个多项式上限。如果有的话，围棋就会是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 的矩形棋盘的合法局面  的递归公式。 在2016年算出了  的准确数字。他们还发现了一个渐进公式 ，其中 ，，。据估计，可观测宇宙包含大约 1080 个原子，远小于常规围棋棋盘（m=n=19）上所有可能的合法局面的数目。随着棋盘变大，合法局面的比例也会降低。

博弈树复杂性

電腦科學家Victor Allis指出，职业棋士之间对弈一般在150手左右，平均每手约250种选择，这就意味着博弈树复杂性为 10360。 对于理论上可能的棋局数量，包括在实际中不可能下出的棋局，Tromp和Farnebäck分别给出 10480 的下限和 101710 的上限。
人们听到最多的所有可能的棋局数量为 10700， 这个数字是361手棋的简单排列（361! = 10768）得出的。另一个常见的推导是假设每一手棋都有 n 个选择，总共 L 手棋，那么棋局总量就是 NL。就比如在某些职业对局中能够见到的一局棋400手，按照这种方法算出来就是 361400（101023）种可能的棋局。

所有可能的对局总数是棋盘大小和手数的函数。虽然大多数棋局都在400手以内，甚至200手都不到，但棋局是有可能更长的。

所有可能的对局总数可以通过多种方式从棋盘大小估算，有些方式会比另外一些更严格。最简单的，棋盘大小的简单排列 (N)L，没有考虑到非法吃子，以及非法的盘面。令 N 为棋盘大小（19×19=361），L 为最长的棋局长度，NL 构成了下界。在Tromp/Farnebäck的论文中给出了更精确的限制。

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

围棋
组合博弈论
趣味數學