Complexity of Go: Calculating the Game Tree Estimate

  • Context: Graduate 
  • Thread starter Thread starter Astudious
  • Start date Start date
  • Tags Tags
    Complexity
Click For Summary
SUMMARY

The complexity of the game Go is staggering, with estimates suggesting approximately 2.1×10^170 possible positions on a 19×19 board and around 9.3×10^567 distinct games without captures. The calculation of game-tree complexity involves understanding the factorial of moves, specifically (120!)^2, which represents the permutations of stone placements by both players. The discussion highlights the challenge of calculating these figures accurately, especially when considering captures, which significantly increase the number of possible game outcomes.

PREREQUISITES
  • Understanding of combinatorial mathematics
  • Familiarity with factorial notation and its applications
  • Basic knowledge of the game Go and its rules
  • Awareness of game-tree complexity concepts
NEXT STEPS
  • Research the mathematical foundations of game-tree complexity in Go
  • Explore combinatorial game theory and its applications to board games
  • Learn about the impact of captures on game complexity in Go
  • Examine existing literature on Go's game-tree estimates and their derivations
USEFUL FOR

Mathematicians, game theorists, Go enthusiasts, and anyone interested in the complexities of strategic board games.

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.
 

Similar threads

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