[gnugo-devel] Multiple semeai patch

[Gunnar Farneback]

When one dragon is involved in multiple semeais, where it locally wins
one and loses one, GNU Go currently tends to misevaluate the status of
at least one dragon. One example of this can be found in nicklas5:1211
and simplified versions of the same problem in the recently added
semeai:81-86.

This patch solves this problem by adding some extra processing of the
semeai results in the semeai() function. Regression delta:

nicklas1:1213   PASS N4 [N4]
nicklas5:1211   PASS alive [alive]
nngs:820        PASS L9 [J13|L9]
semeai:82       pass (fails in CVS)
semeai:83       pass (fails in CVS)
semeai:85       pass (fails in CVS)
semeai:86       pass (fails in CVS)
strategy4:162   FAIL M8 [O7|Q7|N7]
nngs4:210       PASS B19 [!S5]

The problem with strategy4:162 seems to be a semeai misread rather
than this patch. However, something strange is also going on. When
generating a move, the semeai traces say

  Considering semeai between L9 and O10
  semeai worm: O10
  semeai worm: L9
  results if black moves first: 0 0, PASS

but when running --decide-semeai we get

  Analyzing semeai between L9 and O10, black moves first
  Semeai defense of L9: result WIN N8
  Semeai attack of O10: result WIN N8
  356 nodes

I have no good idea what's going on here.

/Gunnar

Index: engine/semeai.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/semeai.c,v
retrieving revision 1.61
diff -u -r1.61 semeai.c
--- engine/semeai.c     30 Aug 2003 20:38:36 -0000      1.61
+++ engine/semeai.c     31 Aug 2003 09:13:04 -0000
@@ -33,7 +33,7 @@
                          enum dragon_status new_safety);
 
 
-/* new_semeai() searches for pairs of dragons of opposite color which
+/* semeai() searches for pairs of dragons of opposite color which
  * have safety DEAD. If such a pair is found, owl_analyze_semeai is
  * called to read out which dragon will prevail in a semeai, and
  * whether a move now will make a difference in the outcome. The
@@ -135,6 +135,50 @@
       semeai_certain[d1][d2] = result_certain;
     }
   
+  /* Look for dragons which lose all their semeais outright. The
+   * winners in those semeais are considered safe and further semeais
+   * they are involved in are disregarded. See semeai:81-86 and
+   * nicklas5:1211 for examples of where this is useful.
+   *
+   * Note: To handle multiple simultaneous semeais properly we would
+   * have to make simultaneous semeai reading. Lacking that we can
+   * only get rough guesses of the correct status of the involved
+   * dragons. This code is not guaranteed to be correct in all
+   * situations but should usually be an improvement.
+   */
+  for (d1 = 0; d1 < num_dragons; d1++) {
+    int involved_in_semeai = 0;
+    int all_lost = 1;
+    for (d2 = 0; d2 < num_dragons; d2++) {
+      if (semeai_results_first[d1][d2] != -1) {
+       involved_in_semeai = 1;
+       if (semeai_results_first[d1][d2] != 0) {
+         all_lost = 0;
+         break;
+       }
+      }
+    }
+    
+    if (involved_in_semeai && all_lost) {
+      /* Leave the status changes to the main loop below. Here we just
+       * remove the presumably irrelevant semeai results.
+       */
+      for (d2 = 0; d2 < num_dragons; d2++) {
+       if (semeai_results_first[d1][d2] == 0) {
+         int d3;
+         for (d3 = 0; d3 < num_dragons; d3++) {
+           if (semeai_results_second[d3][d2] > 0) {
+             semeai_results_first[d3][d2] = -1;
+             semeai_results_second[d3][d2] = -1;
+             semeai_results_first[d2][d3] = -1;
+             semeai_results_second[d2][d3] = -1;
+           }
+         }
+       }
+      }
+    }
+  }
+
   for (d1 = 0; d1 < num_dragons; d1++) {
     int semeai_found = 0;
     int best_defense = 0;