Page 1 of 3
Possible # of legal positions.
Posted: Thu May 29, 2014 1:46 pm
by Solomon
From the
wiki page on Go and mathematics, the number of legal
moves positions based on the size of the Go board:
(1, 1) -> 1
(2, 2) -> 57
(3, 3) -> 12,675
...
(19, 19) -> 2.08168199382 * 10^170
My question is, is there a function that takes the board size as input and can output the possible number of legal
moves positions?
Re: Possible # of legal positions.
Posted: Thu May 29, 2014 2:11 pm
by cyndane
The function isnt specified here, but maybe reading some of John Tromps work would reveal it? The sequence itself may be interesting to you?
https://oeis.org/search?q=1%2C57%2C1267 ... &go=Search
Re: Possible # of legal positions.
Posted: Thu May 29, 2014 2:26 pm
by xed_over
wouldn't a 1x1 board have 0 legal positions? The first stone played would have no free liberties, so its already illegal.
or is suicide legal? In that case, the number of legal moves would be 2 (one each for black and white), after that the board position repeats. (or maybe it repeats after the first move, so we're back to 1 legal move)
Re: Possible # of legal positions.
Posted: Thu May 29, 2014 2:30 pm
by Shawn Ligocki
xed_over wrote:wouldn't a 1x1 board have 0 legal positions? The first stone played would have no free liberties, so its already illegal.
or is suicide legal? In that case, the number of legal moves would be 2 (one each for black and white), after that the board position repeats. (or maybe it repeats after the first move, so we're back to 1 legal move)
No, it has 1 legal position, the empty board. (At least I assume that a position is a choice of {Black, White, or Empty} for every coordinate on the board and legal means that all groups have >= 1 liberty.)
Re: Possible # of legal positions.
Posted: Thu May 29, 2014 2:40 pm
by Uberdude
Legal positions or legal moves? the thread content and title are inconsistent.
Re: Possible # of legal positions.
Posted: Thu May 29, 2014 2:41 pm
by Shawn Ligocki
I suspect there's no simple way to specify the function, but you can read the paper by Tromp and Farnebäck that is mentioned in the Wikipedia article:
http://www.researchgate.net/publication ... f5f2a0.pdf
Re: Possible # of legal positions.
Posted: Thu May 29, 2014 2:45 pm
by Solomon
Uberdude wrote:Legal positions or legal moves? the thread content and title are inconsistent.
Sorry Uberdude. I meant positions in the post, but of course both are of interest.
Re: Possible # of legal positions.
Posted: Thu May 29, 2014 5:01 pm
by DrStraw
Almost certainly there cannot be a function which gives an exact value. But there may be one which gives a fair estimate. Sort of like the the approximate formula x/logx for the number of primes.
Re: Possible # of legal positions.
Posted: Thu May 29, 2014 6:01 pm
by gowan
Of course there is such a function! It is defined by P(n) = the number of legal go positions on an nxn board. Equally of course this definition doesn't help you to compute the function's values but that's not what Araban asked.
I think some care is needed in stating what counts as a legal position. Is it true that all arrangements of stones such that each group has at least one liberty are reachable from an empty board by a sequence of moves valid according to whatever rule set is being used?
Re: Possible # of legal positions.
Posted: Thu May 29, 2014 6:05 pm
by DrStraw
gowan wrote:Of course there is such a function! It is defined by P(n) = the number of legal go positions on an nxn board. Equally of course this definition doesn't help you to compute the function's values but that's not what Araban asked.
I think some care is needed in stating what counts as a legal position. Is it true that all arrangements of stones such that each group has at least one liberty are reachable from an empty board by a sequence of moves valid according to whatever rule set is being used?
If you are going to be pedantic then maybe it is not a function. Maybe the number of different board positions depends on the rule set and so it is merely a relation. I'm not actually sure if a position can be legal under one rule set and not under another.
Re: Possible # of legal positions.
Posted: Thu May 29, 2014 6:30 pm
by Mef
DrStraw wrote: I'm not actually sure if a position can be legal under one rule set and not under another.
To my knowledge there are no positions among common rule sets that would be legal in one but not another. The only ways to make a position illegal is to have a group with no liberties remain on the board, and this is universally forbidden. I suppose there would be strange exceptions for tournament rules where a player can accept the position "as is" (implicitly under AGA) as opposed to having a forfeit occur (Japanese)...But I'm thinking we'll skip over that because it's a bit too much of a meta game
Re: Possible # of legal positions.
Posted: Fri May 30, 2014 3:54 am
by ez4u
Mef wrote:DrStraw wrote: I'm not actually sure if a position can be legal under one rule set and not under another.
To my knowledge there are no positions among common rule sets that would be legal in one but not another. The only ways to make a position illegal is to have a group with no liberties remain on the board, and this is universally forbidden. I suppose there would be strange exceptions for tournament rules where a player can accept the position "as is" (implicitly under AGA) as opposed to having a forfeit occur (Japanese)...But I'm thinking we'll skip over that because it's a bit too much of a meta game
What about suicide moves? If Black plays a suicide move as a ko threat, does the turn end with the suicide stones still on the board? In other words, does White remove the stones as a part of her turn? If so, that would seem to create such a position, no?
Re: Possible # of legal positions.
Posted: Fri May 30, 2014 6:55 am
by moboy78
xed_over wrote:wouldn't a 1x1 board have 0 legal positions? The first stone played would have no free liberties, so its already illegal.
or is suicide legal? In that case, the number of legal moves would be 2 (one each for black and white), after that the board position repeats. (or maybe it repeats after the first move, so we're back to 1 legal move)
I would imagine having a 1x1 board is impossible. The smallest board you could conceivably have is a 2x2 board.
Re: Possible # of legal positions.
Posted: Fri May 30, 2014 7:14 am
by DrStraw
moboy78 wrote:
I would imagine having a 1x1 board is impossible. The smallest board you could conceivably have is a 2x2 board.
Re: Possible # of legal positions.
Posted: Fri May 30, 2014 7:54 am
by moyoaji
ez4u wrote:What about suicide moves? If Black plays a suicide move as a ko threat, does the turn end with the suicide stones still on the board? In other words, does White remove the stones as a part of her turn? If so, that would seem to create such a position, no?
Suicide functions exactly like capturing. So if black plays a suicide move, then white immediately captures his stones. This occurs as part of black's turn, not white's turn, so the board state never has stones without liberties on it.
The only thing that might vary would be if the board state contained many important kos. A triple ko rule would end a game before it reached 7 or 8 large kos, so these board positions would be unreachable under certain rulesets. However, they would not necessarily be illegal board states.