Number of Legal 19x19 positions calculated

[Uberdude]

I just saw that John Tromp has announced the number of legal 19x19 board positions as:

208168199381979984699478633344862770286522453884530548425639456820927419612738015378525648451698519643907259916015628128546089888314427129715319317557736620397247064840935

See http://tromp.github.io/go/legal.html for more.

[DrStraw]

Interesting but it does get me too excited. It is about as useful as calculating pi to more than 100 digits.

[RBerenguel]

Interesting but it does get me too excited. It is about as useful as calculating pi to more than 100 digits.

Mathematics is about expanding knowledge, you should know that.

[Uberdude]

I was indeed surprised a mathematician such as DrStraw would complain about lack of usefulness, but then maybe he is a grumpy old man first and a mathematician second .

P.S. I don't think there's many instances where you'd need pi to even that precision. IIRC you need about 40 digits to calculate the size of the observable universe to the accuracy of an atom, so unless you were calculating something with powers of pi (which is not so common) to increase the error then 100 is more than you need.

[gowan]

Obviously the value of this lies in the methods used, not in knowing the particular number. I was interested to see that they define a valid position as one in which every chain of stones of one color is adjacent to an empty point. It's not clear to me that every such position could actually arise as a result of a sequence of valid moves starting with an empty board. It seems more interesting to me to count how many actual game positions there could be.

[RobertJasiek]

I was interested to see that they define a valid position as one in which every chain of stones of one color is adjacent to an empty point. It's not clear to me that every such position could actually arise as a result of a sequence of valid moves starting with an empty board.

Trivial. Alternate to play the upper left most stone in the position to be constructed. If a player has played all his stones in that position, he passes. During the construction sequence, each string has at least one liberty because a) it has at least one liberty in the position to be constructed or b) has at least one liberty on an intersection to be filled later by a same-coloured stone. QED.

[jeromie]

It's not clear to me that every such position could actually arise as a result of a sequence of valid moves starting with an empty board.

Due to its capture rule, the positions that can arise in a game of Go are exactly the legal positions.

Remember that passing is a legal move, too, so between placing stones, captures, and passing you can pretty easily reach any legal board state.

(And Robert beat me to the punch.)

[DrStraw]

I was indeed surprised a mathematician such as DrStraw would complain about lack of usefulness, but then maybe he is a grumpy old man first and a mathematician second .

P.S. I don't think there's many instances where you'd need pi to even that precision. IIRC you need about 40 digits to calculate the size of the observable universe to the accuracy of an atom, so unless you were calculating something with powers of pi (which is not so common) to increase the error then 100 is more than you need.

I may be grumpy at times but I am not old. And I have not been a mathematician now for several years, at least not in the sense that I actively do mathematics.

I do agree with the second paragraph though. It was exactly that which prompted my comment but I could not remember off the top of my head how many digits were required so I just said 100. Oh, and I wasn't complaining: merely commenting that I personally do not get excited by such results.

[Bill Spight]

It's not clear to me that every such position could actually arise as a result of a sequence of valid moves starting with an empty board.

Due to its capture rule, the positions that can arise in a game of Go are exactly the legal positions.

Remember that passing is a legal move, too, so between placing stones, captures, and passing you can pretty easily reach any legal board state.

(And Robert beat me to the punch.)

Passing is a move in Ing Rules and AGA rules, but not in all modern versions of the rules.

[TheBigH]

I assume this calculation does not count rotations, reflections, and swapping black and white as different positions. Well, I know that the colour swap doesn't count, or the number of legal positions would be an even number.

It's interesting to see that the number of legal positions is odd for every board size up to 19x19. Is this always true?

[hyperpape]

It doesn't account for rotations--all rotated versions are counted as separate positions. The odd number is because the empty board is legal, but the full board is not.

[TheBigH]

Ah, good point. Although even if full boards were allowed it would still be an odd number because there are 2^361 possible fully occupied boards.

[Jhyn]

Mathematics is about expanding knowledge, you should know that.

As a mathematician myself, I do think that "knowledge expansion" has to be divided between gathering trivia and gathering information that deepen our understanding (with most research sitting in the middle). Knowing the actual number lies formly on the former side in my opinion (which is perfectly fine ; trivia is fun), as it doesn't help us understand anything better. The fact that we are able to count it so efficiently, on the other hand, is impressive.

[luigi]

It doesn't account for rotations--all rotated versions are counted as separate positions. The odd number is because the empty board is legal, but the full board is not.

Hmm, no. The odd number is because all positions but the empty board come in pairs where one results from reversing the colors of the other.

[RobertJasiek]

Tromp posted the number ca. 2 years ago, after ca. 20 years of his research in the topic.