moboy78 wrote:
I would imagine having a 1x1 board is impossible. The smallest board you could conceivably have is a 2x2 board.
| Attachments: |
|
1x1 board.jpg [ 4.43 KiB | Viewed 9033 times ] |
| Life In 19x19 http://prod.lifein19x19.com/ |
|
| Possible # of legal positions. http://prod.lifein19x19.com/viewtopic.php?f=10&t=10374 |
Page 1 of 2 |
| Author: | Solomon [ Thu May 29, 2014 1:46 pm ] |
| Post subject: | Possible # of legal positions. |
From the wiki page on Go and mathematics, the number of legal (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 |
|
| Author: | cyndane [ Thu May 29, 2014 2:11 pm ] |
| Post subject: | Re: Possible # of legal positions. |
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 |
|
| Author: | xed_over [ Thu May 29, 2014 2:26 pm ] |
| Post subject: | Re: Possible # of legal positions. |
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) |
|
| Author: | Shawn Ligocki [ Thu May 29, 2014 2:30 pm ] |
| Post subject: | Re: Possible # of legal positions. |
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.) |
|
| Author: | Uberdude [ Thu May 29, 2014 2:40 pm ] |
| Post subject: | Re: Possible # of legal positions. |
Legal positions or legal moves? the thread content and title are inconsistent. |
|
| Author: | Shawn Ligocki [ Thu May 29, 2014 2:41 pm ] |
| Post subject: | Re: Possible # of legal positions. |
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 |
|
| Author: | Solomon [ Thu May 29, 2014 2:45 pm ] |
| Post subject: | Re: Possible # of legal positions. |
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. |
|
| Author: | DrStraw [ Thu May 29, 2014 5:01 pm ] |
| Post subject: | Re: Possible # of legal positions. |
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. |
|
| Author: | gowan [ Thu May 29, 2014 6:01 pm ] |
| Post subject: | Re: Possible # of legal positions. |
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? |
|
| Author: | DrStraw [ Thu May 29, 2014 6:05 pm ] |
| Post subject: | Re: Possible # of legal positions. |
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. |
|
| Author: | Mef [ Thu May 29, 2014 6:30 pm ] |
| Post subject: | Re: Possible # of legal positions. |
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 |
|
| Author: | ez4u [ Fri May 30, 2014 3:54 am ] |
| Post subject: | Re: Possible # of legal positions. |
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? |
|
| Author: | moboy78 [ Fri May 30, 2014 6:55 am ] |
| Post subject: | Re: Possible # of legal positions. |
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. |
|
| Author: | DrStraw [ Fri May 30, 2014 7:14 am ] | ||
| Post subject: | Re: Possible # of legal positions. | ||
moboy78 wrote: I would imagine having a 1x1 board is impossible. The smallest board you could conceivably have is a 2x2 board.
|
|||
| Author: | moyoaji [ Fri May 30, 2014 7:54 am ] |
| Post subject: | Re: Possible # of legal positions. |
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. |
|
| Author: | Dusk Eagle [ Fri May 30, 2014 8:31 am ] |
| Post subject: | Re: Possible # of legal positions. |
The triple kos would end the game only if the players insisted on playing out the kos. The appearance of a triple ko board position does not instantly end the game. For instance, sometimes one player decides to sacrifice the kos in order to gain a winning position. So though contrived, it would be possible to form seven or eight simultaneous kos on the board. |
|
| Author: | Dusk Eagle [ Fri May 30, 2014 8:45 am ] |
| Post subject: | Re: Possible # of legal positions. |
Quote: 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? Yes. Black can set all of his stones into the desired position while white passes every turn. Once black has placed the last of his pieces that he will place, white begins placing his stones and black starts passing. |
|
| Author: | Mef [ Fri May 30, 2014 10:45 am ] |
| Post subject: | Re: Possible # of legal positions. |
moyoaji wrote: The only thing that might vary would be if the board state contained many important kos. I don't think ko can affect the number of legal positions. By its nature ko prevents the repetition of a position, which presumably means the position must be played at least once before a ban can take effect. |
|
| Author: | shapenaji [ Fri May 30, 2014 11:28 am ] |
| Post subject: | Re: Possible # of legal positions. |
I wonder if there's a simplification in terms of using legal "lines" to make up a full board. Starting by laying down the first line of the board, and then adjusting the number of legal strips next to it. Suppose we have a 3x3 board, we have 3^3 = 27 potential lines that we can lay down for the first strip. You'd need a set of rules to define what strips can go next after the first one, but then you might be able to simplify the process by treating multiple strips as a single strip. If you could simplify in this way, you might be able to get an exact number. for example, the following is an illegal strip in response to the first one: And here is a legal strip: now, after this strip, all the next legal strips respond to this precisely as they would to just this: In effect, the first strip has been simplified away. This may be a useless exercise, but maybe not, thoughts? |
|
| Author: | bayu [ Fri May 30, 2014 12:06 pm ] |
| Post subject: | Re: Possible # of legal positions. |
shapenaji wrote: I wonder if there's a simplification in terms of using legal "lines" to make up a full board. This may be a useless exercise, but maybe not, thoughts? 2 Thoughts: Taking advantage of the fact that the game is not played on a torus definitively seems natural. And your method might work, but I don't think it is that easy: has lots of legal successors, like now, after this strip, all the next legal strips -won't- respond to this precisely as they would to just this: In effect, you have to remember some information from the further left. However, if you label each stone in your row according to whether its group has a liberty somewhere on the left or not, all the necessary information seems to be there. |
|
| Page 1 of 2 | All times are UTC - 8 hours [ DST ] |
| Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ |
|