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).
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.
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.
[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.
[8] This is proven by simulating QBF, known to be PSPACE-complete, with ladders that bounce around the board like light beams.
Tromp and Farnebäck derived a recursive formula for legal positions
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).
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.
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.
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.