Possible # of legal positions.

shapenaji · **#21**

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 · **#22**

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 · **#23**

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 · **#24**

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 · **#25**

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 · **#26**

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 · **#27**

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 · **#28**

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 · **#29**

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 · **#30**

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.

Bill Spight · **#31**

shapenaji wrote:

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.

Who say that a pass is a play? Ing and Tromp and the AGA, to be sure. But traditionally I don't think that it was, by Chinese, Japanese, or Korean rules.

leichtloeslich · **#32**

You're still missing connection information for stones without liberties:

Click Here To Show Diagram Code: [go]$$B $$ +---------+ $$ | X X . . | $$ | X O . . | $$ | X X . . | $$ +---------+[/go]

The two black stones in the second strip are actually connected, so to make a legal position only one of them needs to get a liberty in one of the following strips.

Anyway, all of this sounds very much like the beginning of that "Combinatorics of Go" paper. Has anybody here read it?

They call it "border state" instead of strip and it's slightly more general. (I think what you call a strip, they call an "edge state".)

In that paper they use a bit of graph theory and linear algebra to derive linear recurrences for the counting function. Interesting stuff.

It can be downloaded from John Tromp's site directly here. (If you have trouble with the link provided earlier.)

xed_over · **#33**

Tryss wrote:

Be carefull, his "legitimate play" means alternate plays without passing.

actually, that thought hadn't crossed my mind yet, but now that you mention it...

shapenaji · **#34**

leichtloeslich wrote:

You're still missing connection information for stones without liberties:

Click Here To Show Diagram Code: [go]$$B $$ +---------+ $$ | X X . . | $$ | X O . . | $$ | X X . . | $$ +---------+[/go]

The two black stones in the second strip are actually connected, so to make a legal position only one of them needs to get a liberty in one of the following strips.

Anyway, all of this sounds very much like the beginning of that "Combinatorics of Go" paper. Has anybody here read it?

They call it "border state" instead of strip and it's slightly more general. (I think what you call a strip, they call an "edge state".)

In that paper they use a bit of graph theory and linear algebra to derive linear recurrences for the counting function. Interesting stuff.

It can be downloaded from John Tromp's site directly here. (If you have trouble with the link provided earlier.)

Nice! I haven't read it, I'll dig in.

But off the top of my head, keeping track of cycles is going to add an additional storage multiplier of 19^19 (each one is connected to one of the other 18, or to none at all)

shapenaji · **#35**

Bill Spight wrote:

Who say that a pass is a play? Ing and Tromp and the AGA, to be sure. But traditionally I don't think that it was, by Chinese, Japanese, or Korean rules.

I dunno, Surely there were a few showboaters in Japan, China, or Korea that offered their opponent a handicap by repeatedly passing. Or simply passed to show that they were ahead, to induce their opponent to resign.

shapenaji · **#36**

Summarizing:

In bits, to store a useful strip on boardsize "X"

we need 5*X bits for the cycle info,
we need 1*X bits for if the end of a row is open
we need 2*X bits for color info
(I realize that Herman pointed out that you can store the latter two together, but it's still 3 bits, the cycle info might also have a simplification)

so each "useful" strip will be X bytes

---------------------------------------

There are ~ (19^19)*(5^19) ~= 10^37.6 possible strips

---------------------------------------

Now my assumption here is that (with the updates) we have stored enough information that any two strips can be combined to form an existing strip in the database.

This means that we would need a relational database containing 10^75 entries. Let's call it small_matrix

Each strip is related to the strips it can become, with the entry being the number of ways it can reach each of these strips (branching factor)

Then the sum of the upper triangular portion in (smaller_matrix)^19 (a special routine would be required for the last row, but this is approximate), should give us the total number of board states.

However, seeing as this calculation requires me to store 19*10^75 bytes of data, I think I can safely say that this method won't be particularly useful.

uPWarrior · **#37**

Has anyone proven this problem to be NP-hard?

moboy78 · **#38**

DrStraw wrote:

moboy78 wrote:

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

If I'm looking at your attachment correctly, then wouldn't that just be a 2x2 with a stone in between intersections?

Possible # of legal positions.

Who is online