11

Are there any arrangements of stones that are:

  1. legal, because all groups have at least one liberty, yet
  2. impossible, because no sequence of moves could possibly result in such an arrangement.

I'm definitely not looking for illegal arrangements where a group exists without any liberties, like this:

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

(By the way, what I'm looking for is the same concept as a Garden of Eden in Conway's Game of Life.)

Joe
  • 3,465
  • 20
  • 49
  • That's an interesting questions. A kind of introduction to retrograde analysis. I've done some chess retrograde analysis puzzles in the past and the general idea of many is that the position, although legal, is impossible. But go retrograde analysis would be a lot harder due to a vast number of possible moves. My guess is that there's no impossible position in go but I'll think about it. – Heimdall Jan 22 '17 at 13:27
  • Is "pass" loads of times allowed? If not, the position could consist of a long black wall on one side and a short white wall on the other side of the board. – Heimdall Jan 22 '17 at 13:30
  • 1
    By arrangement, do you mean just what's on the board or also the captured stone counter? If the latter, then the answer would be one white wall and one black wall (or sufficiently isolated stones) and at least one captured stone for an impossible position. – Heimdall Jan 22 '17 at 13:34

2 Answers2

7

Assuming you're only interested in what's on the board and passes are allowed.

I would go backwards then: what was the position just before?

It's quite easy to see that if you remove any stone of any colour from a legal position, it will still be legal.

So in deciding what was the last move, pick any stone of the player whose turn just ended and assume that that stone was placed without any capturing.

If the number of black and white stones is too different, include a sufficient number of passes for one player.

In other words, the way to get to a given position, the players just have to place their stones (in any order) to where we want them to be and nowhere else (with a certain number of passes if necessary). No capturing will happen then.

Heimdall
  • 202
  • 1
  • 4
  • This is a great strategy for finding the sort of arrangement, but unfortunately it doesn't answer the question of whether or not such an arrangement can exist. – Thunderforge Jan 23 '17 at 05:41
  • 1
    @Thunderforge: No, this is a sketch of proof that such kind of position cannot exist in Go (with passes allowed, as under standard Japanese rules). – Sir Cornflakes Jan 24 '17 at 12:58
  • That's right, @jknappen, it demonstrates that any legal position can be constructed as a (rather ridiculous) play. – Heimdall Jan 25 '17 at 19:11
3

I do not believe that there are any arrangements that strictly meet your requirements. Given that the rules are so simple I cannot imagine an arrangement that could not be reached by selective application of the rules (see here for more on rules).

In particular it's because there are few options, with few restrictions. Each player must either pass, or place a stone. There are no restrictions on when a player may pass, and the only relevant requirement for placing a stone is the one you mentioned: it must have a liberty as the turn resolves. This means that if the purpose of the "game" is to create a specific arrangement then two players cooperating could create any board state.

However, there are many arrangements that could not arise without cooperation between the players, and would not arise in a regular game.

BBS
  • 231
  • 1
  • 3