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?

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

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

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

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

Sorry Uberdude. I meant positions in the post, but of course both are of interest.

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.

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

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.

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

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?

_________________
Dave Sigaty
"Short-lived are both the praiser and the praised, and rememberer and the remembered..."
- Marcus Aurelius; Meditations, VIII 21

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

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

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.

_________________
"You have to walk before you can run. Black 1 was a walking move.
I blushed inwardly to recall the ignorant thoughts that had gone through
my mind before, when I had not realized the true worth of Black 1."
-Kageyama Toshiro on proper moves

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.

_________________
We don't know who we are; we don't know where we are.
Each of us woke up one moment and here we were in the darkness.
We're nameless things with no memory; no knowledge of what went before,
No understanding of what is now, no knowledge of what will be.

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.

_________________
We don't know who we are; we don't know where we are.
Each of us woke up one moment and here we were in the darkness.
We're nameless things with no memory; no knowledge of what went before,
No understanding of what is now, no knowledge of what will be.

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.

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.

Click Here To Show Diagram Code

[go]$$Bc Example: A strip
$$ ---------
$$ | B . . |
$$ | W . . |
$$ | B . . |
$$ ---------[/go]

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:

Click Here To Show Diagram Code

[go]$$Bc Example: A strip
$$ ---------
$$ | B W . |
$$ | W B . |
$$ | B W . |
$$ ---------[/go]

And here is a legal strip:

Click Here To Show Diagram Code

[go]$$Bc Example: A strip
$$ ---------
$$ | B B . |
$$ | W . . |
$$ | B B . |
$$ ---------[/go]

now, after this strip, all the next legal strips respond to this precisely as they would to just this:

Click Here To Show Diagram Code

[go]$$Bc Example: A strip
$$ -------
$$ | B . |
$$ | . . |
$$ | B . |
$$ -------[/go]

In effect, the first strip has been simplified away.

This may be a useless exercise, but maybe not, thoughts?

_________________
Tactics yes, Tact no...

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:

Click Here To Show Diagram Code

[go]$$Bc Example: A strip
$$ ---------
$$ | B . . |
$$ | . . . |
$$ | B . . |
$$ ---------[/go]

has lots of legal successors, like

Click Here To Show Diagram Code

[go]$$Bc Example: A strip
$$ ---------
$$ | B B . |
$$ | . W . |
$$ | B B . |
$$ ---------[/go]

now, after this strip, all the next legal strips -won't- respond to this precisely as they would to just this:

Click Here To Show Diagram Code

[go]$$Bc Example: A strip
$$ -------
$$ | B . |
$$ | W . |
$$ | B . |
$$ -------[/go]

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.

_________________
If something sank it might be a treasure. And 2kyu advice is not necessarily Dan repertoire..