Re: [gnugo-devel] readconnect patch

[Gunnar Farneback]

Tristan wrote:
>    A B C D E F G H J K L M N O P Q R S T
> 19 . . . . . . 7 6 8 9 . . . . . . . . . 19
> 18 . . . . . . 5 4 X 3 . . . . . . . . . 18
> 17 . . . . O . X 1 O X . O . . . . . . . 17
> 16 . . . + . . . . 2 + . . . . . X . . . 16
> 15 . . . . O . . . . . . O . . . . . . . 15
> 14 . . . . . . . . . . . . . . . . . . . 14
> 13 . . . . O . O . O . O . . . . . . . . 13
> 
> You have to recall the intersections involved in this "ladder"
> and try them in the global search.
> 
> In my jargon this ladder is a gi51111 one (5 forced moves of depth
> one involved (=ip1) moves).
> 
> The most complex position in the search is this one:
> 
>    A B C D E F G H J K L M N O P Q R S T
> 19 . . . . . . . . . . . . . . . . . . . 19
> 18 . . . . . X O X X O X . . . . . . . . 18
> 17 . . . . O . X O O X . O . . . . . . . 17
> 16 . . . + . . . . . + . . . . . X . . . 16
> 15 . . . . O . . . . . . O . . . . . . . 15
> 14 . . . . . . . . . . . . . . . . . . . 14
> 13 . . . . O . O . O . O . . . . . . . . 13
> 
> If you want more details, maybe a good thing is to read the
> following paper:
> 
> http://www.ai.univ-paris8.fr/~cazenave/TheoremProvingInGo.pdf
> 
> The ip51111 is described in this other one (in french... wait a little
> for the english version for another game...) 

I don't think I understand this fully. Please correct me where I go
wrong in the explanation below of why test case connect:2 fails.

----

The test case is for white to try to disconnect a black two space jump
on the third line. The correct answer is that it can't be
disconnected, but GNU Go from current CVS says that it is disconnected
as it stands.

According to the reasoning above this is an ip5 game (or is it ip6?)
for white.

In recursive_disconnect() the following code can be found:

  Moves[0] = 0;
  if (prevent_connection_one_move(Moves, str1, str2))
    res = 0;
  else if (prevent_connection_two_moves(Moves, str1, str2))
    res = 0;
  else if (prevent_simple_connection_three_moves(Moves, str1, str2))
    res = 0;

The three called functions try, according to the recently added
comments, to detect ip1, ip2, and (a special case of) ip3 games. If
all of them return false, the conclusion is that the position is
disconnected as it stands.

Thus, in order to solve test case 2, it's necessary to add functions
prevent_simple_connection_four_moves() and
prevent_simple_connection_five_moves().

----

If this is correct, I'm starting to get worried about the required
code complexity, since I don't see why ip5 should be the limit.

Consider this example, black to disconnect the two white strings on
the second line:

|..O......
|.OOX.....
|.OXX.....
|.XOX.....
|.XOOO....
|.XOXXX...
|.OXX.....
|.OOO.....
|.........

If I understand the terminology (and read) correctly this would be an
ipN game, where N is something large. Black's only chance to
disconnect is to capture the five white stones in the middle in one of
the available ladders. The five white stones can of course also be
captured in a net, but then white can link up along the edge. Even if
black has a lot of support outside the displayed region, it seems like
N must be at least 12 or 13. For a ladder crossing the entire board it
would be much larger.

Now this isn't entirely similar to test case connect:2, but it becomes
closer if we change it to

|..O......
|.OOX.....
|.OXX.....
|.XOX.....
|.XOO.....
|.XOXXX...
|.OXX.....
|.OOO.....
|.........

where white to connect is an ipN game for some big N.

I guess I'm missing something, or is this just a too difficult
position?

/Gunnar