Go and mathematics
Go 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. 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 being a specific example of its use in Go).
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. 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.
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.
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
Robson and checkers are EXPTIME-complete. However, this result does not apply to Go.
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. 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 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 <math>L(m,n)</math> of a rectangle board with length m and n. The exact number of <math>L(19,19)</math> was obtained in 2016. 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 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.
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. 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. The most commonly quoted number for the number of possible games, 10700 is derived from a simple permutation of 361 moves or . Another common derivation is to assume N intersections and L longest game for N 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.
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 forms an upper limit. A more accurate limit is presented in the Tromp/Farnebäck paper.
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 years, playing 16 hours a day at one move per second, to play 47 million moves.