查看“︁围棋与数学”︁的源代码

{{围棋}}
[[围棋]]是世界上最流行的游戏之一。由于其规则优美而简单，围棋一直是[[数学]]研究的灵感来源。11世纪的中国学者[[沈括]]在《[[梦溪笔谈]]》中估计，围棋所有可能的局面数量为 10<sup>172</sup> 左右。近年来，[[約翰·何頓·康威|約翰·H·康威]]在对围棋的研究中发明了[[超現實數]]，并促进了[[组合博弈论]]的发展（“围棋微数字”<ref>{{Cite web |url=http://senseis.xmp.net/?GoInfinitesimals |title=Go Infinitesimals |accessdate=2018-04-26 |archive-date=2017-11-07 |archive-url=https://web.archive.org/web/20171107111924/https://senseis.xmp.net/?GoInfinitesimals |dead-url=no }}</ref>就是它在围棋中使用的一个具体示例）。

==计算复杂性==

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

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

===没有打劫的情况===

没有打劫的话，围棋是[[PSPACE|PSPACE困难]]的。<ref name="sipser1980">{{cite journal|last1=Lichtenstein|first1=David|last2=Sipser|first2=Michael|title=Go Is Polynomial-Space Hard|journal=Journal of the ACM|date=April 1980|volume=27|issue=2|pages=393–401|url=http://webdocs.cs.ualberta.ca/~games/go/seminar/2003/030331/p393-lichtenstein.pdf|doi=10.1145/322186.322201|access-date=2018-04-26|archive-date=2017-08-08|archive-url=https://web.archive.org/web/20170808195425/http://webdocs.cs.ualberta.ca/~games/go/seminar/2003/030331/p393-lichtenstein.pdf|dead-url=no}}</ref> 这是通过把PSPACE完全的TQBF（真量化布尔公式）简化到{{le|广义地理|generalized geography}}，到平面广义地理，到最高3阶的广义地理，最后简化到围棋棋盘位置。

有打劫的围棋则不在PSPACE中。尽管实际的棋局似乎从没超出过 <math>n^2</math> 手，但一般而言，没有人知道围棋棋局的手数是否有一个多项式上限。如果有的话，围棋就会是PSPACE完全的。就目前而言，围棋可能是PSPACE完全，EXPTIME完全，甚至EXPSPACE完全的。

===日本打劫规则===

日本规则只规定了基本的劫，即一手棋下了之后，如果会恢复这手棋下之前的那个棋盘状态，那么这手棋是不允许下的。如果重复多手之前的棋盘状态是允许的，这也就意味着一局棋可以永久循环，如三劫循环，即同时有三个劫，经过12手就可以循环。

在日本打劫规则下，围棋是[[EXPTIME]]完全的。<ref name="robson1983">{{cite journal|last1=Robson|first1=John|title=The complexity of Go|journal=Proceedings of the IFIP 9th World Computer Congress on Information Processing|date=1983|pages=413–417}}</ref>

===禁止全局同形规则===

禁止全局同形规则是说重复出现任何先前棋盘状态都是不允许的。这是大多数中国和美国规则中使用的打劫规则。

在禁止全局同形规则下围棋的复杂性类为何，是一个未解决的问题。虽然日本打劫规则下围棋的复杂性为EXPTIME完全已被证明，但Robson的这个证明中，无论是上界还是下界的EXPTIME完全性的证明，都打破了禁止全局同形规则。<ref name="robson1983" />

至少现在已知，其复杂性至少是PSPACE困难，因为<ref name="sipser1980" />中对围棋的PSPACE困难性的证明是不依赖于打劫规则的，或者说即便是没有打劫规则，也是PSPACE困难的。现在还知道围棋的复杂性是在EXPSPACE内的。<ref name="robson1984">{{cite journal|last1=Robson|first1=J|title=Combinatorial games with exponential space complete decision problems|journal=Proceedings of the Mathematical Foundations of Computer Science|date=1984|pages=498–506|doi=10.1007/BFb0030333}}</ref>

Robson<ref name="robson1984" />证明了如果在EXPTIME完全的双人游戏的基础上，加上“禁止全局同形”的规则，游戏复杂性将会变为EXPSPACE完全。直观地说，这是因为对加入新规则的游戏来说，即便是确定一个局面下符合规则的下法，都需要指数级别的空间，因为从开局下到某一局面的长度是有可能达到指数级别的。

因此，广义[[國際象棋]]和[[西洋跳棋]]的禁止全局同形版本都是EXPSPACE完全的，因为广义国际象棋<ref name="Fraenkel1981">{{cite journal| author = [[Aviezri Fraenkel]] and D. Lichtenstein| title = Computing a perfect strategy for n&times;n chess requires time exponential in n| journal = J. Comb. Th. A| issue = 31| year = 1981| pages = 199–214|doi=10.1016/0097-3165(81)90016-9}}</ref>和西洋跳棋<ref name="robson1984checkers">{{cite journal| author = J. M. Robson| title = N by N checkers is Exptime complete| journal = SIAM Journal on Computing| volume = 13| issue = 2| pages = 252–267| year = 1984| doi = 10.1137/0213018}}</ref>都是EXPTIME完全的。不过这个结果不适用于围棋。

===围棋特定情形的复杂性===

当棋盘被活子把棋盘分割成若干孤立的区域的时候，围棋就进入了官子阶段，这时每个局部区域都会有一个多项式级别的规范博弈树。用[[组合博弈论]]的话来说，当围棋分解成具有多项式级别规范博弈树的子博弈之和时，就会进入官子。

在这个定义下，围棋的收官是PSPACE困难的。<ref>{{cite journal|last1=Wolfe|first1=David|editor1-last=Nowakowski|editor1-first=Richard J.|title=Go endgames are PSPACE-hard|journal=More Games of No Chance, Mathematical Sciences Research Institute Publications 42|date=2002|pages=125–136|url=http://library.msri.org/books/Book42/files/wolfe.pdf|publisher=Cambridge University Press|access-date=2018-04-26|archive-date=2017-08-10|archive-url=https://web.archive.org/web/20170810022942/http://library.msri.org/books/Book42/files/wolfe.pdf|dead-url=no}}</ref>

这可以通过将PSPACE完全的QBF（[[w:True quantified Boolean formula|Quantified Boolean Formula]]）问题转换成小型（多项式级别规范博弈树）围棋子游戏的总和来证明。请注意，论文并未证明围棋是在PSPACE中的，所以就有不是PSPACE完全的可能性。

确定哪一方[[征子]]有利是PSPACE完全的，无论是日本打劫规则还是禁止全局同形规则。<ref>{{cite journal|last1=Crâşmaru|first1=Marcel|last2=Tromp|first2=John|author-link2=John Tromp|title=Ladders are PSPACE-Complete|journal=Computers and Games, volume 2063 of Lecture Notes in Computer Science|date=2000|doi=10.1007/3-540-45579-5_16|publisher=Springer}}</ref> 这一点（PSPACE完全）可以通过模仿QBF证明。

==合法局面==
由于棋盘上每个位置都可以为空、白棋、黑棋三种情况，所以对于边长为 n 的棋盘总共有 3<sup>n<sup>2</sup></sup> 种可能的局面；但只有一部分是合法的。[[John Tromp|Tromp]]和Farnebäck推导了长 m 宽 n 的矩形棋盘的合法局面 <math>L(m,n)</math> 的递归公式。<ref name="Tromp and Farnebäck 2007">{{citation | last1= Tromp | first1 = J |author-link1=John Tromp| last2 = Farnebäck | first2 = G |year = 2007 | title =Combinatorics of Go | publisher = Springer, Berlin, Heidelberg | isbn = 978-3-540-75537-1 |doi=10.1007/978-3-540-75538-8_8 }}</ref> 在2016年算出了 <math>L(19,19)</math> 的准确数字<ref>https://tromp.github.io/go/legal.html {{Wayback|url=https://tromp.github.io/go/legal.html |date=20160206212717 }} 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</ref>。他们还发现了一个渐进公式 <math>L\approx AB^{m+n}C^{mn}</math>，其中 <math>A\approx 0.8506399258457145</math>，<math>B\approx 0.96553505933837387</math>，<math>C\approx 2.975734192043357249381</math>。据估计，可观测宇宙包含大约 10<sup>80</sup> 个原子，远小于常规围棋棋盘（m=n=19）上所有可能的合法局面的数目。随着棋盘变大，合法局面的比例也会降低。

{| class="wikitable"
!盘面大小 n&times;n
!3<sup>n<sup>2</sup></sup>
!合法的比例
!<math>L</math>（合法局面）（{{OEIS link|A094777}}）<ref>{{Cite web |url=https://tromp.github.io/go/gostate.pdf |title=存档副本 |accessdate=2018-04-26 |archive-date=2017-10-26 |archive-url=https://web.archive.org/web/20171026013857/http://tromp.github.io/go/gostate.pdf |dead-url=no }}</ref>
|-
!1&times;1
|align="right"|3
|align="right"|33.33%
|align="right"|1
|-
!2&times;2
|align="right"|81
|align="right"|70.37%
|align="right"|57
|-
!3&times;3
|align="right"|19,683
|align="right"|64.40%
|align="right"|12,675
|-
!4&times;4
|align="right"|43,046,721
|align="right"|56.49%
|align="right"|24,318,165
|-
!5&times;5
|align="right"|847,288,609,443
|align="right"|48.90%
|align="right"|414,295,148,741
|-
!9&times;9
|align="right"|4.43426488243&times;10<sup>38</sup>
|align="right"|23.44%
|align="right"|1.03919148791&times;10<sup>38</sup>
|-
!13&times;13
|align="right"|4.30023359390&times;10<sup>80</sup>
|align="right"|8.66%
|align="right"|3.72497923077&times;10<sup>79</sup>
|-
!19&times;19
|align="right"|1.74089650659&times;10<sup>172</sup>
|align="right"|1.20%
|align="right"|2.08168199382&times;10<sup>170</sup>
|}

==博弈树复杂性==

[[電腦科學家]][[Victor Allis]]指出，职业棋士之间对弈一般在150手左右，平均每手约250种选择，这就意味着[[游戏复杂度|博弈树复杂性]]为 10<sup>360</sup>。<ref>Allis 1994</ref> 对于''理论上可能''的棋局数量，包括在实际中不可能下出的棋局，Tromp和Farnebäck分别给出 10<sup>480</sup> 的下限和 10<sup>1710</sup> 的上限。<ref name="Tromp and Farnebäck 2007"/>
人们听到最多的所有可能的棋局数量为 10<sup>700</sup>，<ref name="top ten">AGA – top ten reason to play Go</ref> 这个数字是361手棋的简单排列（361! = 10<sup>768</sup>）得出的。另一个常见的推导是假设每一手棋都有 n 个选择，总共 L 手棋，那么棋局总量就是 N<sup>L</sup>。就比如在某些职业对局中能够见到的一局棋400手，按照这种方法算出来就是 361<sup>400</sup>（10<sup>1023</sup>）种可能的棋局。

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

{| class="wikitable"
!棋盘大小
!交叉点数N
!N!
!平均对局手数L
!N<sup>L</sup>
!最长对局手数
!棋局数量下限
!棋局数量上限
|-
!2&times;2
|align="right"|4
|align="right"|24
|align="right"|3
|align="right"|64
|align="right"|
|align="right"|386,356,909,593<ref>Tromp 1999</ref>
|align="right"|386,356,909,593
|-
!3&times;3
|align="right"|9
|align="right"|3.6&times;10<sup>5</sup>
|align="right"|5
|align="right"|5.9&times;10<sup>4</sup>
|align="right"|
|align="right"|
|
|-
!4&times;4
|align="right"|16
|align="right"|2.1&times;10<sup>13</sup>
|align="right"|9
|align="right"|6.9&times;10<sup>10</sup>
|align="right"|
|align="right"|
|
|-
!5&times;5
|align="right"|25
|align="right"|1.6&times;10<sup>25</sup>
|align="right"|15
|align="right"|9.3&times;10<sup>20</sup>
|align="right"|
|align="right"|
|
|-
!9&times;9
|align="right"|81
|align="right"|5.8&times;10<sup>120</sup>
|align="right"|45
|align="right"|7.6&times;10<sup>85</sup>
|align="right"|
|align="right"|
|
|-
!13&times;13
|align="right"|169
|align="right"|4.3&times;10<sup>304</sup>
|align="right"|90
|align="right"|3.2&times;10<sup>200</sup>
|align="right"|
|align="right"|
|
|-
!19&times;19
|align="right"|361
|align="right"|1.0&times;10<sup>768</sup>
|align="right"|200
|align="right"|3&times;10<sup>511</sup>
|align="right"|10<sup>48</sup>
|align="right"|10<sup>10<sup>48</sup></sup>
|align="right"|10<sup>10<sup>171</sup></sup>
|-
!21&times;21
|align="right"|441
|align="right"|2.5&times;10<sup>976</sup>
|align="right"|250
|align="right"|1.3&times;10<sup>661</sup>
|align="right"|
|align="right"|
|
|}

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

{| class="wikitable"
!align="left"|最长棋局 L (19&times;19)
!align="left"|(N)<sub>L</sub>
!align="left"|棋局数量的下界
!align="left"|棋局数量的上界
!align="left"|注释
|-
!1
|align="right"|361
|align="right"|361
|align="right"|361
|白棋第一手就认输了，就会有361种棋局，如果忽略掉所有对称性就是55种。
|-
!2
|align="right"|722
|align="right"|
|align="right"|721
|黑棋在白棋第一手后就认输了，就会有721种棋局，忽略掉所有对称性就是189种。
|-
!50
|align="right"|2.1&times;10<sup>126</sup>
|align="right"|
|align="right"|7.5&times;10<sup>127</sup>
|
|-
!100
|align="right"|1.4&times;10<sup>249</sup>
|align="right"|
|align="right"|5.6&times;10<sup>255</sup>
|
|-
!150
|align="right"|6.4&times;10<sup>367</sup>
|align="right"|
|align="right"|4.2&times;10<sup>383</sup>
|
|-
!200
|align="right"|1.9&times;10<sup>481</sup>
|align="right"|
|align="right"|3.2&times;10<sup>511</sup>
|
|-
!250
|align="right"|8.2&times;10<sup>587</sup>
|align="right"|
|align="right"|2.4&times;10<sup>639</sup>
|
|-
!300
|align="right"|2.8&times;10<sup>684</sup>
|align="right"|
|align="right"|7.8&times;10<sup>766</sup>
|
|-
!350
|align="right"|3.6&times;10<sup>760</sup>
|align="right"|
|align="right"|1.3&times;10<sup>895</sup>
|
|-
!361
|align="right"|1.4&times;10<sup>768</sup>
|align="right"|
|align="right"|1.8&times;10<sup>923</sup>
|使用181个黑子和180个白子的最长棋局
|-
!400
|align="right"|n/a
|align="right"|
|align="right"|1.0&times;10<sup>1023</sup>
|最长职业对局
|-
!500
|align="right"|n/a
|align="right"|
|align="right"|5.7&times;10<sup>1278</sup>
|
|-
!1000
|align="right"|n/a
|align="right"|
|align="right"|3.2&times;10<sup>2557</sup>
|
|-
!4700万
|align="right"|n/a
|align="right"|
|align="right"|10<sup>10<sup>8</sup></sup>
|361<sup>3</sup> 手棋
|-
!10<sup>48</sup>
|align="right"|n/a
|align="right"|10<sup>10<sup>48</sup></sup>
|align="right"|10<sup>10<sup>171</sup></sup>
|最长棋局
|}

10<sup>700</sup> 这个数字对于200手以内的所有棋局来说是一种高估，但对361手以内的所有棋局来说是一种低估。而4700万手的棋，在一秒一手、每天下16个小时的情况下，也要下2¼年（一年有3100万秒）。

==参见==
* [[游戏复杂度]]
* {{le|香农数|Shannon number}}（国际象棋）

==注释==
{{Reflist|2}}

==参考文献 ==
* {{cite web | title = Top Ten Reasons to Play Go | author = AGA | url = http://www.usgo.org/resources/topten.html | accessdate = 2018-04-26 | archive-date = 2012-05-30 | archive-url = https://web.archive.org/web/20120530063909/http://www.usgo.org/resources/topten.html | dead-url = no }}
* {{cite book | author = Allis, Victor | year = 1994 | title = Searching for Solutions in Games and Artificial Intelligence | publisher = Ph.D. Thesis, University of Limburg, Maastricht, The Netherlands | isbn = 90-900748-8-0 | url = http://fragrieu.free.fr/SearchingForSolutions.pdf | format = PDF | access-date = 2018-04-26 | archive-date = 2018-08-20 | archive-url = https://web.archive.org/web/20180820005345/http://fragrieu.free.fr/SearchingForSolutions.pdf | dead-url = yes }}
* {{cite web | url = http://www.swiss.ai.mit.edu/~bob/hearn-thesis-final.pdf | format = PDF | title = Games, Puzzles, and Computation | author = Hearn, Robert A. | year = 2006 | accessdate = 2018-04-26 | archive-date = 2008-05-28 | archive-url = https://web.archive.org/web/20080528195209/http://www.swiss.ai.mit.edu/~bob/hearn-thesis-final.pdf | dead-url = no }} [Ph.D. Thesis, MIT.]
* {{cite web | url=https://query.nytimes.com/gst/fullpage.html?res=9C04EFD6123AF93AA15754C0A961958260 | title=To Test a Powerful Computer, Play an Ancient Game | last=Johnson |
first=George | work=[[纽约时报|New York Times]]| date=1997-07-29}}
*[[赫里斯托斯·帕帕季米特里乌|Papadimitriou, Christos]] (1994), ''Computational Complexity'', Addison Wesley.
* {{cite web | url = https://groups.google.com/group/rec.games.go/browse_thread/thread/161ff6e5922e1124/c90e5b4a61ea0602?lnk=st | last = Tromp | first = John | author-link = John Tromp | year = 1999 | title = Number of 2&times;2 games with positional superko | accessdate = 2018-04-26 | archive-date = 2012-10-26 | archive-url = https://web.archive.org/web/20121026141210/http://groups.google.com/group/rec.games.go/browse_thread/thread/161ff6e5922e1124/c90e5b4a61ea0602?lnk=st | dead-url = no }}
* {{cite web | url = https://tromp.github.io/go/legal.html | title = Number of legal Go positions (up to 19&times;19) | last = Tromp | first = John | author-link = John Tromp | year = 2005 | accessdate = 2018-04-26 | archive-date = 2016-02-06 | archive-url = https://web.archive.org/web/20160206212717/http://tromp.github.io/go/legal.html | dead-url = no }}
* {{cite web | title = Combinatorics of Go | author1 = [[John Tromp|Tromp, John]] | author2 = Farnebäck, Gunnar | year = 2007 | url = https://tromp.github.io/go/gostate.ps | accessdate = 2018-04-26 | archive-date = 2017-01-18 | archive-url = https://web.archive.org/web/20170118125253/http://tromp.github.io/go/gostate.ps | dead-url = no }}

==外部链接==
* [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]{{Wayback|url=http://senseis.xmp.net/?NumberOfPossibleOutcomesOfAGame |date=20181215173659 }} - article at Sensei's Library

[[Category:围棋]]
[[Category:组合博弈论]]
[[Category:趣味數學]]