Go and mathematics

From Wikipedia, the free encyclopedia

Part of a series of articles on Go (board game)


Game specifics Go rules Go handicaps Go proverb Go terms Go strategy and tactics History & Culture History of Go Go equipment Hikaru no Go Go variants Four go houses Players & Organisations Go players Go ranks and ratings Go professional Go organizations Go competitions Computers & Mathematics Go and mathematics Computer Go Go software Internet Go server This box: view • talk • edit

The game of Go is one of the most popular games in the world and is on par with games such as chess, in any of its Western or 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.^[1] 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 reach only the 1-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.^[2]

As a result of its elegant and simple rules, the game of Go 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^[3] being a specific example of its use in Go).

1 Legal positions
2 Game tree complexity
3 Positional complexity
4 See also
5 Notes
6 References
7 External links

[edit] Legal positions

Since each location on the board can be either empty, black, or white, there are a total of 3^N possible board positions. Tromp and Farnebäck show that on a 19×19 board, about 1.196% of board positions are legal (no stones without liberties exist on the board), which makes for 3³⁶¹×0.01196... = 2.08168199382 ×10¹⁷⁰ legal positions "of which we can expect all digits to be correct" (i.e. because the convergence is so fast).^[4] As the board gets larger, the percentage of the positions that is legal decreases. Go (with Japanese ko rules) is a two player un-bounded EXPTIME-complete game.^[5]

Game size	Board size N	3^N	Percent legal	Maximum legal game positions^[6]
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×10¹¹	49%	4.1×10¹¹
9×9	81	4.4×10³⁸	23.4%	1.039×10³⁸
13×13	169	4.3×10⁸⁰	8.66%	3.72497923×10⁷⁹
19×19	361	1.74×10¹⁷²	1.196%	2.08168199382×10¹⁷⁰
21×21	441	2.57×10²¹⁰

[edit] 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 10³⁶⁰.^[7] For the number of theoretically possible games, including ones impossible to play in practice. Tromp and Farnebäck give lower and upper bounds of 10^10⁴⁸ and 10^10¹⁷¹ respectively.^[8] The most commonly quoted number for the number of possible games, 10⁷⁰⁰^[1] 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⁴⁰⁰ or 1 × 10¹⁰²³ 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
2×2	4	24	3	64		386,356,909,593^[9]
3×3	9	3.6×10⁵	5	5.9×10⁴
4×4	16	2.1×10¹³	9	6.9×10¹⁰
5×5	25	1.6×10²⁵	15	9.3×10²⁰
9×9	81	5.8×10¹²⁰	45	7.6×10⁸⁵
13×13	169	4.3×10³⁰⁴	90	3.2×10²⁰⁰
19×19	361	1.0×10⁷⁶⁸	200	3×10⁵¹¹	10⁴⁸	10^10⁴⁸	10^10¹⁷¹
21×21	441	2.5×10⁹⁷⁶	250	1.3×10⁶⁶¹

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 illegal captures and positions. Taking N as the board size (19×19=361) and 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 (19×19)	(N)_L	N^L	Lower Limit of games	Notes
1	1	361	361	White resigns after first move
50	2.1×10¹²⁶	7.5×10¹²⁷
100	1.4×10²⁴⁹	5.6×10²⁵⁵
150	6.4×10³⁶⁷	4.2×10³⁸³
200	1.9×10⁴⁸¹	3.2×10⁵¹¹
250	8.2×10⁵⁸⁷	2.4×10⁶³⁹
300	2.8×10⁶⁸⁴	7.8×10⁷⁶⁶
350	3.6×10⁷⁶⁰	1.3×10⁸⁹⁵
361	1.4×10⁷⁶⁸	1.8×10⁹²³		Longest game using 181 black and 180 white stones
400	n/a	1.0×10¹⁰²³		Longest professional games
500	n/a	5.7×10¹²⁷⁸
1000	n/a	3.2×10²⁵⁵⁷
47 million	n/a	10^10⁸		361^3 moves
10⁴⁸		10^{2.6×10⁴⁸}	10^10⁴⁸	Longest game

From this table, we can see that 10⁷⁰⁰ 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 10⁴⁸, 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, any number higher than 10³⁹ is beyond possibility of being played.

[edit] Positional complexity

A game of Go

Many of the commonly seen 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 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 limit the scope of variation in actual play while deepening strategy.