Go and mathematics
Encyclopedia
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. While the strongest computer chess software has defeated top players (Deep Blue beat the world champion Garry Kasparov
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
.
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 number
s and contributed to development of combinatorial game theory
(with Go Infinitesimals being a specific example of its use in Go).
game. Rule variations that places a polynomial bound on the length of the game produces a PSPACE-complete
game. The complexity of Go with superko rules remains an open question.
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 361! = 10768. 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 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, NL forms an upper limit. A more accurate limit is presented in the Tromp/Farnebäck paper.
From this table, we can see that 10700 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 1048, since the future age of the universe is projected to be less than 1000 trillion years and no computer is projected to compute anything close to a trillion Teraflop
s (one yottaflop), any number higher than 1039 is beyond possibility of being played.
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
are taught to beginners help to limit the scope of variation in actual play while deepening strategy.
Go (board game)
Go , is an ancient board game for two players that originated in China more than 2,000 years ago...
is one of the most popular games in the world and is on par with games such as chess, in any of its Western
Chess
Chess is a two-player board game played on a chessboard, a square-checkered board with 64 squares arranged in an eight-by-eight grid. It is one of the world's most popular games, played by millions of people worldwide at home, in clubs, online, by correspondence, and in tournaments.Each player...
or Asian variants, in terms of game theory
Game theory
Game theory is a mathematical method for analyzing calculated circumstances, such as in games, where a person’s success is based upon the choices of others...
and as an intellectual
Intellectual
An intellectual is a person who uses intelligence and critical or analytical reasoning in either a professional or a personal capacity.- Terminology and endeavours :"Intellectual" can denote four types of persons:...
activity. It has also been argued to be the most complex of all games
Game complexity
Combinatorial game theory has several ways of measuring game complexity. This article describes five of them: state-space complexity, game tree size, decision complexity, game-tree complexity, and computational complexity.-Measures of game complexity:...
, with most advocates referring to the difficulty in programming the game
Computer Go
Computer Go is the field of artificial intelligence dedicated to creating a computer program that plays Go, a traditional board game.-Performance:...
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 Garry Kasparov
Garry Kasparov
Garry Kimovich Kasparov is a Russian chess grandmaster, a former World Chess Champion, writer, political activist, and one of the greatest chess players of all time....
in 1997), the best Go programs routinely lose to talented children and consistently reach only the 1-10 kyu
Go ranks and ratings
Skill in the traditional board game Go is measured by a number of different national, regional and online ranking and rating systems. Traditionally, go rankings have been measured using a system of dan and kyu ranks...
range of ranking. Many in the field of artificial intelligence
Artificial intelligence
Artificial intelligence is the intelligence of machines and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its...
consider Go to be a better measure of a computer's capacity for thought than chess
Chess
Chess is a two-player board game played on a chessboard, a square-checkered board with 64 squares arranged in an eight-by-eight grid. It is one of the world's most popular games, played by millions of people worldwide at home, in clubs, online, by correspondence, and in tournaments.Each player...
.
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
John Horton Conway
John Horton Conway is a prolific mathematician active in the theory of finite groups, knot theory, number theory, combinatorial game theory and coding theory...
led to the invention of the surreal number
Surreal number
In mathematics, the surreal number system is an arithmetic continuum containing the real numbers as well as infinite and infinitesimal numbers, respectively larger or smaller in absolute value than any positive real number...
s and contributed to development of combinatorial game theory
Combinatorial game theory
Combinatorial game theory is a branch of applied mathematics and theoretical computer science that studies sequential games with perfect information, that is, two-player games which have a position in which the players take turns changing in defined ways or moves to achieve a defined winning...
(with Go Infinitesimals being a specific example of its use in Go).
Legal positions
Since each location on the board can be either empty, black, or white, there are a total of 3N possible board positions on a board with N intersections. Tromp and Farnebäck show that on a 19×19 board, about 1.2% of board positions are legal (no stones without liberties exist on the board), which makes for 3361×0.012... = 2.1 ×10170 legal positions "of which we can expect all digits to be correct" (i.e. because the convergence is so fast). 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-completeEXPTIME
In computational complexity theory, the complexity class EXPTIME is the set of all decision problems solvable by a deterministic Turing machine in O time, where p is a polynomial function of n....
game. Rule variations that places a polynomial bound on the length of the game produces a PSPACE-complete
PSPACE-complete
In complexity theory, a decision problem is PSPACE-complete if it is in the complexity class PSPACE, and every problem in PSPACE can be reduced to it in polynomial time...
game. The complexity of Go with superko rules remains an open question.
| Game size | Board size N | 3N | Percent legal | Maximum legal game positions |
|---|---|---|---|---|
| 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×1011 | 49% | 4.1×1011 |
| 9×9 | 81 | 4.4×1038 | 23.4% | 1.039×1038 |
| 13×13 | 169 | 4.3×1080 | 8.66% | 3.72497923×1079 |
| 19×19 | 361 | 1.74×10172 | 1.196% | 2.08168199382×10170 |
| 21×21 | 441 | 2.57×10210 |
Game tree complexity
The computer scientistComputer scientist
A computer scientist is a scientist who has acquired knowledge of computer science, the study of the theoretical foundations of information and computation and their application in computer systems....
Victor Allis
Victor Allis
Louis Victor Allis is a Dutch computer scientist working in the artificial intelligence field. In his graduate work, he revealed AI solutions for Connect Four, Qubic, and Gomoku. His dissertation introduced two new game search techniques: proof-number search and dependency-based search...
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 361! = 10768. 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 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 size | Board size N (intersections) | N | Average game length L | NL | Maximum game length (# of moves) | Lower Limit of games | Upper Limit of games |
|---|---|---|---|---|---|---|---|
| 2×2 | 4 | 24 | 3 | 64 | 386,356,909,593 | ||
| 3×3 | 9 | 3.6×105 | 5 | 5.9×104 | |||
| 4×4 | 16 | 2.1×1013 | 9 | 6.9×1010 | |||
| 5×5 | 25 | 1.6×1025 | 15 | 9.3×1020 | |||
| 9×9 | 81 | 5.8×10120 | 45 | 7.6×1085 | |||
| 13×13 | 169 | 4.3×10304 | 90 | 3.2×10200 | |||
| 19×19 | 361 | 1.0×10768 | 200 | 3×10511 | 1048 | 101048 | 1010171 |
| 21×21 | 441 | 2.5×10976 | 250 | 1.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)L | Lower Limit of games | Upper Limit of games | Notes |
|---|---|---|---|---|
| 1 | 1 | 361 | 361 | White resigns after first move |
| 50 | 2.1×10126 | 7.5×10127 | ||
| 100 | 1.4×10249 | 5.6×10255 | ||
| 150 | 6.4×10367 | 4.2×10383 | ||
| 200 | 1.9×10481 | 3.2×10511 | ||
| 250 | 8.2×10587 | 2.4×10639 | ||
| 300 | 2.8×10684 | 7.8×10766 | ||
| 350 | 3.6×10760 | 1.3×10895 | ||
| 361 | 1.4×10768 | 1.8×10923 | Longest game using 181 black and 180 white stones | |
| 400 | n/a | 1.0×101023 | Longest professional games | |
| 500 | n/a | 5.7×101278 | ||
| 1000 | n/a | 3.2×102557 | ||
| 47 million | n/a | 10108 | 361^3 moves | |
| 1048 | n/a | 101048 | 1010171 | Longest game |
From this table, we can see that 10700 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 1048, since the future age of the universe is projected to be less than 1000 trillion years and no computer is projected to compute anything close to a trillion Teraflop
FLOPS
In computing, FLOPS is a measure of a computer's performance, especially in fields of scientific calculations that make heavy use of floating-point calculations, similar to the older, simpler, instructions per second...
s (one yottaflop), any number higher than 1039 is beyond possibility of being played.
Positional complexity
Go opening theory
In the game of Go, the term opening theory refers to concepts which underlie where, why, in what order, and in what shapes the first several moves are played...
, joseki
Joseki
In Go, are studied sequences of moves in the corner areas of the Go board, for which the result is considered balanced for both black and white sides. Because games typically start with plays in the corners, players often try to use their understanding of joseki to gain local advantages in the...
and tactical shapes
Shape (Go)
In the game of Go, shape describes the positional qualities of a group of stones. Descriptions of shapes in go revolve around how well a group creates or removes life and territory. Good shape can refer to the efficient use of stones in outlining territory, the strength of a group in a prospective...
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
Go players
This page gives an overview of well-known players of the game of Go throughout the ages. The page has been divided into sections based on the era in which the Go players played and the country in which they played. As this was not necessarily their country of birth, a flag of that country precedes...
are taught to beginners help to limit the scope of variation in actual play while deepening strategy.
External links
- Combinatorics of Go online viewer
- Go and Mathematics