Forum for Number of Possible Go Games
Lower bound [#2099]
I think using the lower bound of the number of moves in a game to get a lower bound of the number of possible games in this way does not hold water, for at least two reasons:
- The calculation only works if we assume that every game can be extended to this length
- The calculation should also use a _lower bound_ rather than an _upper bound_ for the number of moves at any one time
I think you may be right, I'll have to think about that. In this specific case however, it doesn't matter.
John Tromp's calculation was based on the fact that you can construct a position so that the game becomes 1 dimensional, where the points along the dimension can de filled a a systematic way to get 10^48 moves, and where you can play them in any order.
Specifically (if I am not mistaken), this position:
![[Diagram]](diagrams/42/1cacf10b5a03b179067890a7e2adaed9.png)
Where there are 103 black and 103 white stones that are fully connected, as well as 155 empty points, all of which are adjacent to both the black and the white group.
Tromp's proof involves the fact that you can fill the empty points with one color (while the other player passes) except for one, then the other player captures, and then you rebuild the position in many different ways, with the one extra stone in place, and then repeat. He further proved that you can then cycle through all the possible fillings of the empty points as a Gray code, and since you can number the points in any order, he proved a lower bound of (103!)^(2^154) on the number of games from that. For details, see section 6.4 (p31 and further) in his paper.
![[Welcome to Sensei's Library!]](images/stone-hello.png "Sensei's Library")