Go and mathematics

Last updated

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. Shen Kuo, an 11th century Chinese scholar, estimated in his Dream Pool Essays that the number of possible board positions is around 10172. In more recent years, research of the game by John H. Conway led to the development 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 × 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 PSPACE-hard. [2] This is proved by reducing True Quantified Boolean Formula, which is known to be PSPACE-complete, to generalized geography, to planar generalized geography, to 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 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. [3]

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 [3] break when the superko rule is added.

It is known that it is at least PSPACE-hard, since the proof in [2] 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. [4]

Robson [4] 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 [5] and checkers [6] are EXPTIME-complete. 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 PSPACE-hard. [7]

This is proven by converting the 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 ladder capturing race is PSPACE-complete, whether Japanese ko rule or superko rule is in place. [8] This is proven by simulating QBF, known to be PSPACE-complete, with ladders that bounce around the board like light beams.

Since each location on the board can be either empty, black, or white, there are a total of 3n2 possible board positions on a square board with length n; however not all of them are legal. Tromp and Farnebäck derived a recursive formula for legal positions of a rectangle board with length m and n. [9] The exact number of was obtained in 2016. [10] They also find an asymptotic formula , where , and . It has been estimated that the observable universe contains around 1080 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.

Board size n×n3n2Percent legal (legal positions) (A094777) [11]
1 × 1333.33%1
2 × 28170.37%57
3 × 319,68364.40%12,675
4 × 443,046,72156.49%24,318,165
5 × 5847,288,609,44348.90%414,295,148,741
9 × 94.43426488243 × 103823.44%1.03919148791 × 1038
13 × 134.30023359390 × 10808.66%3.72497923077 × 1079
19 × 191.74089650659 × 101721.20%2.08168199382 × 10170

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. [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 101048 and 1010171 respectively. [9] The lower bound was improved to a googolplex by Walraet and Tromp. [13] The most commonly quoted number for the number of possible games, 10700 [14] 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 NL 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 sizeBoard size N (intersections)N!Average game length LNLMaximum game length (# of moves)Lower limit of gamesUpper limit of games
2 × 2424364386,356,909,593 [15] 386,356,909,593
3 × 393.6×10555.9×104
4 × 4162.1×101396.9×1010
5 × 5251.6×1025159.3×1020
9 × 9815.8×10120457.6×1085
13 × 131694.3×10304903.2×10200
19 × 193611.4×107682003×1051110481010481010171
21 × 214412.5×109762501.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)LLower limit of gamesUpper limit of gamesNotes
1361361361White resigns after first move, 361 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.
2722721Black resigns after white's first move, 721 ignoring all symmetry including y=x else 19×19−19=342 342/2=171 +19 = 190 − 1 = 189.
502.1×101267.5×10127
1001.4×102495.6×10255
1506.4×103674.2×10383
2001.9×104813.2×10511
2508.2×105872.4×10639
3002.8×106847.8×10766
3503.6×107601.3×10895
3611.4×107681.8×10923Longest game using 181 black and 180 white stones
411n/a1.3×101051Longest professional game [16]
500n/a5.7×101278
1000n/a3.2×102557
47045881n/a101083613 moves
1048n/a10101001010171Longest game

10700 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 2+1⁄4 years, playing 16 hours a day at one move per second, to play 47 million moves.

See also

Notes

  1. ↑ "Go Infinitesimals at Sensei's Library". senseis.xmp.net. Retrieved 2022-02-10.
  2. 1 2 Lichtenstein, David; Sipser, Michael (April 1980). "Go Is Polynomial-Space Hard" (PDF). Journal of the ACM. 27 (2): 393–401. doi:10.1145/322186.322201. S2CID   29498352.
  3. 1 2 Robson, John (1983). "The complexity of Go". Proceedings of the IFIP 9th World Computer Congress on Information Processing: 413–417.
  4. 1 2 3 Robson, J (1984). "Combinatorial games with exponential space complete decision problems". Mathematical Foundations of Computer Science 1984. Lecture Notes in Computer Science. Vol. 176. pp. 498–506. doi:10.1007/BFb0030333. ISBN   978-3-540-13372-8.{{cite book}}: |journal= ignored (help)
  5. ↑ Aviezri Fraenkel and D. Lichtenstein (1981). "Computing a perfect strategy for n×n chess requires time exponential in n". J. Comb. Theory A. 31 (2): 199–214. doi: 10.1016/0097-3165(81)90016-9 .
  6. ↑ J. M. Robson (1984). "N by N checkers is Exptime complete". SIAM Journal on Computing. 13 (2): 252–267. doi:10.1137/0213018.
  7. ↑ Wolfe, David (2002). Nowakowski, Richard J. (ed.). "Go endgames are PSPACE-hard" (PDF). More Games of No Chance, Mathematical Sciences Research Institute Publications 42: 125–136. Archived from the original (PDF) on 2017-08-10. Retrieved 2016-07-09.
  8. ↑ Crâşmaru, Marcel; Tromp, John (2000). "Ladders Are PSPACE-Complete". Computers and Games. Lecture Notes in Computer Science. Vol. 2063. Springer. pp. 241–249. CiteSeerX   10.1.1.24.4665 . doi:10.1007/3-540-45579-5_16. ISBN   978-3-540-43080-3.
  9. 1 2 Tromp, J; Farnebäck, G (2007), "Combinatorics of Go", Computers and Games, Lecture Notes in Computer Science, vol. 4630, Springer, Berlin, Heidelberg, pp. 84–99, doi:10.1007/978-3-540-75538-8_8, ISBN   978-3-540-75537-1
  10. ↑ 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
  11. ↑ "Combinatorics of Go" (PDF). github.io. Retrieved 17 June 2023.
  12. ↑ Allis 1994
  13. ↑ Walraet, M; Tromp, J (2016), "A Googolplex of Go Games", Computers and Games, Lecture Notes in Computer Science, vol. 10068, Springer, Berlin, Heidelberg, pp. 191–201, doi:10.1007/978-3-319-50935-8_18, ISBN   978-3-319-50934-1
  14. ↑ "Home - American Go Association". www.usgo.org. Retrieved 17 June 2023.
  15. ↑ Tromp 1999
  16. ↑ "Statistics on the length of a go game".

Related Research Articles

The P versus NP problem is a major unsolved problem in theoretical computer science. Informally, it asks whether every problem whose solution can be quickly verified can also be quickly solved.

In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and explores the relationships between these classifications. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm.

<span class="mw-page-title-main">NP (complexity)</span> Complexity class used to classify decision problems

In computational complexity theory, NP is a complexity class used to classify decision problems. NP is the set of decision problems for which the problem instances, where the answer is "yes", have proofs verifiable in polynomial time by a deterministic Turing machine, or alternatively the set of problems that can be solved in polynomial time by a nondeterministic Turing machine.

<span class="mw-page-title-main">PSPACE</span> Set of decision problems

In computational complexity theory, PSPACE is the set of all decision problems that can be solved by a Turing machine using a polynomial amount of space.

In computational complexity theory, a decision problem is PSPACE-complete if it can be solved using an amount of memory that is polynomial in the input length and if every other problem that can be solved in polynomial space can be transformed to it in polynomial time. The problems that are PSPACE-complete can be thought of as the hardest problems in PSPACE, the class of decision problems solvable in polynomial space, because a solution to any one such problem could easily be used to solve any other problem in PSPACE.

In computational complexity theory, the complexity class EXPTIME (sometimes called EXP or DEXPTIME) is the set of all decision problems that are solvable by a deterministic Turing machine in exponential time, i.e., in O(2p(n)) time, where p(n) is a polynomial function of n.

In computational complexity theory, EXPSPACE is the set of all decision problems solvable by a deterministic Turing machine in exponential space, i.e., in space, where is a polynomial function of . Some authors restrict to be a linear function, but most authors instead call the resulting class ESPACE. If we use a nondeterministic machine instead, we get the class NEXPSPACE, which is equal to EXPSPACE by Savitch's theorem.

A solved game is a game whose outcome can be correctly predicted from any position, assuming that both players play perfectly. This concept is usually applied to abstract strategy games, and especially to games with full information and no element of chance; solving such a game may use combinatorial game theory and/or computer assistance.

Combinatorial game theory measures game complexity in several ways:

  1. State-space complexity,
  2. Game tree size,
  3. Decision complexity,
  4. Game-tree complexity,
  5. Computational complexity.
<span class="mw-page-title-main">Complexity class</span> Set of problems in computational complexity theory

In computational complexity theory, a complexity class is a set of computational problems "of related resource-based complexity". The two most commonly analyzed resources are time and memory.

<span class="mw-page-title-main">Rush Hour (puzzle)</span> Sliding block puzzle

Rush Hour is a sliding block puzzle invented by Nob Yoshigahara in the 1970s. It was first sold in the United States in 1996. It is now being manufactured by ThinkFun.

In computational complexity theory, P, also known as PTIME or DTIME(nO(1)), is a fundamental complexity class. It contains all decision problems that can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.

In computational complexity theory, the polynomial hierarchy is a hierarchy of complexity classes that generalize the classes NP and co-NP. Each class in the hierarchy is contained within PSPACE. The hierarchy can be defined using oracle machines or alternating Turing machines. It is a resource-bounded counterpart to the arithmetical hierarchy and analytical hierarchy from mathematical logic. The union of the classes in the hierarchy is denoted PH.

<span class="mw-page-title-main">Generalized game</span> Game generalized so that it can be played on a board or grid of any size

In computational complexity theory, a generalized game is a game or puzzle that has been generalized so that it can be played on a board or grid of any size. For example, generalized chess is the game of chess played on an board, with pieces on each side. Generalized Sudoku includes Sudokus constructed on an grid.

The Game of the Amazons is a two-player abstract strategy game invented in 1988 by Walter Zamkauskas of Argentina. The game is played by moving pieces and blocking the opponents from squares, and the last player able to move is the winner. It is a member of the territorial game family, a distant relative of Go and chess.

In computational complexity theory, P/poly is a complexity class representing problems that can be solved by small circuits. More precisely, it is the set of formal languages that have polynomial-size circuit families. It can also be defined equivalently in terms of Turing machines with advice, extra information supplied to the Turing machine along with its input, that may depend on the input length but not on the input itself. In this formulation, P/poly is the class of decision problems that can be solved by a polynomial-time Turing machine with advice strings of length polynomial in the input size. These two different definitions make P/poly central to circuit complexity and non-uniform complexity.

In computational complexity theory, generalized geography is a well-known PSPACE-complete problem.

In computational complexity theory, the complexity class 2-EXPTIME (sometimes called 2-EXP) is the set of all decision problems solvable by a deterministic Turing machine in O(22p(n)) time, where p(n) is a polynomial function of n.

In computational complexity theory, the language TQBF is a formal language consisting of the true quantified Boolean formulas. A (fully) quantified Boolean formula is a formula in quantified propositional logic where every variable is quantified, using either existential or universal quantifiers, at the beginning of the sentence. Such a formula is equivalent to either true or false. If such a formula evaluates to true, then that formula is in the language TQBF. It is also known as QSAT.

References

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.