View source for Go and mathematics

{{Short description|Calculations of the game complexity of go}}
{{GoBoardGame}}
The game of [[Go (board game)|Go]] is one of the most popular games in the world. As a result of its elegant and simple rules, the game has long been an inspiration for [[mathematical]] research. [[Shen Kuo]], an 11th century Chinese scholar, estimated in his ''[[Dream Pool Essays]]'' that the number of possible board positions is around 10<sup>172</sup>. In more recent years, research of the game by [[John Horton Conway|John H. Conway]] led to the development of the [[surreal number]]s and contributed to development of [[combinatorial game theory]] (with Go Infinitesimals<ref>{{Cite web|title=Go Infinitesimals at Sensei's Library|url=https://senseis.xmp.net/?GoInfinitesimals|access-date=2022-02-10|website=senseis.xmp.net}}</ref> being a specific example of its use in Go).

==Computational complexity==

Generalized Go is played on ''n'' × ''n'' boards, and the [[Complexity class|computational complexity]] of determining the winner in a given position of generalized Go depends crucially on the [[ko rule]]s.

Go is “almost” in [[PSPACE]], since in normal play, moves are not reversible, and it is only through capture that there is the possibility of the repeating patterns necessary for a harder complexity.

===Without ko===

Without ko, Go is [[PSPACE-hard]].<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|s2cid=29498352}}</ref> This is proved by reducing [[True Quantified Boolean Formula#PSPACE-completeness|True Quantified Boolean Formula]], which is known to be PSPACE-complete, to [[generalized geography]], to planar generalized geography, to [[Generalized geography#Planar bipartite graph with maximum degree 3|planar generalized geography with maximum degree 3]], finally to Go positions.

Go with superko is not known to be in PSPACE. Though actual games seem never to last longer than <math>n^2</math> moves, in general it is not known if there were a polynomial bound on the length of Go games. If there were, Go would be PSPACE-complete. As it currently stands, it might be PSPACE-complete, EXPTIME-complete, or even EXPSPACE-complete.

===Japanese ko rule===

Japanese ko rules state that only the basic ko, that is, a move that reverts the board to the situation one move previously, is forbidden. Longer repetitive situations are allowed, thus potentially allowing a game to loop forever, such as the triple ko, where there are three kos at the same time, allowing a cycle of 12 moves.

With Japanese ko rules, Go is [[EXPTIME]]-complete.<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>

===Superko rule===

The [[superko rule]] (also called the positional superko rule) states that a repetition of any board position that has previously occurred is forbidden. This is the ko rule used in most Chinese and US rulesets.

It is an open problem what the complexity class of Go is under superko rule. Though Go with Japanese ko rule is EXPTIME-complete, both the lower and the upper bounds of Robson’s EXPTIME-completeness proof<ref name="robson1983" /> break when the superko rule is added.

It is known that it is at least PSPACE-hard, since the proof in<ref name="sipser1980" /> of the PSPACE-hardness of Go does not rely on the ko rule, or lack of the ko rule. It is also known that Go is in EXPSPACE.<ref name="robson1984">{{cite book|last1=Robson|first1=J|title=Mathematical Foundations of Computer Science 1984|chapter=Combinatorial games with exponential space complete decision problems|journal=Proceedings of the Mathematical Foundations of Computer Science|volume=176|date=1984|pages=498–506|doi=10.1007/BFb0030333|series=Lecture Notes in Computer Science|isbn=978-3-540-13372-8}}</ref>

Robson<ref name="robson1984" /> showed that if the superko rule, that is, “no previous position may ever be recreated”, is added to certain two-player games that are EXPTIME-complete, then the new games would be EXPSPACE-complete. Intuitively, this is because an exponential amount of space is required even to determine the legal moves from a position, because the game history leading up to a position could be exponentially long.

As a result, superko variants (moves that repeat a previous board position are not allowed) of generalized [[chess]] and [[checkers]] are EXPSPACE-complete, since generalized chess<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. Theory A| volume = 31| issue = 2| year = 1981| pages = 199–214|doi=10.1016/0097-3165(81)90016-9| doi-access = free}}</ref> and checkers<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> are EXPTIME-complete. However, this result does not apply to Go.<ref name="robson1984" />

===Complexity of certain Go configurations===

A Go endgame begins when the board is divided into areas that are isolated from all other local areas by living stones, such that each local area has a polynomial size canonical game tree. In the language of [[combinatorial game theory]], it happens when a Go game decomposes into a sum of subgames with polynomial size canonical game trees.

With that definition, Go endgames are PSPACE-hard.<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|access-date=2016-07-09|archive-date=2017-08-10|archive-url=https://web.archive.org/web/20170810022942/http://library.msri.org/books/Book42/files/wolfe.pdf|url-status=dead}}</ref>

This is proven by converting the [[True quantified Boolean formula|Quantified Boolean Formula]] problem, which is PSPACE-complete, into a sum of small (with polynomial size canonical game trees) Go subgames. Note that the paper does not prove that Go endgames are in PSPACE, so they might not be PSPACE-complete.

Determining which side wins a [http://senseis.xmp.net/?ladder ladder] capturing race is PSPACE-complete, whether Japanese ko rule or superko rule is in place.<ref>{{cite book|last1=Crâşmaru|first1=Marcel|last2=Tromp|first2=John|title=Computers and Games |chapter=Ladders Are PSPACE-Complete |author-link2=John Tromp|volume=2063|pages=241–249|date=2000|doi=10.1007/3-540-45579-5_16|publisher=Springer|series=Lecture Notes in Computer Science|isbn=978-3-540-43080-3|citeseerx=10.1.1.24.4665}}</ref> This is proven by simulating QBF, known to be PSPACE-complete, with ladders that bounce around the board like light beams.

==Legal positions==
Since each location on the board can be either empty, black, or white, there are a total of 3<sup>''n''<sup>2</sup></sup> possible board positions on a square board with length ''n''; however not all of them are legal. [[John Tromp|Tromp]] and Farnebäck derived a recursive formula for legal positions <math>L(m,n)</math> of a rectangle board with length ''m'' and ''n''.<ref name="Tromp and Farnebäck 2007">{{citation | last1= Tromp | first1 = J |author-link1=John Tromp| last2 = Farnebäck | first2 = G | title = Computers and Games | chapter = Combinatorics of Go | series = Lecture Notes in Computer Science | volume = 4630 | pages = 84–99 |year = 2007 | publisher = Springer, Berlin, Heidelberg | isbn = 978-3-540-75537-1 | doi=10.1007/978-3-540-75538-8_8 }}</ref> The exact number of <math>L(19,19)</math> was obtained in 2016.<ref>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</ref> They also find an asymptotic formula <math>L\approx AB^{m+n}C^{mn}</math>, where <math>A\approx 0.8506399258457145</math>, <math>B\approx 0.96553505933837387</math> and <math>C\approx 2.975734192043357249381</math>. It has been estimated that the observable universe contains around 10<sup>80</sup> atoms, far fewer than the number of possible legal positions of regular board size (m=n=19). As the board gets larger, the percentage of the positions that are legal decreases.

{| class="wikitable"
!Board size n&times;n
!3<sup>''n''<sup>2</sup></sup>
!Percent legal
!<math>L</math> (legal positions) ({{OEIS link|A094777}})<ref>{{cite web|url=https://tromp.github.io/go/gostate.pdf|title=Combinatorics of Go
|website=github.io|access-date=17 June 2023}}</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>
|}

==Game tree complexity==

The [[computer scientist]] [[Victor Allis]] notes that typical games between experts last about 150 moves, with an average of about 250 choices per move, suggesting a [[game-tree complexity]] of 10<sup>360</sup>.<ref>Allis 1994</ref> For the number of ''theoretically possible'' games, including games impossible to play in practice, Tromp and Farnebäck give lower and upper bounds of 10<sup>10<sup>48</sup></sup> and 10<sup>10<sup>171</sup></sup> respectively.<ref name="Tromp and Farnebäck 2007"/>
The lower bound was improved to a [[googolplex]] by Walraet and Tromp.<ref>{{citation | last1= Walraet | first1 = M | last2 = Tromp | first2 = J | title = Computers and Games | chapter = A Googolplex of Go Games | series = Lecture Notes in Computer Science | volume = 10068 | pages = 191–201 | author-link2 = John Tromp|year = 2016 | publisher = Springer, Berlin, Heidelberg | isbn = 978-3-319-50934-1 | doi=10.1007/978-3-319-50935-8_18 }}</ref>
The most commonly quoted number for the number of possible games, 10<sup>700</sup><ref name="top ten">{{Cite web|url=https://www.usgo.org/|title=Home - American Go Association|website=www.usgo.org|accessdate=17 June 2023}}</ref> is derived from a simple permutation of 361 moves or {{nowrap|1=361! = 10<sup>768</sup>}}.  Another common derivation is to assume ''N'' intersections and ''L'' longest game for ''N''{{i sup|''L''}} total games.  For example, 400 moves, as seen in some professional games, would be one out of 361<sup>400</sup> or 1 &times; 10<sup>1023</sup> possible games.

The total number of possible games is a function both of the size of the board and the number of moves played.  While most games last less than 400 or even 200 moves, many more are possible.

{| class="wikitable"
!Game size
!Board size ''N'' (intersections)
!''N''!
!Average game length ''L''
!''N''{{i sup|''L''}}
!Maximum game length (# of moves)
!Lower limit of games
!Upper limit of games
|-
!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"|{{val|3.6|e=5}}
|align="right"|5
|align="right"|{{val|5.9|e=4}}
|align="right"|
|align="right"|
|
|-
!4 &times; 4
|align="right"|16
|align="right"|{{val|2.1|e=13}}
|align="right"|9
|align="right"|{{val|6.9|e=10}}
|align="right"|
|align="right"|
|
|-
!5 &times; 5
|align="right"|25
|align="right"|{{val|1.6|e=25}}
|align="right"|15
|align="right"|{{val|9.3|e=20}}
|align="right"|
|align="right"|
|
|-
!9 &times; 9
|align="right"|81
|align="right"|{{val|5.8|e=120}}
|align="right"|45
|align="right"|{{val|7.6|e=85}}
|align="right"|
|align="right"|
|
|-
!13 &times; 13
|align="right"|169
|align="right"|{{val|4.3|e=304}}
|align="right"|90
|align="right"|{{val|3.2|e=200}}
|align="right"|
|align="right"|
|
|-
!19 &times; 19
|align="right"|361
|align="right"|{{val|1.4|e=768}}
|align="right"|200
|align="right"|{{val|3|e=511}}
|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"|{{val|2.5|e=976}}
|align="right"|250
|align="right"|{{val|1.3|e=661}}
|align="right"|
|align="right"|
|
|}

The total number of possible games can be estimated from the board size in a number of ways, some more rigorous than others.  The simplest, a permutation of the board size, (''N'')<sub>''L''</sub>, fails to include illegal captures and positions.  Taking ''N'' as the board size (19 &times; 19 = 361) and ''L'' as the longest game, ''N''{{i sup|''L''}} forms an upper limit.  A more accurate limit is presented in the Tromp/Farnebäck paper.

{| class="wikitable"
!align="left"|Longest game ''L'' (19 &times; 19)
!align="left"|(''N'')<sub>''L''</sub>
!align="left"|Lower limit of games
!align="left"|Upper limit of games
!align="left"|Notes
|-
!1
|align="right"|361
|align="right"|361
|align="right"|362
|White resigns after first move, 361(362 if include pass) ignoring all symmetry including ''y'' = ''x'' else (distances from corner) 10×10−10=90 90/2=45 +10 (adding back ''x'' = ''y'' points of symmetry) = 55.(56 if include pass)
|-
!2
|align="right"|129960
|align="right"|
|align="right"|130682
| 361(black)× 360(white) + 361(black pass) + 361(white pass)
|-
!50
|align="right"|{{val|2.1|e=126}}
|align="right"|
|align="right"|{{val|7.5|e=127}}
|
|-
!100
|align="right"|{{val|1.4|e=249}}
|align="right"|
|align="right"|{{val|5.6|e=255}}
|
|-
!150
|align="right"|{{val|6.4|e=367}}
|align="right"|
|align="right"|{{val|4.2|e=383}}
|
|-
!200
|align="right"|{{val|1.9|e=481}}
|align="right"|
|align="right"|{{val|3.2|e=511}}
|
|-
!211
|align="right"|{{val|2.5|e=505}}
|align="right"|
|align="right"|{{val|4.3|e=539}}
|average length of professional games
|-
!250
|align="right"|{{val|8.2|e=587}}
|align="right"|
|align="right"|{{val|2.4|e=639}}
|
|-
!300
|align="right"|{{val|2.8|e=684}}
|align="right"|
|align="right"|{{val|7.8|e=766}}
|
|-
!350
|align="right"|{{val|3.6|e=760}}
|align="right"|
|align="right"|{{val|1.3|e=895}}
|
|-
!361
|align="right"|{{val|1.4|e=768}}
|align="right"|
|align="right"|{{val|1.8|e=923}}
|Longest game using 181 black and 180 white stones
|-
!411
|align="right"|n/a
|align="right"|
|align="right"|{{val|1.3|e=1051}}
|Longest professional game<ref>{{Cite web|url=https://homepages.cwi.nl/~aeb/go/misc/gostat.html|title = Statistics on the length of a go game}}</ref>
|-
!500
|align="right"|n/a
|align="right"|
|align="right"|{{val|5.7|e=1278}}
|
|-
!1000
|align="right"|n/a
|align="right"|
|align="right"|{{val|3.2|e=2557}}
|
|-
!47045881
|align="right"|n/a
|align="right"|
|align="right"|10<sup>10<sup>8</sup></sup>
|361<sup>3</sup> moves
|-
!10<sup>48</sup>
|align="right"|n/a
|align="right"|10<sup>10<sup>100</sup></sup>
|align="right"|10<sup>10<sup>171</sup></sup>
|Longest game
|}

10<sup>700</sup> is thus an overestimate of the number of possible games that can be played in 200 moves and an underestimate of the number of games that can be played in 361 moves.  Since there are about 31 million seconds in a year, it would take about {{frac|2|1|4}} years, playing 16 hours a day at one move per second, to play 47 million moves.

==See also==
{{Portal|Go}}
* [[Game complexity]]
* [[God's algorithm]]
* [[Shannon number]] (Chess)

==Notes==
{{Reflist|2}}

==References ==
* {{cite web | title = Top Ten Reasons to Play Go | author = AGA | url = http://www.usgo.org/resources/topten.html }}
* {{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 = 978-90-900748-8-7 | url = http://fragrieu.free.fr/SearchingForSolutions.pdf}}
* {{cite web | url = http://www.swiss.ai.mit.edu/~bob/hearn-thesis-final.pdf | title = Games, Puzzles, and Computation | author = Hearn, Robert A.|author-link=Bob Hearn | year = 2006 }} [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}}
*[[Christos Papadimitriou|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 }}
* {{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 = 2016 }}
* {{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}}

==External links==
* [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

{{Go (game)}}

[[Category:Go (game)|Mathematics]]
[[Category:Combinatorial game theory]]