Possible # of legal positions.

[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?

[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

[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)

[Shawn Ligocki]

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.)

[Uberdude]

Legal positions or legal moves? the thread content and title are inconsistent.

[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

[Solomon]

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.

[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.

[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?

[DrStraw]

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.

[Mef]

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

[ez4u]

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?

[moboy78]

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.

[DrStraw]

I would imagine having a 1x1 board is impossible. The smallest board you could conceivably have is a 2x2 board.

[moyoaji]

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.