visualizing valid and invalid go states

[dohduhdah]

We can consider a go state as a combination of two bitstrings, where the length of
of those bitstrings is equal to the number of locations on the goban.

So for instance, on a 2x2 goban, there are 4 locations and hence 2^4=16 possible
patterns of stones of one color and on a 3x3 goban, there are 9 locations and
hence 2^9=512 possible patterns of stones of one color.

A combination of two bitstrings of length N is equivalent to a bitstring of
length 2N and amongst those, there are 3^N possible combinations of two mutually
exclusive bitstrings of length N.

Since in any location there can be either a white stone, or a black stone, but
not both, we can see that the number of possible go states
is 3^N, embedded in (2^N)(2^N) = 2^(2N) possible combinations of two
bitstrings of length N, where N is the number of locations on the goban.

So, on a 2x2 goban, there are 3^4 = 81 possible patterns of stones
of two colors, embedded in a spectrum of 256=(2^4)(2^4)=(2^8) possible
combinations of two patterns of stones of one color.
On a 3x3 goban, there are 3^9=19683 possible patterns of stones of two colors,
embedded in a spectrum of 262144=(2^9)(2^9)=(2^18) possible combinations of
two patterns of stones of one color.

A valid go state is one where there are no stones or chains that lack
liberties.
On a 2x2 goban, there are 24 invalid go states and 57 valid go states (24+57=81).
This can be visualized as follows (white stones represent valid states and black
stones invalid states):

http://i.imgur.com/CucxhXS.jpg

To illustrate the way bitstrings are combined, here is a version
that includes an index of the complete spectrum of all possible bitstrings
(in this case of length 4) for both dimensions:

http://i.imgur.com/iDlDKfL.jpg


On a 3x3 goban, there are 7008 invalid go states and 12675 valid go states (7008+12675=19683).
This can be visualized in multiple ways, depending on how the locations on the goban are mapped
to positions of bits in the bitstring:

014
235
678

http://i.imgur.com/b3YmbLD.jpg

012
345
678

http://i.imgur.com/is5PAGW.jpg

[EdLee]

Because of the symmetries, do you want to divide by 4 ?

( Of course, because of the huge number at 19x19,
dividing by 4 is insignificant because it's still on the same order of magnitude. )

[dohduhdah]

Because of the symmetries, do you want to divide by 4 ?

( Of course, because of the huge number at 19x19,
dividing by 4 is insignificant because it's still on the same order of magnitude. )

Well, most patterns occur in 16 variations (if we include variations obtained by reflections, rotations
and interchanging colors).

[Mike Novack]

Are you sure about the number of possible legal states for an intersection?

I can see at least four.
a) has a black stone
b) has a white stone
c) has no stone and may be played upon by either side
d) has no stone but may not be played upon by the side having the move (the result of a ko capture).

There are of course other possible ways of encoding the latter so as not to require a state for each intersection and that might save significant space. But space and time often trade off and there might be major (time) advantages for keeping the number of states a power of two.

[dohduhdah]

Are you sure about the number of possible legal states for an intersection?

I can see at least four.
a) has a black stone
b) has a white stone
c) has no stone and may be played upon by either side
d) has no stone but may not be played upon by the side having the move (the result of a ko capture).

There are of course other possible ways of encoding the latter so as not to require a state for each intersection and that might save significant space. But space and time often trade off and there might be major (time) advantages for keeping the number of states a power of two.

Well, the numbers I get with my prolog program that differentiates between valid and invalid
states corresponds to the numbers found in online info (though I only checked for the 2x2 and 3x3
cases):

http://en.wikipedia.org/wiki/Go_and_mathematics
http://senseis.xmp.net/?NumberOfPossibleOutcomesOfAGame

I think (super)ko is a concept at the level of sequences of states rather than individual states,
because it involves excluding repetition in any sequence of states (like a sequence of states
that might occur from a given state as both sides play valid moves).
So this can be excluded from consideration when dealing with individual states, just like the side
which is to move is left out of consideration.

For any given individual state, we can consider it in the context of information like where this
state occured in a tree of possible game progressions, which dictates additional aspects like which
side is to move and which empty spots can't be played because of the (super)ko rule to avoid
repetition in the sequence of states from the root of the game tree to the given state.

[RBerenguel]

Are you sure about the number of possible legal states for an intersection?

I can see at least four.
a) has a black stone
b) has a white stone
c) has no stone and may be played upon by either side
d) has no stone but may not be played upon by the side having the move (the result of a ko capture).

There are of course other possible ways of encoding the latter so as not to require a state for each intersection and that might save significant space. But space and time often trade off and there might be major (time) advantages for keeping the number of states a power of two.

Well, the numbers I get with my prolog program that differentiates between valid and invalid
states corresponds to the numbers found in online info (though I only checked for the 2x2 and 3x3
cases):

http://en.wikipedia.org/wiki/Go_and_mathematics
http://senseis.xmp.net/?NumberOfPossibleOutcomesOfAGame

I think (super)ko is a concept at the level of sequences of states rather than individual states,
because it involves excluding repetition in any sequence of states (like a sequence of states
that might occur from a given state as both sides play valid moves).
So this can be excluded from consideration when dealing with individual states, just like the side
which is to move is left out of consideration.

For any given individual state, we can consider it in the context of information like where this
state occured in a tree of possible game progressions, which dictates additional aspects like which
side is to move and which empty spots can't be played because of the (super)ko rule to avoid
repetition in the sequence of states from the root of the game tree to the given state.

Oh, I'd love to see the code! I like Prolog, but rarely find any use for it in my day-to-day or even mildly for-fun activities

[dohduhdah]

http://i.imgur.com/qRsWI54.jpg

This is a version for a 2x2x2 goban (3 dimensional), where there are 3^8 = 6561 possible states
(embedded in 256^2=65536 possible combinations of two bitstrings of length 8).
Of those, 1288 are invalid and 5273 valid.

[dohduhdah]

Oh, I'd love to see the code! I like Prolog, but rarely find any use for it in my day-to-day or even mildly for-fun activities

http://pastebin.com/QHuWrjsG

Various libraries of SICStus prolog 3.8.4 are used (system, lists, random, ordsets).

The code is a bit of a hack of code I had created earlier to visualize prime numbers and the Moebius function:

http://commons.wikimedia.org/wiki/Categ ... oebius.jpg

It presupposes having a folder at "d:\prog\go" and having 6 (small) square jpg files there:

0.jpg = empty - middle
1.jpg = black stone
2.jpg = white stone
3.jpg = empty - lower right corner
4.jpg = empty - bottom side
5.jpg = empty - right side

You could save and rename these files:
http://i.imgur.com/UGEp3Ht.jpg
http://i.imgur.com/aK3Em8j.jpg
http://i.imgur.com/MALazOK.jpg
http://i.imgur.com/Q2uZ3HS.jpg
http://i.imgur.com/kYlhWAu.jpg
http://i.imgur.com/BGaD5Ly.jpg


Those images are composed using imagemagick (which is supposed to be installed for it to work), via
the 'montage' commandline utility.

http://www.imagemagick.org/

[RBerenguel]

Phew, quite a lot of rules in there, I'd need to take my time. Also lots of cuts, I hope they are green

Edit: All of my prolog code, ever was hacky, by the way (and most of any of my code...)

[dohduhdah]

Phew, quite a lot of rules in there, I'd need to take my time. Also lots of cuts, I hope they are green

Edit: All of my prolog code, ever was hacky, by the way (and most of any of my code...)

Well, not all code is used, some are utility predicates for prototyping and checking.
Some code may also be left over from the original code where I extracted sections that could be
used for how the image is built recursively from smaller pieces.

Sorry about the sparing commenting in the code and I'm sure it's suboptimal, because I don't
code very frequently.

To quickly check the number of invalid states, you can simply do something like:

generatex2(8, X)? X=24

generatex2(18, X)? X=7008

http://i.imgur.com/py9y9Q0.png

[RBerenguel]

No need to apologise. I code very frequently and comment sparingly and have a lot of funky spaghetti most of the time. All I care about is if it works, if it does, it's fine by now. If it is code I need to reuse or anything I try to improve and comment, but every time I've tried to make it a priority, getting to "works relatively ok" took 10 times as much

[Mike Novack]

I was referring to ordinary ko (whether a ko state exists and if so, for black or for white, is part of the state of the board).

I intentionally mentioned this in terms of information for each intersection but because only one intersection at a time can have a ko state this information might better be stored (for boards up to 22*22) as 11 bits, 2 bits for doesn't exist, exists for black, exists for white and then 9 to specify the intersection.

I am referring to bits because you began with "what is the minimal bitstring". Practical considerations like language and what space/time tradeoffs might be wise depending on how to be processed another matter entirely.

[dohduhdah]

I was referring to ordinary ko (whether a ko state exists and if so, for black or for white, is part of the state of the board).

I intentionally mentioned this in terms of information for each intersection but because only one intersection at a time can have a ko state this information might better be stored (for boards up to 22*22) as 11 bits, 2 bits for doesn't exist, exists for black, exists for white and then 9 to specify the intersection.

I am referring to bits because you began with "what is the minimal bitstring". Practical considerations like language and what space/time tradeoffs might be wise depending on how to be processed another matter entirely.

No, that's my point.. it's *not* part of the state of the board. You don't need to store it in the state of the board,
because it follows from the sequence of states that occurred previously whether or not there is a ko situation.

Also, I'm not talking about a minimal bitstring. I'm just saying that a bitstring is all you need for the pattern of stones of
one color. Since there are only two colors involved, a combination of two bitstrings can be used in a very straightforward way
to encode both patterns. It's not intended as a minimal way to encode states, just a very intuitive way as there is a
very straightforward correspondence between the pattern of stones and the bitstring encoding that pattern of stones.

[Mike Novack]

No, that's my point.. it's *not* part of the state of the board. You don't need to store it in the state of the board,
because it follows from the sequence of states that occurred previously whether or not there is a ko situation.

We are maybe not speaking the same "language"?

If you are willing to consider "the state of the board" to include information from the previous states of the board then it could take (for example)only 10 bits! (nine to specify intersection and one to specify if a black or white stone) for this move << since the current move plus all the previous moves specify the current state of the board >>

The sense in which I am using the term "state of the board" would not require any additional information about how arrived at that state. Equivalent to "state of a go game".

[dohduhdah]

No, that's my point.. it's *not* part of the state of the board. You don't need to store it in the state of the board,
because it follows from the sequence of states that occurred previously whether or not there is a ko situation.

We are maybe not speaking the same "language"?

If you are willing to consider "the state of the board" to include information from the previous states of the board then it could take (for example)only 10 bits! (nine to specify intersection and one to specify if a black or white stone) for this move << since the current move plus all the previous moves specify the current state of the board >>

The sense in which I am using the term "state of the board" would not require any additional information about how arrived at that state. Equivalent to "state of a go game".

But how many bits are required to store states is completely irrelevant in the context of this discussion.
My only goal is to visualize the proportion of valid to invalid states and for that purpose, ko is irrelevant.

I'm talking about categorically valid/invalid go states, where this concept of validity is independent of the
context in which the state occurs. The fact that certain valid states can still be invalid in the context of a particular
game because of the ko or superko rule, doesn't detract from the utility of a categorical concept of validity of a go state,
defined strictly in terms of what patterns of stones are involved.

The kind of valid go states I'm talking about are the ones that KGS lets you create when you set up a board position via edit
in a custom game.

http://i.imgur.com/dSMQTqd.png

For instance, it allows me to create a valid state like this:
http://i.imgur.com/PpBBhtx.png

but not an invalid state like this:
http://i.imgur.com/peIDBbw.png