[gnugo-devel] half and false eyes

[Paul Pogonyshev]

while working on the problem of badly connected dragons (see owl1.tst,
270 - 276), i found it to be closely related to half eyes. so, i'd
like to move search for half and false eyes to a separate function.
currently there are two places where such search occur: in
make_dragons() and owl_determine_life(). in make_dragons() there's a
FIXME: 

   * FIXME: Consolidate this piece of code with the very similar one
   * in owl_determine_life().

i'm planning to add a function called find_half_eyes() into optics.c
module. there's one difference in two pieces of code, which makes me
uncertain though.

in owl.c, when we find a false eye (which is treated the same as a
false margin), we reevaluate all its diagonal neighbours. this is
never done in dragon.c.

reason for reevaluation is in the evaluate_diagonal_intersection()
function.

    |.XXXX...     in this position vertex a is a half eye. to
    |.OOOX...     determine this, we must evaluate vertex b to
    |O..OX...     1.0 although it is in own eyespace. so, we
    |aOO.X...     don't evaluate vertice in own eyespace to 0.0
    |Ob.XX...     if they have two marginal neighbours.
    |..O.X...
    |.X..X...
    |..XXX...

however, i can't imagine a position where reevalution is really needed
after finding a false eye. consider this modification:

    |.XXXX...     this time vertex a is a solid eye although vertex
    |.OOOX...     b still has two marginal vertice (one real and one
    |O..OX...     false eye).
    |aOOXX...
    |ObcOX...
    |..OXX...
    |.X..X...
    |..XXX...

the funniest thing is that reevaluation does *not* work as intended.
in the second example we see that after discovering a false eye at c,
it is point a which needs to be reevaluated. code in owl.c reevaluates
eyes which are diagonal neighbours of a false eye, while they are
direct neighbours and eyes at knight move distance which might need
reevaluation.

so, i think that such reevaluation doesn't work in its current
implementation and, more than that, it is not needed at all. however,
i can't say that i'm certain about all these reasonings.

can anybody apply the patch below (it removes reevaluation) and run
gnugo through regression tests? i'm having hard times running perl
scripts under windows ;)

if the patch doesn't make any difference in regression, i will know
how to write find_half_eyes().

Paul


Index: gnugo/engine/owl.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/owl.c,v
retrieving revision 1.102
diff -u -r1.102 owl.c
--- gnugo/engine/owl.c  10 Sep 2002 20:17:27 -0000      1.102
+++ gnugo/engine/owl.c  14 Sep 2002 18:46:43 -0000
@@ -2392,28 +2392,11 @@
        
        if (sum >= 4.0) {
          /* False eye. */
-         int previously_marginal = eye[pos].marginal;
          owl->half_eye[pos].type = FALSE_EYE;
          if (eye[pos].esize == 1
              || is_legal(pos, OTHER_COLOR(color))
              || board[pos] == OTHER_COLOR(color)) {
            add_false_eye(pos, eye, owl->half_eye);
-           
-           /* Marginal status may have changed. This can change the
-             * topological eye evaluation for diagonal neighbors, so
-             * we mark these for another pass if they have already
-             * been examined.
-            */
-           if (!previously_marginal) {
-             for (k = 4; k < 8; k++) {
-               int i = m + deltai[k];
-               int j = n + deltaj[k];
-               if (ON_BOARD(POS(i, j)) && mx[POS(i, j)] == -1) {
-                 mx[POS(i, j)] = 1;
-                 topological_intersections++;
-               }
-             }
-           }
          }
        }
        else if (sum > 2.0) {