visualizing valid and invalid go states

[tj86430]

In go, black and white stones are placed alternately and once placed, not moved unless removed by capture.

What about passing?

$$
$$+---+
$$|...|
$$|...|
$$|.1.|
$$+---+

Click Here To Show Diagram Code

[go]$$
$$+---+
$$|...|
$$|...|
$$|.1.|
$$+---+[/go]

White passes

$$
$$+---+
$$|3..|
$$|...|
$$|.X.|
$$+---+

Click Here To Show Diagram Code

[go]$$
$$+---+
$$|3..|
$$|...|
$$|.X.|
$$+---+[/go]

White passes

$$
$$+---+
$$|X.6|
$$|75.|
$$|.X.|
$$+---+

Click Here To Show Diagram Code

[go]$$
$$+---+
$$|X.6|
$$|75.|
$$|.X.|
$$+---+[/go]

[Mike Novack]

passing -- good point.

[HermanHiddema]

Question:

Assuming the original definition of legal state (all groups have at least one liberty) there is a question of "reachable" states. Take this example:

$$
$$+---+
$$|X.O|
$$|XX.|
$$|.X.|
$$+---+

Click Here To Show Diagram Code

[go]$$
$$+---+
$$|X.O|
$$|XX.|
$$|.X.|
$$+---+[/go]

In go, black and white stones are placed alternately and once placed, not moved unless removed by capture. Only one white stone could have been captured (the number of black stones placed on the board can never be less than the number of white stones placed) so there are too few white stones present in the diagram.

So that would be a legal state but not a reachable legal state?

$$B :w8: at :b1:, :w10: at :b1:
$$+---+
$$|921|
$$|734|
$$|.56|
$$+---+

Click Here To Show Diagram Code

[go]$$B :w8: at :b1:, :w10: at :b1:
$$+---+
$$|921|
$$|734|
$$|.56|
$$+---+[/go]

(but of course there exist actual unreachable positions)

[uPWarrior]

(but of course there exist actual unreachable positions)

Such as? This doesn't seem obvious to me at all. I think we can construct arbitrarily long sequences of capturing and under-the-stones tesujis to create any (valid) board state we want. Even a single white stone, assuming black started and never passed, is possible.

[HermanHiddema]

(but of course there exist actual unreachable positions)

Such as? This doesn't seem obvious to me at all. I think we can construct arbitrarily long sequences of capturing and under-the-stones tesujis to create any (valid) board state we want. Even a single white stone, assuming black started and never passed, is possible.

$$
$$+---+
$$|..X|
$$|...|
$$|X..|
$$+---+

Click Here To Show Diagram Code

[go]$$
$$+---+
$$|..X|
$$|...|
$$|X..|
$$+---+[/go]

[skydyr]

(but of course there exist actual unreachable positions)

Such as? This doesn't seem obvious to me at all. I think we can construct arbitrarily long sequences of capturing and under-the-stones tesujis to create any (valid) board state we want. Even a single white stone, assuming black started and never passed, is possible.

$$
$$+---+
$$|..X|
$$|...|
$$|X..|
$$+---+

Click Here To Show Diagram Code

[go]$$
$$+---+
$$|..X|
$$|...|
$$|X..|
$$+---+[/go]

Oh, that's a handicap game.

[uPWarrior]

(but of course there exist actual unreachable positions)

Such as? This doesn't seem obvious to me at all. I think we can construct arbitrarily long sequences of capturing and under-the-stones tesujis to create any (valid) board state we want. Even a single white stone, assuming black started and never passed, is possible.

$$
$$+---+
$$|..X|
$$|...|
$$|X..|
$$+---+

Click Here To Show Diagram Code

[go]$$
$$+---+
$$|..X|
$$|...|
$$|X..|
$$+---+[/go]

Great. The negative has 2 eyes.

[dohduhdah]

$$
$$+---+
$$|..X|
$$|...|
$$|X..|
$$+---+

Click Here To Show Diagram Code

[go]$$
$$+---+
$$|..X|
$$|...|
$$|X..|
$$+---+[/go]

I don't see how there are states that are unreachable, except under certain assumptions
(like players not doing weird things like filling up their own eyes, which would usually
be unreasonable given the goal of the game).

For the concept of theoretical games, where the only assumption is that both sides play
in accordance with the rules, any valid state can obviously be reached.

[dohduhdah]

Question:

Assuming the original definition of legal state (all groups have at least one liberty) there is a question of "reachable" states. Take this example:

$$
$$+---+
$$|X.O|
$$|XX.|
$$|.X.|
$$+---+

Click Here To Show Diagram Code

[go]$$
$$+---+
$$|X.O|
$$|XX.|
$$|.X.|
$$+---+[/go]

In go, black and white stones are placed alternately and once placed, not moved unless removed by capture. Only one white stone could have been captured (the number of black stones placed on the board can never be less than the number of white stones placed) so there are too few white stones present in the diagram.

So that would be a legal state but not a reachable legal state?

There are no unreachable legal states, unless you're willing to impose certain assumptions on the
behavior of the players, like acting in accordance with the goal of the game and not just playing
moves that are allowed according to the rules.
For instance, it would be allowed for one player to keep passing from the start as the other player
keeps playing moves until they feel they have enough stones on the goban that the opponent will no
longer be able to create any living groups.
It would be a nonsensical game, but it's still a valid game, as both players play valid moves.

[skydyr]

There are no unreachable legal states, unless you're willing to impose certain assumptions on the
behavior of the players, like acting in accordance with the goal of the game and not just playing
moves that are allowed according to the rules.
For instance, it would be allowed for one player to keep passing from the start as the other player
keeps playing moves until they feel they have enough stones on the goban that the opponent will no
longer be able to create any living groups.
It would be a nonsensical game, but it's still a valid game, as both players play valid moves.

I think one takeaway from this is that it exposes how much and aggressively we as humans prune the game tree when evaluating moves and positions. Presumably, as we get stronger, we do it even more. This is demonstrated both by beginning players who worry that their position might collapse if their opponent plays at A, B, and C, as well as by professionals who overlook a sequence that completely destroys their opponent in a game because it requires an unforced empty triangle, or similar "bad" moves.

[HermanHiddema]

I don't see how there are states that are unreachable, except under certain assumptions
(like players not doing weird things like filling up their own eyes, which would usually
be unreasonable given the goal of the game).

For the concept of theoretical games, where the only assumption is that both sides play
in accordance with the rules, any valid state can obviously be reached.

The assumption here, as introduced by Mike, is no passes.

There is no reason to apply such a restriction, other than as a theoretical thought experiment, but since the whole thread is very much about theory, it was an interesting tangent.

With passes, any state can obviously be reached.

[dohduhdah]

I've created a new version:

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

Hopefully that clarifies the relationship between the pattern:

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

and valid states (legal positions):

http://i.imgur.com/4Xev8VV.jpg

That last graphic comes from a paper on the combinatorics of go:
http://homepages.cwi.nl/~tromp/go/gostate.ps


https://www.usgo.org/files/bh_library/Tromp.pdf
http://homepages.cwi.nl/~tromp/go/legal.html

[tj86430]

I've created a new version:

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

Now this is a great picture. Before, I was too busy (read: lazy) to try to figure out what your diagrams are actually all about, while this shows it very clearly with (almost) one glance.