围棋是世界上最流行的游戏之一。由于其规则优美而简单，围棋一直是数学研究的灵感来源。11世纪的中国学者沈括在《梦溪笔谈》中估计，围棋所有可能的局面数量为 10172 左右。近年来，約翰·H·康威在对围棋的研究中发明了超現實數，并促进了组合博弈论的发展（“围棋微数字”就是它在围棋中使用的一个具体示例）。
计算复杂性
广义围棋是在 n x n 的棋盘上进行的，在广义围棋的给定位置确定赢家的计算复杂性主要取决于打劫规则。
围棋的复杂性“几乎”是在PSPACE内的，这是因为在对弈的非打劫阶段，每一手都是不可逆的，只有通过吃子才有可能出现重复的棋形，使得复杂性提高。
没有打劫的情况
没有打劫的话，围棋是PSPACE困难的。 这是通过把PSPACE完全的TQBF（真量化布尔公式）简化到，到平面广义地理，到最高3阶的广义地理，最后简化到围棋棋盘位置。
有打劫的围棋则不在PSPACE中。尽管实际的棋局似乎从没超出过 n^2 手，但一般而言，没有人知道围棋棋局的手数是否有一个多项式上限。如果有的话，围棋就会是PSPACE完全的。就目前而言，围棋可能是PSPACE完全，EXPTIME完全，甚至EXPSPACE完全的。
日本打劫规则
日本规则只规定了基本的劫，即一手棋下了之后，如果会恢复这手棋下之前的那个棋盘状态，那么这手棋是不允许下的。如果重复多手之前的棋盘状态是允许的，这也就意味着一局棋可以永久循环，如三劫循环，即同时有三个劫，经过12手就可以循环。
在日本打劫规则下，围棋是EXPTIME完全的。
禁止全局同形规则
禁止全局同形规则是说重复出现任何先前棋盘状态都是不允许的。这是大多数中国和美国规则中使用的打劫规则。
在禁止全局同形规则下围棋的复杂性类为何，是一个未解决的问题。虽然日本打劫规则下围棋的复杂性为EXPTIME完全已被证明，但Robson的这个证明中，无论是上界还是下界的EXPTIME完全性的证明，都打破了禁止全局同形规则。
Robson和西洋跳棋都是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）上所有可能的合法局面的数目。随着棋盘变大，合法局面的比例也会降低。
博弈树复杂性
電腦科學家Victor Allis指出，职业棋士之间对弈一般在150手左右，平均每手约250种选择，这就意味着博弈树复杂性为 10360。 对于理论上可能的棋局数量，包括在实际中不可能下出的棋局，Tromp和Farnebäck分别给出 10480 的下限和 101710 的上限。 这个数字是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.
*
*
*
外部链接
- [https://web.archive.org/web/20070611031147/http://msoworld.com/mindzine/news/orient/go/special/gomath.html Go and Mathematics]
- [http://senseis.xmp.net/?NumberOfPossibleOutcomesOfAGame Number of possible outcomes of a game] - article at Sensei's Library
评论 (0)