围棋是世界上最流行的游戏之一。由于其规则优美而简单,围棋一直是数学研究的灵感来源。11世纪的中国学者沈括在《梦溪笔谈》中估计,围棋所有可能的局面数量为 10172 左右。近年来,约翰·H·康威在对围棋的研究中发明了超现实数,并促进了组合博弈论的发展(“围棋微数字”[1]就是它在围棋中使用的一个具体示例)。
计算复杂性
广义围棋是在 n x n 的棋盘上进行的,在广义围棋的给定位置确定赢家的计算复杂性主要取决于打劫规则。
围棋的复杂性“几乎”是在PSPACE内的,这是因为在对弈的非打劫阶段,每一手都是不可逆的,只有通过吃子才有可能出现重复的棋形,使得复杂性提高。
没有打劫的话,围棋是PSPACE困难的。[2] 这是通过把PSPACE完全的TQBF(真量化布尔公式)简化到广义地理,到平面广义地理,到最高3阶的广义地理,最后简化到围棋棋盘位置。
有打劫的围棋则不在PSPACE中。尽管实际的棋局似乎从没超出过 手,但一般而言,没有人知道围棋棋局的手数是否有一个多项式上限。如果有的话,围棋就会是PSPACE完全的。就目前而言,围棋可能是PSPACE完全,EXPTIME完全,甚至EXPSPACE完全的。
日本规则只规定了基本的劫,即一手棋下了之后,如果会恢复这手棋下之前的那个棋盘状态,那么这手棋是不允许下的。如果重复多手之前的棋盘状态是允许的,这也就意味着一局棋可以永久循环,如三劫循环,即同时有三个劫,经过12手就可以循环。
禁止全局同形规则是说重复出现任何先前棋盘状态都是不允许的。这是大多数中国和美国规则中使用的打劫规则。
在禁止全局同形规则下围棋的复杂性类为何,是一个未解决的问题。虽然日本打劫规则下围棋的复杂性为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 的棋盘总共有 3n2 种可能的局面;但只有一部分是合法的。Tromp和Farnebäck推导了长 m 宽 n 的矩形棋盘的合法局面 的递归公式。[9] 在2016年算出了 的准确数字[10]。他们还发现了一个渐进公式 ,其中 ,,。据估计,可观测宇宙包含大约 1080 个原子,远小于常规围棋棋盘(m=n=19)上所有可能的合法局面的数目。随着棋盘变大,合法局面的比例也会降低。
盘面大小 n×n | 3n2 | 合法的比例 | (合法局面)(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种选择,这就意味着博弈树复杂性为 10360。[12] 对于理论上可能的棋局数量,包括在实际中不可能下出的棋局,Tromp和Farnebäck分别给出 10480 的下限和 101710 的上限。[9] 人们听到最多的所有可能的棋局数量为 10700,[13] 这个数字是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[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 为最长的棋局长度,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万秒)。
参见
- 游戏复杂度
- 香农数(国际象棋)
注释
参考文献
外部链接
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.