[gnugo-devel] arend_3_5.4: more semeai stuff

[Arend Bayer]

 - don't push owl data in owl_analyze_semeai below branch depth
 - semeai refinements

(This patch is on top of arend_3_5.1a, independent of _5.2.)

The first change should save a little time and memory.
(Note: The same change would be possible in do_owl_attack/defend -- if
it weren't for the pass == 3 which can cause branches even below
owl_branch_depth. I am not sure whether this is intentional.)

Then there are a few small step enhancements:
 * saved_goal is reinstated, which I incorrectly killed in arend_3_5.1a.
 * We now try a little harder to update goal array -- but not as hard as
   in owl code. That is, if the move made belongs to the dragon, we look
   for the superstring it might belong to.
 * I have experimentally enabled looking for vital attack moves, to
   correct the eye estimates found by owl_determine_life. I am not sure
   whether this is too expensive.

In general, I have not yet measured the performance hit caused by my
semeai patches.

Arend

Current breakage (of 3.3.4 + arend_3_5.{1a,2,4}):
12 PASSes, 5 FAILs.

./regress.sh . strategy.tst --experimental-semeai
45 unexpected PASS!
./regress.sh . lazarus.tst --experimental-semeai
16 unexpected FAIL: Correct '!L17|J5|K5|K6', got 'L17'
./regress.sh . strategy2.tst --experimental-semeai
72 unexpected PASS!
73 unexpected PASS!
75 unexpected FAIL: Correct 'Q11', got 'F7'
76 unexpected FAIL: Correct 'Q11', got 'F7'
93 unexpected FAIL: Correct 'D11', got 'C11'
./regress.sh . trevor.tst --experimental-semeai
461 unexpected PASS!
./regress.sh . nngs.tst --experimental-semeai
290 unexpected PASS!
2040 unexpected PASS!
./regress.sh . strategy3.tst --experimental-semeai
135 unexpected PASS!
./regress.sh . global.tst --experimental-semeai
46 unexpected PASS!
./regress.sh . 13x13.tst --experimental-semeai
36 unexpected FAIL: Correct 'C5', got 'B2'
./regress.sh . semeai.tst --experimental-semeai
32 unexpected PASS!
37 unexpected PASS!
./regress.sh . strategy4.tst --experimental-semeai
168 unexpected FAIL: Correct 'A3|A4', got 'C8'
188 unexpected PASS!
./regress.sh . nngs2.tst --experimental-semeai
60 unexpected PASS!


diff -X /home/arend/.diffignore -ur ./engine/liberty.h 
../gnugo-push-semeai-owl2/engine/liberty.h
--- ./engine/liberty.h  Thu Jun 20 00:56:42 2002
+++ ../gnugo-push-semeai-owl2/engine/liberty.h  Sun Jun 23 16:10:37 2002
@@ -421,6 +421,7 @@

 void unconditional_life(int unconditional_territory[BOARDMAX], int color);
 void find_superstring(int str, int *num_stones, int *stones);
+void find_superstring_conservative(int str, int *num_stones, int *stones);
 void find_superstring_liberties(int str, int *liberties, int *libs,
                                 int liberty_cap);
 void find_proper_superstring_liberties(int str, int *liberties, int *libs,
diff -X /home/arend/.diffignore -ur ./engine/owl.c 
../gnugo-push-semeai-owl2/engine/owl.c
--- ./engine/owl.c      Mon Jun 24 01:34:09 2002
+++ ../gnugo-push-semeai-owl2/engine/owl.c      Sun Jun 23 16:15:01 2002
@@ -48,6 +48,7 @@

 #define MAX_MOVES 3           /* maximum number of branches at each node */
 #define MAX_SEMEAI_MOVES 2    /* semeai branch factor--must be <= MAX_MOVES */
+#define SEMEAI_BRANCH_DEPTH 12 /* Only one move considered below this depths.*/
 #define MAX_SEMEAI_DEPTH 100  /* Don't read below this depth */
 #define MAX_LUNCHES 10
 #define MAX_WORMS 10  /* maximum number of worms in a dragon to be cataloged */
@@ -214,7 +215,7 @@
                          struct local_owl_data *owl);
 static void owl_mark_boundary(struct local_owl_data *owl);
 static void owl_update_goal(int pos, int same_dragon,
-                           struct local_owl_data *owl);
+                           struct local_owl_data *owl, int semeai_call);
 static void owl_update_boundary_marks(int pos, struct local_owl_data *owl);
 static void owl_find_lunches(struct local_owl_data *owl);
 static void owl_make_domains(struct local_owl_data *owla,
@@ -249,7 +250,9 @@
 static void do_push_owl(struct local_owl_data **owl);
 static void pop_owl(struct local_owl_data **owl);

+#if 0
 static int catalog_goal(struct local_owl_data *owl, int goal_worm[MAX_WORMS]);
+#endif


 /* Called when (apos) and (bpos) point to adjacent dragons
@@ -326,8 +329,10 @@
 {
   int color = board[apos];
   int other = OTHER_COLOR(color);
+#if 0
   int wormsa, wormsb;
   int goal_wormsa[MAX_WORMS], goal_wormsb[MAX_WORMS];
+#endif
   struct owl_move_data vital_defensive_moves[MAX_MOVES];
   struct owl_move_data vital_offensive_moves[MAX_MOVES];
   struct owl_move_data shape_defensive_moves[MAX_MOVES];
@@ -338,6 +343,7 @@
   struct owl_move_data outside_liberty;
   struct owl_move_data common_liberty;
   struct owl_move_data backfilling_move;
+  char saved_goal[BOARDMAX];
   int safe_outside_liberty_found = 0;
   int unsafe_outside_liberty_found = 0;
   int safe_common_liberty_found = 0;
@@ -415,8 +421,10 @@
   else
     read_result = NULL;

+#if 0
   wormsa = catalog_goal(owla, goal_wormsa);
   wormsb = catalog_goal(owlb, goal_wormsb);
+#endif

   outside_liberty.pos = 0;
   common_liberty.pos = 0;
@@ -469,14 +477,32 @@
       }
     }
 #endif
+
     owl_determine_life(owla, owlb, owla->my_eye,
                       color, komaster, 1,
                       vital_defensive_moves,
                       &probable_mina, &probable_maxa);
+    if (level >= 9) {
+      current_owl_data = owla;
+      matches_found = 0;
+      memset(found_matches, 0, sizeof(found_matches));
+      matchpat(owl_shapes_callback, other,
+              &owl_vital_apat_db, vital_defensive_moves, owla->goal);
+      probable_mina -= matches_found;
+    }
+
     owl_determine_life(owlb, owla, owlb->my_eye,
                       other, komaster, 1,
                       vital_offensive_moves,
                       &probable_minb, &probable_maxb);
+    if (level >= 9) {
+      current_owl_data = owlb;
+      matches_found = 0;
+      memset(found_matches, 0, sizeof(found_matches));
+      matchpat(owl_shapes_callback, other,
+              &owl_vital_apat_db, vital_offensive_moves, owla->goal);
+      probable_minb -= matches_found;
+    }

     /* Certain cases can be handled immediately. */
     /* I live, you die, no move needed. */
@@ -651,7 +677,7 @@
                                     owla, owlb,
                                     vital_offensive_moves[k].value);
       owl_add_move(moves, vital_offensive_moves[k].pos,
-                     move_value, vital_offensive_moves[k].name,
+                  move_value, vital_offensive_moves[k].name,
                   same_dragon,
                   vital_offensive_moves[k].escape);
     }
@@ -825,7 +851,7 @@

     if (k > 2
        || (stackp > 6 && k > 1)
-       || (stackp > 12 && k > 0))
+       || (stackp > SEMEAI_BRANCH_DEPTH && k > 0))
       continue;

     if (mpos != NO_MOVE
@@ -833,34 +859,36 @@
        && stackp < MAX_SEMEAI_DEPTH
        && semeai_trymove(mpos, color, moves[k].name, apos, bpos,
                          owl_phase, moves[k].value)) {
-      if (owl_phase)
+      if (owl_phase && stackp <= SEMEAI_BRANCH_DEPTH + 1)
        push_owl(&owla, &owlb);
-      if (debug & DEBUG_SEMEAI)
+      else
+       memcpy(saved_goal, owla->goal, sizeof(saved_goal));
+      if ((debug & DEBUG_SEMEAI) && verbose)
        dump_stack();
       if (board[bpos] == EMPTY) {
        this_resultb = DEAD;
        this_resulta = ALIVE;
       }
       else {
-       if (moves[k].same_dragon)
-         mark_string(mpos, owla->goal, 1);
+       owl_update_goal(mpos, moves[k].same_dragon, owla, 1);
        owla->lunches_are_current = 0;
        owl_update_boundary_marks(mpos, owla);
-       if (liberty_of_goal(mpos, owla))
-         owla->goal[mpos] = 1;
        do_owl_analyze_semeai(bpos, apos, owlb, owla, komaster,
                              &this_resultb, &this_resulta, NULL, 0, owl_phase);
       }

       if (this_resultb == DEAD && this_resulta == ALIVE) {
-       if (owl_phase) {
+       if (owl_phase && stackp <= SEMEAI_BRANCH_DEPTH + 1) {
          pop_owl(&owlb);
          pop_owl(&owla);
        }
+       else
+         memcpy(owla->goal, saved_goal, sizeof(saved_goal));
        popgo();
        *resulta = ALIVE;
        *resultb = DEAD;
-       if (move) *move = mpos;
+       if (move)
+         *move = mpos;
        SGFTRACE2(mpos, ALIVE, moves[k].name);
        close_pattern_list(color, &shape_defensive_patterns);
        close_pattern_list(color, &shape_offensive_patterns);
@@ -882,10 +910,12 @@
        best_move = mpos;
        best_move_k = k;
       }
-      if (owl_phase) {
+      if (owl_phase && stackp <= SEMEAI_BRANCH_DEPTH + 1) {
        pop_owl(&owlb);
        pop_owl(&owla);
       }
+      else
+       memcpy(owla->goal, saved_goal, sizeof(saved_goal));
       popgo();
     }
   }
@@ -2031,7 +2061,7 @@
       /* Add the stone just played to the goal dragon, unless the
        * pattern explicitly asked for not doing this.
        */
-      owl_update_goal(mpos, moves[k].same_dragon, owl);
+      owl_update_goal(mpos, moves[k].same_dragon, owl, 0);

       if (!ko_move) {
        acode = do_owl_attack(str, NULL, owl, new_komaster,
@@ -2136,7 +2166,7 @@
       if (moves[k].pos != NO_MOVE && moves[k].value > 0)
        if (trymove(moves[k].pos, color, moves[k].name, target, EMPTY, 0)) {
          owl->lunches_are_current = 0;
-         owl_update_goal(moves[k].pos, moves[k].same_dragon, owl);
+         owl_update_goal(moves[k].pos, moves[k].same_dragon, owl, 0);
          if (do_owl_defend(target, &move2, owl, EMPTY, 0, 0) == WIN) {
            move = moves[k].pos;
            popgo();
@@ -3246,7 +3276,8 @@
  * goal. If same_dragon is 0, we don't add any stones at all.
  */
 static void
-owl_update_goal(int pos, int same_dragon, struct local_owl_data *owl)
+owl_update_goal(int pos, int same_dragon, struct local_owl_data *owl,
+               int semeai_call)
 {
   int stones[MAX_BOARD * MAX_BOARD];
   int num_stones;
@@ -3262,7 +3293,10 @@
   sgf_dumptree = NULL;
   count_variations = 0;

-  find_superstring(pos, &num_stones, stones);
+  if (semeai_call)
+    find_superstring_conservative(pos, &num_stones, stones);
+  else
+    find_superstring(pos, &num_stones, stones);

   /* Turn sgf output back on. */
   sgf_dumptree = save_sgf_dumptree;
@@ -3752,7 +3786,7 @@
   init_owl(&owl, target1, target2, NO_MOVE, 1);

   if (trymove(move, color, "owl_connection_defends", target1, EMPTY, 0)) {
-    owl_update_goal(move, 1, owl);
+    owl_update_goal(move, 1, owl, 0);
     if (!do_owl_attack(move, NULL, owl, EMPTY, 0, 0))
       result = WIN;
     owl->lunches_are_current = 0;
@@ -4542,7 +4576,7 @@
   (*owl)->lunches_are_current = 0;
   owl_mark_dragon(target1, target2, *owl);
   if (move != NO_MOVE)
-    owl_update_goal(move, 1, *owl);
+    owl_update_goal(move, 1, *owl, 0);
   compute_owl_escape_values(*owl);
 }

@@ -5028,6 +5062,7 @@

 /* Returns the number of worms in the goal dragon, and a pointer to each */

+#if 0
 static int
 catalog_goal(struct local_owl_data *owl, int goal_worm[MAX_WORMS])
 {
@@ -5052,6 +5087,7 @@
     }
   return worms;
 }
+#endif



diff -X /home/arend/.diffignore -ur ./engine/utils.c 
../gnugo-push-semeai-owl2/engine/utils.c
--- ./engine/utils.c    Fri May 17 21:52:43 2002
+++ ../gnugo-push-semeai-owl2/engine/utils.c    Sun Jun 23 16:09:45 2002
@@ -1320,6 +1320,18 @@
                      0, 1);
 }

+/* This is the same as find_superstring, except that connections of
+ * type 5 are omitted. This is used in semeai analysis.
+ */
+void
+find_superstring_conservative(int str, int *num_stones, int *stones)
+{
+  do_find_superstring(str, num_stones, stones,
+                     NULL, NULL, 0,
+                     NULL, NULL, 0,
+                     0, 0);
+}
+

 /* This function computes the superstring at (str) as described above,
  * but omitting connections of type 5. Then it constructs a list of