Life In 19x19
http://www.lifein19x19.com/

Number of Legal 19x19 positions calculated
http://www.lifein19x19.com/viewtopic.php?f=9&t=12625
Page 1 of 1

Author:  Uberdude [ Fri Jan 22, 2016 7:15 am ]
Post subject:  Number of Legal 19x19 positions calculated

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.

Author:  DrStraw [ Fri Jan 22, 2016 7:24 am ]
Post subject:  Re: Number of Legal 19x19 positions calculated

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

Author:  RBerenguel [ Fri Jan 22, 2016 8:56 am ]
Post subject:  Re: Number of Legal 19x19 positions calculated

DrStraw wrote:
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.

Author:  Uberdude [ Fri Jan 22, 2016 9:06 am ]
Post subject:  Re: Number of Legal 19x19 positions calculated

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.

Author:  gowan [ Fri Jan 22, 2016 9:26 am ]
Post subject:  Re: Number of Legal 19x19 positions calculated

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.

Author:  RobertJasiek [ Fri Jan 22, 2016 9:41 am ]
Post subject:  Re: Number of Legal 19x19 positions calculated

gowan wrote:
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.

Author:  jeromie [ Fri Jan 22, 2016 9:47 am ]
Post subject:  Re: Number of Legal 19x19 positions calculated

gowan wrote:
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.


the article wrote:
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.)

Author:  DrStraw [ Fri Jan 22, 2016 10:07 am ]
Post subject:  Re: Number of Legal 19x19 positions calculated

Uberdude wrote:
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. :grumpy:

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.

Author:  Bill Spight [ Fri Jan 22, 2016 11:09 am ]
Post subject:  Re: Number of Legal 19x19 positions calculated

jeromie wrote:
gowan wrote:
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.


the article wrote:
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.

Author:  TheBigH [ Sun Jan 24, 2016 2:12 am ]
Post subject:  Re: Number of Legal 19x19 positions calculated

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?

Author:  hyperpape [ Sun Jan 24, 2016 1:16 pm ]
Post subject:  Re: Number of Legal 19x19 positions calculated

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.

Author:  TheBigH [ Sun Jan 24, 2016 1:22 pm ]
Post subject:  Re: Number of Legal 19x19 positions calculated

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.

Author:  Jhyn [ Tue Jan 26, 2016 12:34 pm ]
Post subject:  Re: Number of Legal 19x19 positions calculated

RBerenguel wrote:
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.

Author:  luigi [ Sun Mar 25, 2018 9:58 am ]
Post subject:  Re: Number of Legal 19x19 positions calculated

hyperpape wrote:
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.

Author:  RobertJasiek [ Mon Mar 26, 2018 2:37 am ]
Post subject:  Re: Number of Legal 19x19 positions calculated

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

Author:  HermanHiddema [ Mon Mar 26, 2018 3:23 am ]
Post subject:  Re: Number of Legal 19x19 positions calculated

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


The first post in this thread is actually from January 2016. It just got revived after two years of silence. :)

Author:  hyperpape [ Sun Jan 03, 2021 10:24 am ]
Post subject:  Re: Number of Legal 19x19 positions calculated

Uberdude wrote:
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.
https://www.youtube.com/watch?v=HEfHFsf ... PM&index=3 The practical implications should be obvious to anyone.

Page 1 of 1 All times are UTC - 8 hours [ DST ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/