Go and mathematics
| Part of a series 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. 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).
Legal positions
Since each location on the board can be either empty, black, or white, there are a total of 3N 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 3361×0.01196... = 2.08168199382... ×10170 legal positions "of which we can expect all digits to be correct" (i.e. because the convergence is so fast).[2] It has been estimated that the observable universe contains around 1080 atoms, far fewer than the number of possible legal positions. As the board gets larger, the percentage of the positions that are legal decreases. Go (with Japanese ko rules) is a two player un-bounded EXPTIME-complete game.[3] Rule variations that place a polynomial bound on the length of the game produces a PSPACE-complete game.[4] The complexity of Go with superko rules remains an open question.
| Game size | Board size N | 3N | Percent legal | Maximum legal game positions (A094777)[5] |
|---|---|---|---|---|
| 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×1011 | 49% | 4.1×1011 |
| 9×9 | 81 | 4.4×1038 | 23.4% | 1.039×1038 |
| 13×13 | 169 | 4.3×1080 | 8.66% | 3.72497923×1079 |
| 19×19 | 361 | 1.74×10172 | 1.196% | 2.08168199382×10170 |
| 21×21 | 441 | 2.57×10210 |
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.[6]
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 10360.[7] For the number of theoretically possible games, including games impossible to play in practice, Tromp and Farnebäck give lower and upper bounds of 101048 and 1010171 respectively.[2] The most commonly quoted number for the number of possible games, 10700[8] is derived from a simple permutation of 361 moves or 361! = 10768. 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 361400 or 1 × 101023 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 | NL | Maximum game length (# of moves) | Lower Limit of games | Upper Limit of games |
|---|---|---|---|---|---|---|---|
| 2×2 | 4 | 24 | 3 | 64 | 386,356,909,593[9] | ||
| 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 |
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, NL 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)10x10-10=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 19x19-19=342 342/2=171 +19 = 190 - 1= 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 | Longest game using 181 black and 180 white stones | |
| 400 | n/a | 1.0×101023 | Longest professional games | |
| 500 | n/a | 5.7×101278 | ||
| 1000 | n/a | 3.2×102557 | ||
| 47 million | n/a | 10108 | 361^3 moves | |
| 1048 | n/a | 101048 | 1010171 | Longest game |
From this table, we can see that 10700 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. As to 1048, since the future age of the universe is projected to be less than 1000 trillion years[10] and no computer is projected to compute anything close to a trillion teraflops (one yottaflops), any number higher than 1039 is beyond possibility of being played.
See also
- Game complexity
- Shannon number (Chess)
Notes
- ^ Go Infinitesimals
- ^ a b "Combinatorics of Go", J Tromp, G Farnebäck - Computers and Games, 2007
- ^ Hearn 2006
- ^ Papadimitriou 1994
- ^ Tromp 2005
- ^ http://tromp.github.io/go/legal.html
- ^ Allis 1994
- ^ AGA – top ten reason to play Go
- ^ Tromp 1999
- ^ The Future of the Universe
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 90-900748-8-0.
- Hearn, Robert A. (2006). "Games, Puzzles, and Computation" (PDF). [Ph.D. Thesis, MIT.]
- Johnson, George (1997-07-29). "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 and Farnebäck, Gunnar (2007). "Combinatorics of Go".
{{cite web}}: CS1 maint: multiple names: authors list (link)
External links
- Combinatorics of Go online viewer
- Go and Mathematics
- Number of possible outcomes of a game - article at Sensei's Library