Complexity of Go: Calculating the Game Tree Estimate

[Astudious]

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?

 

[mfb]

(120!)² 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 10⁷⁶¹ 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.