The number of potential positions on a Go board


There's a reference to research done by Tromp and Taylor at Position that may be relevant. Their estimate is higher by many orders of magnitude. --Hyperpapeterie

Theorem: There are more than one googol (10^100) potential positions on a 19x19 Go board, allowing technically illegal positions in which a group of stones has no liberties.

Proof: Each point on the board either contains a black stone, a white stone, or no stone. There are 19*19=361 points on a Go board. Therefore the number of combinations is 3^361 > 3^360 = 3^(3*120) = (3^3)^120 = 27^120 > 10^120 > 10^100

Lemma: There are more than eight googol (8*10^100) legal board positions on a Go board. Why do I say eight googol instead of one googol? See my next theorem after this lemma.

Proof: Suppose you allow board positions with only black stones and no white stones. Each point either contains a black stone or no stone. The number of combinations is 2^361. However, exactly one of these board positions is illegal:

The only illegal board position with no white stones  

As you can see, this is illegal, because the huge black group has no liberties. But any other combination of black stones and empty points is legal. Therefore, there are 2^361 - 1 such combinations.

Let S be the set of legal positions allowing black and white stones. Let n be the number of elements in S. The set of legal positions allowing only black stones is a subset of S. Therefore, n > 2^361 - 1

-1 > -2^360

n > 2^361 - 1 > 2^361 - 2^360 = 2*2^360 - 2^360 = (2 - 1)*2^360 = 1*2^360 = 2^360 = 2^(10*36) = (2^10)^36 = 1024^36 > 1000^36 = (10^3)^36 = 10^(3*36) = 10^108 > 10^101 = 10*10^100 > 8*10^100

Theorem: There are more than one googol legal board positions that are unique after taking transformations into account. The following are examples of transformations:

Original position  

Proof: Let T be a set of legal board positions that are unique after taking transformations into account. T is not the only such set, but it contains the maximum number of elements, which we'll call m. By replacing each element in T by eight elements that are the transformations of that element, the resulting set is identical to S. However, Some board positions are rotationally and/or reflectively symmetrical, meaning that they transform into themselves, Here are some examples:

Rotational symmetry  
Reflective symmetry  

Therefore, 8m > n > 8*10^100

m > 10^100

Theorem: There are more than one googol legal board positions in which all stones are alive according to the rules of go:

Proof: Consider the set of all possible arrangements where white stones are restricted to points north of Tengen, and black stones are restricted to points south of Tengen. This is only a subset of all possible legal positions. In the white half each point is either empty or contains a white stone, and the white half consists of 9*19=171 points. There are therefore 2^171 possible arrangements.

Board divided into black and white halves. Neither side can place a stone at the line dividing the halves, marked by squares.  

It is also obviously impossible for any of the white stones to be dead since every white group must have liberties inside the white half, or in the line between the black and white halves.

All these things are true of the black stones as well. Since the arrangement of the black stones is independent of the white ones, there must be a total of (2^171)^2=4^171 total arrangements of stones. 4^171 > 8*10^102 > 10^100. QED.

The number of potential positions on a Go board last edited by on March 9, 2015 - 18:24
RecentChanges · StartingPoints · About
Edit page ·Search · Related · Page info · Latest diff
[Welcome to Sensei's Library!]
Search position
Page history
Latest page diff
Partner sites:
Go Teaching Ladder
Login / Prefs
Sensei's Library