Go and mathematics
Part of a series of articles on 
Go 

Game specifics 

History and culture 
Players and organizations 
Computers and mathematics 
The game of 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. Chinese scholars of the 11th century already published work on permutations based on the go board.^{[citation needed]} In more recent years, research of the game by John H. Conway led to the invention of the surreal numbers and contributed to development of combinatorial game theory (with Go Infinitesimals^{[1]} being a specific example of its use in Go).
Contents
Computational complexity
Generalized Go is played on n x n boards, and the computational complexity of determining the winner in a given position of generalized Go depends crucially on the ko rules.
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 PSPACEhard.^{[2]} This is proved by reducing True Quantified Boolean Formula, which is known to be PSPACEcomplete, to generalized geography, to planar generalized geography, to planar generalized geography with maximum degree 3, finally to Go positions.
Go with ko is not known to be in PSPACE. Though actual games seem never to last longer than moves, in general it's not known if there were a polynomial bound on the length of Go games. If there were, Go would be PSPACEcomplete. As it currently stands, it might be PSPACEcomplete, EXPTIMEcomplete, or even EXPSPACEcomplete.
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). For example, the triple ko, where there are three kos at the same time, allowing a cycle of 12 moves.
With Japanese ko rules, Go is EXPTIMEcomplete.^{[3]}
Superko rule
The superko rule (also called positional superko rule) states that a repetition of any board position that has previously occurred is forbidden. It's 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 EXPTIMEcomplete, both the lower and the upper bounds of Robson’s EXPTIMEcompleteness proof^{[3]} break when the superko rule is added.
It is known that it is at least PSPACEhard, since the proof in ^{[2]} of the PSPACEhardness of Go does not rely on the ko rule, or lack of the ko rule. It is also known that Go is in EXPSPACE.^{[4]}
Robson ^{[4]} showed that if the superko rule, that is, “no previous position may ever be recreated”, is added to certain twoplayer games that are EXPTIMEcomplete, then the new games would be EXPSPACEcomplete. Intuitively, it's because it requires an exponential amount of space 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 EXPSPACEcomplete, since generalized chess^{[5]} and checkers^{[6]} are EXPTIMEcomplete. However, this result does not apply to Go.^{[4]}
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 PSPACEhard.^{[7]}
This is proven by converting the Quantified Boolean Formula problem, which is PSPACEcomplete, 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 PSPACEcomplete.
Determining which side wins a ladder capturing race is PSPACEcomplete, whether Japanese ko rule or superko rule is in place.^{[8]} This is proven by simulating QBF, known to be PSPACEcomplete, 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^{N} possible board positions on a board with N intersections. Tromp and Farnebäck showed that on a 19×19 board, about 1.2% of board positions are legal (no stones without liberties exist on the board), which makes for 3^{361}×0.01196... = 2.08168199382... ×10^{170} legal positions "of which we can expect all digits to be correct" (i.e. because the convergence is so fast).^{[9]} It has been estimated that the observable universe contains around 10^{80} atoms, far fewer than the number of possible legal positions. As the board gets larger, the percentage of the positions that are legal decreases.
Game size  Board size N  3^{N}  Percent legal  Maximum legal game positions (A094777)^{[10]} 

1×1  1  3  33%  1 
2×2  4  81  70%  57 
3×3  9  19,683  64%  12,675 
4×4  16  43,046,721  56%  24,318,165 
5×5  25  8.47×10^{11}  49%  4.1×10^{11} 
9×9  81  4.4×10^{38}  23.4%  1.039×10^{38} 
13×13  169  4.3×10^{80}  8.66%  3.72497923×10^{79} 
19×19  361  1.74×10^{172}  1.196%  2.08168199382×10^{170} 
21×21  441  2.57×10^{210} 
The exact number of legal 19x19 positions was computed by Tromp and others in early 2016 as 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.^{[11]}
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 gametree complexity of 10^{360}.^{[12]} 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^{1048} and 10^{10171} respectively.^{[9]} The most commonly quoted number for the number of possible games, 10^{700}^{[13]} is derived from a simple permutation of 361 moves or 361! = 10^{768}. Another common derivation is to assume N intersections and L longest game for N^L total games. For example, 400 moves, as seen in some professional games, would be one out of 361^{400} or 1 × 10^{1023} 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.
Game size  Board size N (intersections)  N!  Average game length L  N^{L}  Maximum game length (# of moves)  Lower Limit of games  Upper Limit of games 

2×2  4  24  3  64  386,356,909,593^{[14]}  
3×3  9  3.6×10^{5}  5  5.9×10^{4}  
4×4  16  2.1×10^{13}  9  6.9×10^{10}  
5×5  25  1.6×10^{25}  15  9.3×10^{20}  
9×9  81  5.8×10^{120}  45  7.6×10^{85}  
13×13  169  4.3×10^{304}  90  3.2×10^{200}  
19×19  361  1.0×10^{768}  200  3×10^{511}  10^{48}  10^{1048}  10^{10171} 
21×21  441  2.5×10^{976}  250  1.3×10^{661} 
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)_{L}, fails to include illegal captures and positions. Taking N as the board size (19×19=361) and L as the longest game, N^{L} forms an upper limit. A more accurate limit is presented in the Tromp/Farnebäck paper.
Longest game L (19×19)  (N)_{L}  Lower Limit of games  Upper Limit of games  Notes 

1  361  361  361  White resigns after first move, 361 ignoring all symmetry including y=x else (Distances from corner)10x1010=90 90/2=45 +10 (adding back x=y points of symmetry) = 55. 
2  722  721  Black resigns after white's first move, 721 ignoring all symmetry including y=x else 19x1919=342 342/2=171 +19 = 190  1= 189.  
50  2.1×10^{126}  7.5×10^{127}  
100  1.4×10^{249}  5.6×10^{255}  
150  6.4×10^{367}  4.2×10^{383}  
200  1.9×10^{481}  3.2×10^{511}  
250  8.2×10^{587}  2.4×10^{639}  
300  2.8×10^{684}  7.8×10^{766}  
350  3.6×10^{760}  1.3×10^{895}  
361  1.4×10^{768}  1.8×10^{923}  Longest game using 181 black and 180 white stones  
400  n/a  1.0×10^{1023}  Longest professional games  
500  n/a  5.7×10^{1278}  
1000  n/a  3.2×10^{2557}  
47 million  n/a  10^{108}  361^3 moves  
10^{48}  n/a  10^{1048}  10^{10171}  Longest game 
From this table, we can see that 10^{700} is 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. It can also be noted that since there are about 31 million seconds in a year, it would take about 2¼ years, playing 16 hours a day at one move per second, to play 47 million moves.
See also
 Game complexity
 Shannon number (Chess)
Notes
 ^ Go Infinitesimals
 ^ ^{a} ^{b} Lichtenstein, David; Sipser, Michael (April 1980). "Go Is PolynomialSpace Hard" (PDF). Journal of the ACM. 27 (2): 393–401. doi:10.1145/322186.322201.
 ^ ^{a} ^{b} Robson, John (1983). "The complexity of Go". Proceedings of the IFIP 9th World Computer Congress on Information Processing: 413–417.
 ^ ^{a} ^{b} ^{c} Robson, J (1984). "Combinatorial games with exponential space complete decision problems". Proceedings of the Mathematical Foundations of Computer Science: 498–506. doi:10.1007/BFb0030333.
 ^ Aviezri Fraenkel and D. Lichtenstein (1981). "Computing a perfect strategy for n×n chess requires time exponential in n". J. Comb. Th. A (31): 199–214. doi:10.1016/00973165(81)900169.
 ^ J. M. Robson (1984). "N by N checkers is Exptime complete". SIAM Journal on Computing. 13 (2): 252–267. doi:10.1137/0213018.
 ^ Wolfe, David (2002). Nowakowski, Richard J., ed. "Go endgames are PSPACEhard" (PDF). More Games of No Chance, Mathematical Sciences Research Institute Publications 42. Cambridge University Press: 125–136.
 ^ Crâşmaru, Marcel; Tromp, John (2000). "Ladders are PSPACEComplete". Computers and Games, volume 2063 of Lecture Notes in Computer Science. Springer. doi:10.1007/3540455795_16.
 ^ ^{a} ^{b} "Combinatorics of Go", J Tromp, G Farnebäck  Computers and Games, 2007
 ^ Tromp 2005
 ^ http://tromp.github.io/go/legal.html
 ^ Allis 1994
 ^ AGA – top ten reason to play Go
 ^ Tromp 1999
References
 AGA. "Top Ten Reasons to Play Go".
 Allis, Victor (1994). Searching for Solutions in Games and Artificial Intelligence (PDF). Ph.D. Thesis, University of Limburg, Maastricht, The Netherlands. ISBN 9090074880.
 Hearn, Robert A. (2006). "Games, Puzzles, and Computation" (PDF). [Ph.D. Thesis, MIT.]
 Johnson, George (19970729). "To Test a Powerful Computer, Play an Ancient Game". New York Times.
 Papadimitriou, Christos (1994), Computational Complexity, Addison Wesley.
 Tromp, John (1999). "Number of 2×2 games with positional superko".
 Tromp, John (2005). "Number of legal Go positions (up to 19×19)".
 Tromp, John; Farnebäck, Gunnar (2007). "Combinatorics of Go".
External links
 Go and Mathematics
 Number of possible outcomes of a game  article at Sensei's Library