Complexity of Go: Calculating the Game Tree Estimate

  • Thread starter Thread starter Astudious
  • Start date Start date
  • Tags Tags
    Complexity
Click For Summary
The discussion centers on the immense complexity of the game Go, highlighting estimates of possible game positions and sequences. It mentions that there are approximately 2.1×10^170 possible board positions and an estimated 9.3×10^567 different games without captures, with captures potentially increasing this number significantly. The calculation of (120!)^2 is explained as the number of ways to arrange 120 stones played by both players, but the reason for limiting to 120 stones is questioned. The challenge of accurately estimating game-tree complexity, especially with captures, is acknowledged, along with the notion that some games may have been repeated, similar to chess. Understanding these calculations is crucial for grasping the vast possibilities within Go.
Astudious
Messages
61
Reaction score
0
I have found various Internet sources claiming words to the following effect, regarding the board-game Go:

"It is commonly said that no game has ever been played twice. This may be true: On a 19×19 board, there are about 3^361×0.012 = 2.1×10^170 possible positions, most of which are the end result of about (120!)^2 = 4.5×10^397 different (no-capture) games, for a total of about 9.3×10^567 games. Allowing captures gives as many as 10^(7.49×10^48) possible games, most of which last for over 1.6×10^49 moves! (By contrast, the number of legal positions in chess is estimated to be between 10^43 and 10^50, and physicists estimate that there are not more than 10^90 protons in the entire universe.)"

I would love to hear where certain of these figures come from, or perhaps to understand how to calculate the game-tree complexity of Go in the first place. Where (120!)^2 and 9.3×10^567 are coming from seems unclear, let alone 10^(7.49×10^48).

I would have thought that, disallowing captures, (19*19)! gives an estimate, but I appear to have severely overcounted as (19*19)! = 1.44*10^768.

Any idea how to reach a better estimate? Including with captures?
 
Mathematics news on Phys.org
(120!)2 is the number of possible ways to reach a specific end if both players put down 120 stones (but not more) in various different orders (120 choices for the first stone, 119 for the second, ...). Multiply this by the number of possible positions and you get the quoted total number of games without captures. I don't know why this calculation limits the stones to 120. The Wikipedia article quotes 10761 which is very close to your estimate.

Captures make it hard...I am quite sure there are game that have been played more than once - like in Chess, players reproducing a previous game to study it.
 

Thread 'Area of Overlapping Squares'

Here is a little puzzle from the book 100 Geometric Games by Pierre Berloquin. The side of a small square is one meter long and the side of a larger square one and a half meters long. One vertex of the large square is at the center of the small square. The side of the large square cuts two sides of the small square into one- third parts and two-thirds parts. What is the area where the squares overlap?
View full post »

Similar threads

How can I avoid large exponents in calculations with small answers?
  • · Replies 5 ·
Replies
5
Views
3K