It is currently Sun May 09, 2021 6:10 am

All times are UTC - 8 hours [ DST ]




Post new topic Reply to topic  [ 17 posts ] 
Author Message
Offline
 Post subject: Number of Legal 19x19 positions calculated
Post #1 Posted: Fri Jan 22, 2016 7:15 am 
Judan

Posts: 6686
Location: Cambridge, UK
Liked others: 432
Was liked: 3663
Rank: UK 4 dan
KGS: Uberdude 4d
OGS: Uberdude 7d
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.


This post by Uberdude was liked by: sorin
Top
 Profile  
 
Offline
 Post subject: Re: Number of Legal 19x19 positions calculated
Post #2 Posted: Fri Jan 22, 2016 7:24 am 
Oza

Posts: 2182
Location: ʍoquıɐɹ ǝɥʇ ɹǝʌo 'ǝɹǝɥʍǝɯos
Liked others: 237
Was liked: 660
Rank: AGA 5d
GD Posts: 4312
Online playing schedule: Every tenth February 29th from 20:00-20:01 (if time permits)
Interesting but it does get me too excited. It is about as useful as calculating pi to more than 100 digits.

_________________
Still officially AGA 5d but I play so irregularly these days that I am probably only 3d or 4d over the board (but hopefully still 5d in terms of knowledge, theory and the ability to contribute).

Top
 Profile  
 
Offline
 Post subject: Re: Number of Legal 19x19 positions calculated
Post #3 Posted: Fri Jan 22, 2016 8:56 am 
Gosei
User avatar

Posts: 1585
Location: Barcelona, Spain (GMT+1)
Liked others: 577
Was liked: 298
Rank: KGS 5k
KGS: RBerenguel
Tygem: rberenguel
Wbaduk: JohnKeats
Kaya handle: RBerenguel
Online playing schedule: KGS on Saturday I use to be online, but I can be if needed from 20-23 GMT+1
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.

_________________
Geek of all trades, master of none: the motto for my blog mostlymaths.net

Top
 Profile  
 
Offline
 Post subject: Re: Number of Legal 19x19 positions calculated
Post #4 Posted: Fri Jan 22, 2016 9:06 am 
Judan

Posts: 6686
Location: Cambridge, UK
Liked others: 432
Was liked: 3663
Rank: UK 4 dan
KGS: Uberdude 4d
OGS: Uberdude 7d
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.

Top
 Profile  
 
Offline
 Post subject: Re: Number of Legal 19x19 positions calculated
Post #5 Posted: Fri Jan 22, 2016 9:26 am 
Gosei

Posts: 1501
Liked others: 452
Was liked: 420
Rank: 5d
GD Posts: 1000
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.

Top
 Profile  
 
Offline
 Post subject: Re: Number of Legal 19x19 positions calculated
Post #6 Posted: Fri Jan 22, 2016 9:41 am 
Tengen

Posts: 5324
Liked others: 0
Was liked: 726
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.

Top
 Profile  
 
Offline
 Post subject: Re: Number of Legal 19x19 positions calculated
Post #7 Posted: Fri Jan 22, 2016 9:47 am 
Lives in sente

Posts: 839
Location: Littleton, CO
Liked others: 286
Was liked: 264
Rank: KGS 3k
Universal go server handle: jeromie
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.)

Top
 Profile  
 
Offline
 Post subject: Re: Number of Legal 19x19 positions calculated
Post #8 Posted: Fri Jan 22, 2016 10:07 am 
Oza

Posts: 2182
Location: ʍoquıɐɹ ǝɥʇ ɹǝʌo 'ǝɹǝɥʍǝɯos
Liked others: 237
Was liked: 660
Rank: AGA 5d
GD Posts: 4312
Online playing schedule: Every tenth February 29th from 20:00-20:01 (if time permits)
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.

_________________
Still officially AGA 5d but I play so irregularly these days that I am probably only 3d or 4d over the board (but hopefully still 5d in terms of knowledge, theory and the ability to contribute).

Top
 Profile  
 
Offline
 Post subject: Re: Number of Legal 19x19 positions calculated
Post #9 Posted: Fri Jan 22, 2016 11:09 am 
Honinbo

Posts: 10722
Liked others: 3610
Was liked: 3348
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.

_________________
The Adkins Principle:
At some point, doesn't thinking have to go on?
— Winona Adkins

Visualize whirled peas.

Everything with love. Stay safe.

Top
 Profile  
 
Offline
 Post subject: Re: Number of Legal 19x19 positions calculated
Post #10 Posted: Sun Jan 24, 2016 2:12 am 
Lives in gote

Posts: 323
Location: Potsdam, Germany
Liked others: 198
Was liked: 76
Rank: 14 kyu
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?

_________________
Poka King of the south east.

Top
 Profile  
 
Offline
 Post subject: Re: Number of Legal 19x19 positions calculated
Post #11 Posted: Sun Jan 24, 2016 1:16 pm 
Tengen

Posts: 4347
Location: North Carolina
Liked others: 489
Was liked: 721
Rank: AGA 3k
GD Posts: 65
OGS: Hyperpape 4k
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.

_________________
Occupy Babel!

Top
 Profile  
 
Offline
 Post subject: Re: Number of Legal 19x19 positions calculated
Post #12 Posted: Sun Jan 24, 2016 1:22 pm 
Lives in gote

Posts: 323
Location: Potsdam, Germany
Liked others: 198
Was liked: 76
Rank: 14 kyu
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.

_________________
Poka King of the south east.

Top
 Profile  
 
Offline
 Post subject: Re: Number of Legal 19x19 positions calculated
Post #13 Posted: Tue Jan 26, 2016 12:34 pm 
Lives with ko

Posts: 202
Location: Santiago, Chile
Liked others: 39
Was liked: 44
Rank: EGF 1d
Universal go server handle: Jhyn
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.

_________________
La victoire est un hasard, la défaite une nécessité.

Top
 Profile  
 
Offline
 Post subject: Re: Number of Legal 19x19 positions calculated
Post #14 Posted: Sun Mar 25, 2018 9:58 am 
Lives with ko

Posts: 289
Location: Spain
Liked others: 176
Was liked: 32
Rank: Low
GD Posts: 10
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.

_________________
Sum ergo non ero.

Top
 Profile  
 
Offline
 Post subject: Re: Number of Legal 19x19 positions calculated
Post #15 Posted: Mon Mar 26, 2018 2:37 am 
Tengen

Posts: 5324
Liked others: 0
Was liked: 726
Tromp posted the number ca. 2 years ago, after ca. 20 years of his research in the topic.

Top
 Profile  
 
Offline
 Post subject: Re: Number of Legal 19x19 positions calculated
Post #16 Posted: Mon Mar 26, 2018 3:23 am 
Gosei
User avatar

Posts: 2005
Location: Groningen, NL
Liked others: 202
Was liked: 1081
Rank: Dutch 4D
GD Posts: 645
Universal go server handle: herminator
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. :)

Top
 Profile  
 
Offline
 Post subject: Re: Number of Legal 19x19 positions calculated
Post #17 Posted: Sun Jan 03, 2021 10:24 am 
Tengen

Posts: 4347
Location: North Carolina
Liked others: 489
Was liked: 721
Rank: AGA 3k
GD Posts: 65
OGS: Hyperpape 4k
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.

_________________
Occupy Babel!


This post by hyperpape was liked by: Uberdude
Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 17 posts ] 

All times are UTC - 8 hours [ DST ]


Who is online

Users browsing this forum: No registered users and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group