[gnugo-devel] Surround revisions

[Nando]

Following patch implements some large surround code revisions.

The main idea is to restrict the considered set of hostile enclosing
stones to those really involved in the surrounding of the goal dragon.
The implementation uses various algorythms to compute distances and
hostile stones are discarded from the mn array when a pair other
hostile ones can be found which makes the considered one useless.

O.X.O  In this example, the bottom O stone would get discarded.
.....
.O.O.
.....
..O..

Virtual enclosing points are generated at the edge for stones on the
second and third lines. This should account for the edge being a
natural barrier.

In order to compute distances between corners of the convex hull
a sorting by angle algorythm has been implemented. If the distance
between a pair enclosing stones is large, the surround status gets
decreased to WEAKLY_SURROUNDED, or even 0 for very large ones.

O.X.O
.....
.O.O.         This is "more" surrounded than ...

O.XXXXXX.O    ...this.
..........    In this example, the surround status would be lowered
.O......O.    to WEAKLY_SURROUNDED.


Finally, surrounding computations have been moved earlier in
make_dragons() in order to influence the computed escape route just
before the weakness evaluation. When a dragon is WEAKLY_SURROUNDED,
the escape_route is divided by 2. If the dragon is SURROUNDED,
escape_route is simply set to 0. Possibly, better tunings can be
found here.


Regressions breakage : 8 PASSes and 4 FAILs

trevora:130     PASS  Good, value of saving E4 gets increased.
nngs1:20        PASS  Not sure. Value of F17 gets increased because
                      D17 is thought to be weakly surrounded. In a
                      sense, it is not completely wrong...
nngs1:46        PASS  Bogus. G15 doesn't address the real issue.
nngs1:48        FAIL  This one passed recently with a patch I
                      submitted. I was wondering if it was accidental
                      or not. It seems it actually was.
trevor:412      PASS  Looks lucky.
trevor:1060     FAIL  Weird one. A new attack is found at E2 and GG
                      doesn't see the tactical defense H4 G3 F2 during
                      the owl reading, although it can find the
                      combination when asked directly
global:26       PASS  Good. (effect on C14)
13x13:65        PASS  Probably lucky.
nngs3:130       FAIL  I honestly don't know. N14 is big too, but GG
                      should not tenuki such attachments. A specific
                      pattern to solve this ?
safety:5        PASS  Good.
safety:7        PASS  Good.
ninestones:150  FAIL  GG is worried about D14, which is indeed
                      getting a bit surrounded.


Despite the apparently positive PASS/FAIL delta, the results are
actually not so great. On the other hand, the passes in safety.tst are
promising, so I'm rather confident that the patch is a good improvement.


/nando


- surround code revised
- surround status used to correct escape route in make_dragons()
- new utility function square_dist() in board.c

surround_3_15.1
Description: Text document