1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Complexity of Go

  1. Sep 6, 2015 #1
    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?
  2. jcsd
  3. Sep 7, 2015 #2


    User Avatar
    2017 Award

    Staff: Mentor

    (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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook