围棋与数学
围棋是世界上最流行的游戏之一。由于其规则优美而简单，围棋一直是数学研究的灵感来源。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万秒）。
参见 编辑
注释 编辑
- ^ Go Infinitesimals. [2018-04-26]. （原始内容存档于2017-11-07）.
- ^ 2.0 2.1 Lichtenstein, David; Sipser, Michael. Go Is Polynomial-Space Hard (PDF). Journal of the ACM. April 1980, 27 (2): 393–401 [2018-04-26]. doi:10.1145/322186.322201. （原始内容存档 (PDF)于2017-08-08）.
- ^ 3.0 3.1 Robson, John. The complexity of Go. Proceedings of the IFIP 9th World Computer Congress on Information Processing. 1983: 413–417.
- ^ 4.0 4.1 Robson, J. Combinatorial games with exponential space complete decision problems. Proceedings of the Mathematical Foundations of Computer Science. 1984: 498–506. doi:10.1007/BFb0030333.
- ^ Aviezri Fraenkel and D. Lichtenstein. Computing a perfect strategy for n×n chess requires time exponential in n. J. Comb. Th. A. 1981, (31): 199–214. doi:10.1016/0097-3165(81)90016-9.
- ^ J. M. Robson. N by N checkers is Exptime complete. SIAM Journal on Computing. 1984, 13 (2): 252–267. doi:10.1137/0213018.
- ^ Wolfe, David. Nowakowski, Richard J. , 编. Go endgames are PSPACE-hard (PDF). More Games of No Chance, Mathematical Sciences Research Institute Publications 42 (Cambridge University Press). 2002: 125–136 [2018-04-26]. （原始内容存档 (PDF)于2017-08-10）.
- ^ Crâşmaru, Marcel; Tromp, John. Ladders are PSPACE-Complete. Computers and Games, volume 2063 of Lecture Notes in Computer Science (Springer). 2000. doi:10.1007/3-540-45579-5_16.
- ^ 9.0 9.1 Tromp, J; Farnebäck, G, Combinatorics of Go, Springer, Berlin, Heidelberg, 2007, ISBN 978-3-540-75537-1, doi:10.1007/978-3-540-75538-8_8
- ^ https://tromp.github.io/go/legal.html （页面存档备份，存于互联网档案馆） 208 168 199 381 979 984 699 478 633 344 862 770 286 522 453 884 530 548 425 639 456 820 927 419 612 738 015 378 525 648 451 698 519 643 907 259 916 015 628 128 546 089 888 314 427 129 715 319 317 557 736 620 397 247 064 840 935
- ^ 存档副本 (PDF). [2018-04-26]. （原始内容存档 (PDF)于2017-10-26）.
- ^ Allis 1994
- ^ AGA – top ten reason to play Go
- ^ Tromp 1999
参考文献 编辑
- AGA. Top Ten Reasons to Play Go. [2018-04-26]. （原始内容存档于2012-05-30）.
- Allis, Victor. Searching for Solutions in Games and Artificial Intelligence (PDF). Ph.D. Thesis, University of Limburg, Maastricht, The Netherlands. 1994 [2018-04-26]. ISBN 90-900748-8-0. （原始内容 (PDF)存档于2018-08-20）.
- Hearn, Robert A. Games, Puzzles, and Computation (PDF). 2006 [2018-04-26]. （原始内容存档 (PDF)于2008-05-28）. [Ph.D. Thesis, MIT.]
- Johnson, George. To Test a Powerful Computer, Play an Ancient Game. New York Times. 1997-07-29.
- Papadimitriou, Christos (1994), Computational Complexity, Addison Wesley.
- Tromp, John. Number of 2×2 games with positional superko. 1999 [2018-04-26]. （原始内容存档于2012-10-26）.
- Tromp, John. Number of legal Go positions (up to 19×19). 2005 [2018-04-26]. （原始内容存档于2016-02-06）.
- Tromp, John; Farnebäck, Gunnar. Combinatorics of Go. 2007 [2018-04-26]. （原始内容存档于2017-01-18）.
外部链接 编辑
- Go and Mathematics
- Number of possible outcomes of a game（页面存档备份，存于互联网档案馆） - article at Sensei's Library