Go and mathematics

File:Go-game-ear-reddening.jpeg

A game of Go

The game of Go is one of the most popular games in the world, and is in on par with games such as Chess (and its Asian variants) in terms of game theory and as an intellectual activity. It has also been argued to be the most complex of all games, with most advocates referring to the difficulty in programming the game to be played by computers and the large number of variations of play. While the strongest computer chess software has defeated top players (Deep Blue beat the world champion in 1997), the best Go programs routinely lose to talented children; and consistently reaching only the 8–10 kyu range of ranking. Many in the field of artificial intelligence consider Go to be a better measure of a computer's capacity for thought than chess.

Complexity and the go game tree

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 10³⁶⁰. For the number of theoretically possible games, including ones impossible to play in practice, see John Tromp and Gunnar Farnebäck (2007). "Combinatorics of Go". This paper gives lower and upper bounds of 10¹⁰⁴⁸ and 10¹⁰¹⁷¹ respectively. It also shows that on a 19×19 board, about 1.196% of board setups are legal positions, which makes 3³⁶¹×0.01196... = 2.08168199382 ×10¹⁷⁰, "of which we can expect all digits to be correct" (i.e. because the convergence is so fast). Since each location on the board can be either empty, black, or white, there are a total 3^N possible board positions. As the board gets larger the percentage of these that are legal decreases.

Game size	Board size N	3^N	Percent legal	Maximum legal game positions
1x1	1	3	100%	3
2x2	4	81	70%	57
3x3	9	19,683	64%	12,675
4x4	16	43,046,721	56%	24,318,165
5x5	25	8.47x1011	49%	4.1x1011
9x9	81	4.4x1038	23.4%	1.039x1038
13x13	169	4.3x1080	8.66%	3.7x1079
19x19	361	10172	1.1196%	2.08168199382x10170
21x21	441	2.57x10210

The most commonly quoted number for the number of possible games, 10⁷⁰⁰ is derived from a simple permutation of 361 moves or 361! = 10⁷⁶⁸. 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 x 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
2x2	4	24	3	64		386,356,909,593
3x3	9	3.6x105	5	5.9x104
4x4	16	2.1x1013	9	6.9x1010
5x5	25	1.6x1025	15	9.3x1020
9x9	81	5.8x10120	45	7.6x1085
13x13	169	4.3x10304	90	3.2x10200
19x19	361	1.0x10768	200	3x10511	1048	101048	1010171
21x21	441	2.5x10976	250	1.3x10661

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, fails to include captures and positions that are not legal. Taking N as the board size (19x19=361), 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 (19x19)	N!	N^L	Lower Limit of games	Notes
1	10768	361	361	White resigns after first move
50	10768	7.5x10127
100	10768	5.6x10255
150	10768	4.2x10383
200	10768	3.2x10511
250	10768	2.4x10639
300	10768	7.8x10766
350	10768	1.3x10895
361	10768	1.8x10923		Longest game using 181 black and 180 white stones
400	10768	1.0x101023		Longest professional games
500	10768	5.7x101278
1000	10768	3.2x102557
47 million	10768	10108		361^3 moves
1048	10768	1010171	101048	Longest game

From this table we can see that 10⁷⁰⁰ is a gross over estimate of the number of possible games that can be played in 200 moves and a gross under estimate of the number of games that can be played in 400 moves. It can also be noted that since there are about 31 million seconds in a year it would take about 2 and one quarter years playing 16 hours a day at one move per second to play 47 million moves. As to 10⁴⁸, since the future age of the universe is projected to be a lot less than a 1000 trillion years and no computer is ever projected to compute anything close to a trillion Teraflops, any number higher than 10³⁹ is clearly beyond possibility of being played.

Positional complexity

Many of the commonly seen established opening strategies, joseki and tactical shapes which aid skillful play have been developed over thousands of years of play and taught to successive generations rather than discovered through individual play. There are many positional situations in Go which are instantly recognizable by an experienced player that are hard to recognize otherwise. Once players gain knowledge of these patterns in play, they then must ponder how to apply them in accordance with the position of the board as it stands and the recognizable patterns already in place. Thus, the traditions of Go strategical theory utilized by most stronger players and taught to beginners help to somewhat limit the scope of variation in actual play, while deepening strategy.

See also

• Game complexity
• Shannon number (Chess)
• Pi (film)

References

• Combinatorics of Go online viewer
• Go and Mathematics
• Victor Allis (1994). Searching for Solutions in Games and Artificial Intelligence (PDF). Ph.D. Thesis, University of Limburg, Maastricht, The Netherlands. ISBN 9090074880.