Complexity of Go: Calculating the Game Tree Estimate

  • Context: Graduate 
  • Thread starter Thread starter Astudious
  • Start date Start date
  • Tags Tags
    Complexity
Join the discussion
Ask a follow-up here, or get your own question answered by working scientists, mathematicians and engineers — people, not an autocomplete.
Real named experts · corrections over time · the nuance an AI answer skips
Sign up Log in
1 reply · 3K views
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.