Re: [gnugo-devel] readconnect patch

[Tristan Cazenave]

Hi,

The idea is to use Abstract Proof Search and further improvements I
made to it so as to read connections.
One property of the algorithm is that when it finds a connection it
has proven the connection, and you can be confident that the
connection works.
Using this algorithm has proven much more fast than usual alpha beta.
The position you are referring to is maybe the most difficult in
connect.tst.

   A B C D E F G H J K L M N O P Q R S T
19 . . . . . . . . . . . . . . . . . . . 19
18 . . . . . . . . X . . . . . . . . . . 18
17 . . . . O . X . O X . O . . . . . . . 17
16 . . . + . . . . . + . . . . . X . . . 16
15 . . . . O . . . . . . O . . . . . . . 15
14 . . . . . . . . . . . . . . . . . . . 14
13 . . . . O . O . O . O . . . . . . . . 13

I think the best way to handle it is to pay X at J18.
Then you have to prove the connection is possible if
X plays first, and recall the intersections involved
in the proof, and try them in order to try to
disconnect O.
Here the sequence is obvious and is a "connection ladder"
consisting of forced moves of depth one :

   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...) 


http://www.ai.univ-paris8.fr/~cazenave/AGPS-RFIA.pdf

So next things to do are to implement the functions that detects the
connection is possible in three moves by the same player, then to
memorize the intersections involved in a search so as to try them
as moves (relevancy zones), and finally to reimplement the gradual
games (ip51111, and some other).

I am currently working on my life and death engine as it is in need
of improvement, I will come back to readconnect after...

Tristan.

> I'm slowly starting to find my way around the readconnect code. I have
> a fairly good idea how to add testing of additional connecting moves.
> What's still a mystery to me is how to fix disconnect mistakes in e.g.
> the basic position in test case 2 of connect.tst. I'm just getting
> lost in the maze of calls
> 
> recursive_disconnect() ->
> prevent_connection_two_moves() ->
> connection_two_moves() ->
> connected_one_move() ->
> connection_one_move()
> 
> and similar. Returning to connect:2, the problem is to try to
> disconnect the two space jump on the third line between G17 and K17.
> 
> 
> What basically happens is that it first tries to determine whether X
> can connect the two stones at all. This involves trying the moves
> X H17 (generated by connection_two_moves())
> O J17 (generated by connected_one_move())
> to get to the position
> 
>    A B C D E F G H J K L M N O P Q R S T
> 19 . . . . . . . . . . . . . . . . . . . 19
> 18 . . . . . . . . . . . . . . . . . . . 18
> 17 . . . . O . X X O X . O . . . . . . . 17
> 16 . . . + . . . . . + . . . . . X . . . 16
> 15 . . . . O . . . . . . O . . . . . . . 15
> 14 . . . . . . . . . . . . . . . . . . . 14
> 13 . . . . O . O . O . O . . . . . . . . 13
> 
> and then connection_one_move() says "no, no connection" and the
> variation is disregarded. After trying the symmetric moves X J17 and O
> H17 with the same result it gives up and says "G17 and K17 are
> disconnected as it stands". Clearly something goes wrong here but I
> don't know how to deal with it. One can notice that
> recursive_connect() manages to find a connection, but this involves
> other code than the functionns called from recursive_disconnect().
> 
> Tristan, could you try to explain the overall structure of the code?
> Which function needs to be improved/bugfixed to solve the mistake
> above?
>