围棋与数学

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

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

没有打劫的情况

编辑

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

有打劫的围棋则不在PSPACE中。尽管实际的棋局似乎从没超出过

n

2

{\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证明。