Possible # of legal positions.

Dusk Eagle · Post by **Dusk Eagle** » Fri May 30, 2014 8:31 am

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.

Dusk Eagle · Post by **Dusk Eagle** » Fri May 30, 2014 8:45 am

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.

Mef · Post by **Mef** » Fri May 30, 2014 10:45 am

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.

shapenaji · Post by **shapenaji** » Fri May 30, 2014 11:28 am

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?

bayu · Post by **bayu** » Fri May 30, 2014 12:06 pm

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:

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.

shapenaji · Post by **shapenaji** » Fri May 30, 2014 12:39 pm

bayu wrote:
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.

Right, there are strips that don't simplify nicely. If you just maintain one additional strip behind (open or closed)

Maybe that's all you need?

if we track two rows, and then an open/closed row, that should be of order, 3^19 * 3^19 * 2^19, a big number ~10^24 but a computable one.

Shaddy · Post by **Shaddy** » Fri May 30, 2014 1:46 pm

You don't care about the actual second row, only whether or not each group on the current row has a liberty, so you can do it with 3^19 * 2^19 states (which is a pretty loose bound, since there's less than 19 groups on each row). It's still annoying to run, though, since it's too large for RAM on a home computer

shapenaji · Post by **shapenaji** » Fri May 30, 2014 1:49 pm

Shaddy wrote:You don't care about the actual second row, only whether or not each group on the current row has a liberty, so you can do it with 3^19 * 2^19 states (which is a pretty loose bound, since there's less than 19 groups on each row). It's still annoying to run, though, since it's too large for RAM on a home computer

Well, you do need to track the simplifying row for each combination of rows, right? So then you can pipe that back in.

xed_over · Post by **xed_over** » Fri May 30, 2014 1:52 pm

Shawn Ligocki wrote:
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.)

My confusion came from the term "legal board positions" -- which conjured in my mind images of legitimate alternating moves or plays.

What we're actually talking about here are abstract legal board states -- irregardless of how we got there.

shapenaji · Post by **shapenaji** » Fri May 30, 2014 1:55 pm

xed_over wrote:
My confusion came from the term "legal board positions" -- which conjured in my mind images of legitimate alternating moves or plays.

What we're actually talking about here are abstract legal board states -- irregardless of how we got there.

I'm going to go out on a limb and make a conjecture, every legal board state can be reached by a legitimate set of plays.

My reasoning is, I can remove any stone from a legal board state, and the remaining board state will still be legal. There are no backwards transitions from legal board states to illegal ones.

Tryss · Post by **Tryss** » Fri May 30, 2014 4:39 pm

shapenaji wrote:
xed_over wrote:
My confusion came from the term "legal board positions" -- which conjured in my mind images of legitimate alternating moves or plays.

What we're actually talking about here are abstract legal board states -- irregardless of how we got there.
I'm going to go out on a limb and make a conjecture, every legal board state can be reached by a legitimate set of plays.

My reasoning is, I can remove any stone from a legal board state, and the remaining board state will still be legal. There are no backwards transitions from legal board states to illegal ones.

Be carefull, his "legitimate play" means alternate plays without passing. And it's clear that all legal board position can't be reached with legitimate plays (as opposed to legal plays, where players can pass).

This position can't be reached with legitimate plays :

Click Here To Show Diagram Code: [go]$$c "Illegitimate" but legal board position $$ --------------------------------------- $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . X . . . . . X . . . . . X . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . X . . . . . X . . . . . X . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . X . . . . . X . . . . . X . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ | . . . . . . . . . . . . . . . . . . . | $$ ---------------------------------------[/go]

moyoaji · Post by **moyoaji** » Fri May 30, 2014 5:56 pm

Tryss wrote:Be careful, his "legitimate play" means alternate plays without passing. And it's clear that all legal board position can't be reached with legitimate plays (as opposed to legal plays, where players can pass).

I didn't realize there was a distinction between legitimate and legal play. For one thing, legitimate and legal basically mean the same thing. For another, why is passing illegitimate? It's bad to do before the game is actually over, but it is a legal move at any time in any ruleset.

I have seen several amateur games with early passes in the endgame - sometimes justified, sometimes not. Are these games illegitimate and therefore not counted?

Dusk Eagle · Post by **Dusk Eagle** » Sat May 31, 2014 12:01 am

I think passing must be counted as legitimate to the question "How many board states can be reached by legal play?" You could however ask the question "How many board states can be reached from an empty board by legal play without either player passing?"

shapenaji · Post by **shapenaji** » Sat May 31, 2014 12:40 am

Dusk Eagle wrote:I think passing must be counted as legitimate to the question "How many board states can be reached by legal play?" You could however ask the question "How many board states can be reached from an empty board by legal play without either player passing?"

You could ask that question, I'm not sure it's useful. I don't see any reason why we would respect the inclusion of bad plays in our board states, but not include bad plays that are passes.

HermanHiddema · Post by **HermanHiddema** » Sat May 31, 2014 12:49 am

Shaddy wrote:You don't care about the actual second row, only whether or not each group on the current row has a liberty, so you can do it with 3^19 * 2^19 states (which is a pretty loose bound, since there's less than 19 groups on each row). It's still annoying to run, though, since it's too large for RAM on a home computer

Since we don't need to know whether an empty point has a liberty, we can simplify to 5 possible states for any point: empty, black with liberties, black without liberties, white with liberties, white without liberties. Then each line has a 5^19 upper bound.

Life In 19x19

Possible # of legal positions.

Re: Possible # of legal positions.

Re: Possible # of legal positions.

Re: Possible # of legal positions.

Re: Possible # of legal positions.

Re: Possible # of legal positions.

Re: Possible # of legal positions.

Re: Possible # of legal positions.

Re: Possible # of legal positions.

Re: Possible # of legal positions.

Re: Possible # of legal positions.

Re: Possible # of legal positions.

Re: Possible # of legal positions.

Re: Possible # of legal positions.

Re: Possible # of legal positions.

Re: Possible # of legal positions.