[gnugo-devel] Alternate connections.

[Gunnar Farneback]

GNU Go 3.1.23 introduced a new configure option
--enable-alternate-connections, at the time having absolutely no
effect. This will change with the patch

http://www.lysator.liu.se/~gunnar/gnugo/patches/gunnar_1_24.2

which adds an alternative connection reading algorithm at the end (or
rather second half) of readconnect.c. To switch between the two
implementations you can also use the runtime option
--alternate-connections, which toggles to the one not chosen as
default at build time.

At the top level the alternative algorithm is identical to Tristan's
with mutual recursion between two functions recursive_connect2() and
recursive_disconnect2(). Also similar is that both these functions
first generate a number of moves and then runs a loop to try them and
mutually recurse.

What differs is the move generation. Where Tristan has a number of
functions to find moves to connect or disconnect within a specific
number of moves, my algorithm has one single find_connection_moves()
function, which tries to identify moves having effect on the minimum
connection distance between the strings. This is done with the help of
the function compute_connection_distances(), which computes distance
and delta (impact) values around each string. For further information,
read the comments and the code itself in the patch.

Both these functions are very ad hoc heuristics, but they seem to be
doing a reasonable job. With alternate connections we get the
following regression results for connect.tst and connection.tst:

./regress.sh . connect.tst
2 unexpected PASS!
16 unexpected PASS!
25 unexpected PASS!
29 unexpected PASS!
35 unexpected PASS!
36 unexpected PASS!
37 unexpected PASS!
57 unexpected FAIL: Correct '1 (D5|C6)', got '1 C5'
70 unexpected PASS!
78 unexpected PASS!
81 unexpected PASS!
./regress.sh . connection.tst
26 unexpected PASS!
27 unexpected PASS!
30 unexpected PASS!
31 unexpected PASS!
32 unexpected PASS!
35 unexpected PASS!
36 unexpected PASS!
37 unexpected PASS!
38 unexpected PASS!
39 unexpected PASS!
42 unexpected PASS!
45 unexpected PASS!
46 unexpected PASS!
47 unexpected PASS!
48 unexpected PASS!
51 unexpected PASS!
53 unexpected PASS!
60 unexpected PASS!
63 unexpected PASS!
73 unexpected PASS!
74 unexpected PASS!

The major weakness currently is the speed. In many positions it is on
par with Tristan's algorithm and generally acceptable but in certain
positions this algorithm is much slower. The accuracy can also be
improved, but I think it's already good enough for serious experiments
in the rest of the engine to be meaningful. More connection test cases
would be very welcome.

Tristan wrote:
> It is worth trying and comparing the two approaches. Moreover some
> of the code you will write, for example the distance code can also
> prove useful in my architecture.

I absolutely agree. The challenge now is to get at least one and if
possible two algorithms which are both fast and accurate enough,
although not necessarily with exactly the same tradeoffs. Feel free to
pick up any useful ideas you can find. You're code has already
influenced mine quite a bit.

> Maybe we can have a variable that switches the move generation, and
> then compare both approaches easily.

Yes, the --alternate-connections option does just this.

> I follow this approach because It worked well in my capture
> search, but maybe connection is a different story.

My approach is structurally rather similar to the tactical reading in
GNU Go, which also works well. So in this respect there is no
difference. :-)

/Gunnar