Number of Possible Go Games
The number of possible go games is extremely large. It is often compared to the number of atoms in the universe ( around 10^80), but it is in fact much much larger. In this article, we will first explore the question from a mathematical perspective, and then also give some information on bounds for realistic game lengths.
Table of contents |
Mathematical bounds
Restriction of cycles
In rule sets that allow cycles, such as those that only restrict basic ko, games can go on indefinitely, and there is no upper limit to the number of games that can be played. It is therefore necessary to only consider those rules that have some form of superko rules, or other ko rules preventing the game from going on indefinitely. The most usual approach is to use the Logical rules of go, which are the easiest to work with from a mathematical perspective.
Number of legal positions
One number of interest for use in calculations of the number of possible games is the number of legal positions. An upper bound of the number of positions on a 19x19 go board is not hard to calculate. Every intersection can be either black, white, or empty, so the number of possible positions is exactly 3^361, which is ~1.741 × 10^172. For this bound, symmetry is not accounted.
However, many of these positions contain strings of stones without liberties and therefore are not legal. The exact number of legal positions has been calculated for square boards up to size 19×19 by Tromp and others^{[1]}^{[2]}.
Some numbers:
- 9×9 board: ~1.039 × 10^38
- 13×13 board: ~3.724 × 10^79
- 17×17 board: ~1.908 × 10^137
- 19×19 board: ~2.082 × 10^170 (i.e., a 2 followed by 170 zeroes)
For the 19×19 board, the number of legal positions is about 1.196% of the possible positions^{[3]}.
Upper bound on longest game length
From the number of legal positions, we can establish a definite upper bound for the possible length of a game. If no cycles are allowed, then theoretically, the longest possible game would reach every legal position once before ending. This means that no game can last more than 2.08 × 10^170 moves. Tromp and Farnebäck have shown that no game can exist that visits all legal positions, but what fraction of them can be visited in a single game is unclear.
Lower bound on longest game length
The upper bound on game length of 2.08 × 10^170 is an absolute upper bound, but the actual upper bound is lower. John Tromp was able to construct a method by which many legal positions can be cycled through systematically, and was able to show that it is possible to play a game lasting at least 10^48 moves on a 19x19 board.
Bounds on number of games
From the upper bound on game length, we can derive an upper bound on the possible number of games. If a game can last up to 2.08 × 10^170 moves, and at each point has at most 361 legal moves, then the possible number of games cannot be larger than 361^(2.08 × 10^170), which is equal to 10^(5.3 × 10^170). From the lower bound, we can similarly show that the number of possible go games is at least 10^(10^48).
Real game bounds
The bounds given above are mathematically correct, but they depend on games of extreme lengths. It is humanly impossible to play a game of 10^48 moves. The age of the universe is only in the order of 10^17 seconds, so you would have to play 10^31 moves per second in order to finish the game within a few billion years.
Statistics from real games between professional players show that it is extremely rare for a game to last more than 400 moves. If, on average, there are 100 legal moves in every position, then the possible number of games of length 400 or less is in the order of 10^800, corresponding to around 10^720 possible games for every atom in the known universe.
See also
References
- [1] http://tromp.github.io/go/legal.html
- [2] http://view.samurajdata.se/ps.php?url=http://tromp.github.io/go/gostate.ps
Footnotes
- [3] This number also includes symmetric positions.
Old content
RobertJasiek: Before reinventing the wheel, read the rec.games.go Rules FAQ!
ilan: It seems to me that total possible number of Go games on a board with N points is, very roughly, N^L, where L is the length of the longest possible game. To see this, note that in a long game (a game which last more than the number of intersections N), then basically every N moves the board will have to be cleared to allow the game to continue. It follows that the board will be cleared then filled about L/N times. Each time the board is filled, there will be very roughly N! ways to fill in this way by changing the order of the moves. The number of different possible games which go through the same position as the longest game will therefore be (N!)^(L/N). In particular, if the game stops after the first N moves, you get the oft quoted 361! figure for the number of games in 19x19 Go. Anyway, N! is very roughly equal to N^N, so it follows that the total number of games constructed above will very roughly be (N^N)^(L/N) = N^L. It seems to me that this construction probably generates almost all possible Go games, for large N, so this would be the right order of magnitude in that case.
If this seems too vague, then a precise statement would be as follows: Let T be the total number of go games on a board of size N, and L the length of the longest game, then Log(T)/(L * Log(N)) -> 1 as N -> Infinity.
If this argument is accepted, the question of total possible games is reduced to the question of the longest possible game. On that page, it is claimed that L grows faster than any power of N, so this would mean that the total number of games would grow faster than N^N^k, for any fixed k. The exact computation for square boards generates an N^3 length game, so one should be able to get an explicit lower bound of about 361^361^3 for the ordinary 19x19 game.
There are about 361! ways to play GO. How much is that ?
5! = 5 x 4 x 3 x 2 x 1 = 120
20! = 20 x 19 x 18 x...x 3 x 2 x 1 = 2,432,902,008,176,640,000
100! = 93,326,180, 000,000,000,000,000,000,000,000,000,000, 000,000,000,000,000,000,000,000,000,000, 000,000,000,000,000,000,000,000,000,000, 000,000,000,000,000,000,000,000,000,000, 000,000,000,000,000,000,000,000,000,000
ilan: This is obviously wrong, since the number of trailing zeroes is equal to the number of multiples of 5 (with multiplicity) less than 100 which equals 100/5 + 100/25 = 24. Now for some really large arguments in the factorial function:
Infinity! := 1 x 2 x 3 x 4 x ... = sqrt(2 pi)
http://www.dorsai.org/~walts/fact100.html A number that has 158 digits!
Here is a direct quote from this website, indicating the level of its author: " I was able to print out a googol for one of my sons, for his math class." ilan
A googol is 1 followed by 100 zeros. So 100! > 1 googol.
Incredible! Imagine how big 361! is.
361! = 1.4379232588848906548323625114999e+768 (use the scientific calculator that comes with windows to calculate)
I doubt that there can ever be a computer that can have the capacity to store all those data.
ilan: As Americans are fond of saying: "Grow Up!"
http://library.thinkquest.org/CR0215002/go/game1.htm It has been estimated that there are more possible Go games than there are atoms in the known universe! (proof required. anyone? ) eng60340
LoP: It's not true that there are 361! possible games. Not every empty point on the board is a valid move. (Also symmetric positions are not really different games)
Niklaus: However, symmetry doesn't change the number that much. 361! / 8 is still a pretty big number. Then there's also the points that you can play on more than once (after capture(s)), which probably cancel out the illegal moves (I'm not a mathematician so I'm just guessing). The exact number won't be 361! for sure, but I don't think it's such a bad estimate.
ilan: It is a terrible underestimate! The reason is that because of capturing, a go game can have N^2 moves, where N is the number of intersections (N = 361 for the ordinary board). In fact, it seems reasonable to me that as N goes to infinity, most possible go games will have on the order of N^2 moves, because there are just more of them. It follows easily that a lower bound for the number of go games is (N - 2)! x (N - 3)! x (N - 4)! x ..., so asymptotically about N^(N^2) instead of about N^N for N! (to be precise, there is an extra exponential term, which is negligible). To see this, consider the following games: Black moves in a corner, then White plays N-2 moves while Black keeps passing, leaving only one open intersection next to the black stone. There are (N-2)! ways of doing this. Black now captures N - 2 stones. Next, white plays N - 3 moves leaving one open space next to the two Black stones, and Black captures, etc. I started wondering about the Longest Possible Game.
ilan: This follows the annoying line of the googol, which is actually a "small" number in a precise sense, e.g., compared to 9^9^...^9 where the stack has 9^9^9 terms. The point is that a googol or 100! are numbers which have short description, so are not very complex, and one can name much larger numbers with similar complexity.
fatoudust: The harder question is trying to figure out how many possible games there could be that actually make sense as games which might happen between two rational players. The vast majority of "possible games" would never occur with players with even a marginal knowledge of the rules and basic theory. The best estimates I've seen of this number are still much larger than the estimated number of atoms in the universe however, which is about 10^80 if I recall.
Let's lowball and say the average game is 150 moves, and that on average a player is only seriously considering about ten possible choices per move, so 10^150, and dividing by eight for symmetry still gives 1.25* 10^149. With only looking at merely five choices per move, that still gives a result of 8.75 * 10^103, or 23 orders of magnitude greater than the atoms in the universe! I wouldn't count on repeating a game anytime soon... (my first contribution to SL, by the way!)
GoJaC: People always obsess over 361! ... Unlike chess, a Go game's "state" is purely described by the board position (in chess you need to know if the king has moved at all, before you know if you may still castle, e.g.) - as such, I feel we should not be so hung up over move sequence, and rather look at board positions. In that case we have 3^361 (each position on the board is either empty, black, or white). This drops the upper limit from 10^768 to 1.7409e+172. (Note that it is not completely true that Go does not care about previous positions: one may not repeat a previous board position -> Ko...
deg: Because of ko, 4^361 is a better (although way too high) upper bound for number of possible board states. Its '4' because the empty point that you can't play in (because of the ko rule) is another type of point.
GoJaC: Interesting point. I don't know if it is necessary though. Consider the graph-based representation I mention further down, the "Ko" rule is in fact more just "you cannot repeat the same board state twice in one game" - i.e. it isn't really a "state" to have a point you can't play in, it is a previous board state you simply may not return to...
deg: Using Polya's Enumeration Theorem, I think that the number of possible colourings of a 19x19 grid (using 3 colours) is between 2.17E+171 and 2.18E+171. (In fact (3^361)/8 is a good approximation.) But how many are legal? I generated 2000 random boards, and found 20 to be legal, so the number of legal Go board positions (ignoring ko) could be around 2E+169
fatoudust: Sure, 3^361 is the upper bound for the number of possible board states. Of course, the actual number is less than this because some of these won't be legal. However, With any given legal board state, there are many game "paths" through this state. Up to two raised to the power of blank spaces left on the board for the next state, and up to two to the power of occupied spaces on the board for possible previous states (yes, maybe?). Going in both directions, we quickly accumulate a vast number of possible games each unique board position could be a part of!
Think of each possible board state as a "digit" and each possible game as a "number" formed from those digits according to the rules of go. How many numbers up to 361 digits can we form just using 0 through 9, for a simplistic example?
Should we start a "possible number of go games" page? This seems to be a topic of interest.
GoJaC More misc "what's on my mind right now" chatter... Maybe consider thinking of it as a "graph", with the 3^361 states (minus the number of "illegal" states due to lack of liberties) being the "nodes" of the graph. Each "move" moves from one node to another, being the "edges" of the graph. Now, how many edges, on average, can each node have? I think an absolute maximum of (361+1)*2 (361 places to go on an empty board, and the possible "pass", and can be either black or white's move - of course, can double the number of nodes instead, saying "this is the state, and it is B (or W)'s move"). Now, whereas there are 1.7409e+172 nodes, there are an *absolute maximum* of 1.2604e+175 edges in this graph. Sure, you can string these edges together in various ways, but I like thinking of it then as borrowing different moves from different games...
I still like "A New Stone Makes a New Game", and probably take it too far - that is the reason I like to think of it as 3^361 games, with various ways of getting "from one game to the next". ;-)
Well, its fun to think about that huge numbers, but the numbers are that huge that - I think - the real point got lost.
Question:
Dos a greatest number exist which can be expressed using the types a-z and the blank using max hunderedforty placements?
Well, may could think 27^140.
But look: what we can do by using our language:
This is the greatest number which can be expressed using the types a to z and the blank using max hunderedforty placements puls one
So this is also happend by go. Its infinite.
Infact using a 21 times 21 goban destroy the game.
moved from Kami no Itte
SonOfJoy?: It is impossible for a computer to read ahead to the end of the game -- even in chess. In chess the computers are capable to read deep? enough to win against a world champion, but it is impossible to compute and store all possible paths. And go is even more complex due to its number of fields and due to the fact that in contrary to chess the setting on the board is not necesarrily getting simple. It is estimated that there are 10^80 atoms in our universe -- that is little more than 2^240. Go with its roundabout 2^361 combinations (it really does not matter that there are symmetric settings, neither does it matter that there are settings which never appear in a real game) would need a machine that is capable to store more than 1 bit of information per atom in the universe... If you are able to do that with a universe, you found "kami-no-ite" -- for sure!
- sykomantis?: I would say it's more like 3^361 combinations if you are including empty points as a possible state but otherwise I agree.