Possible # of legal positions.

[Bill Spight]

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]

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

$$B
$$ +---------+
$$ | X X . . |
$$ | X O . . |
$$ | X X . . |
$$ +---------+

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]

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]

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

$$B
$$ +---------+
$$ | X X . . |
$$ | X O . . |
$$ | X X . . |
$$ +---------+

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]

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]

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]

Has anyone proven this problem to be NP-hard?

[moboy78]

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?