[gnugo-devel] arend_3_5.1a: semeai pushes owl data

[Arend Bayer]

 - owl stack can now handle two local_owl_data structs
 - semeai code now uses owl stack
 - owl_phase now local variable in do_owl_analyze_semeai

This is a revision of arend_3_5.1, which causes crashes. The 3rd point
above is new compared to arend_3_5.1 (plus I killed the now unneeded
saved_goal array).

Most of the work in this patch is a little reorganization of the owl
stack, needed to be able to handle two local_owl_data structs.

The patch enlarges memory consumption; in global.tst by about 1.8 M;
this is caused by generating owl moves as far down as stackp==35. Maybe
we should set a limit here (not so much because of the memory consumption,
but because I can't imagine that this still leads to sane results. Hmm).


Arend


Here is the breakage after this patch:
Changes compared to Dan's run at 3.3.3 (haven't checked whether these
are caused by the patch, or by the changes between 3.3.[34]):

new PASSes
strategy: 45
lazarus: 4

new FAILs:
lazarus: 14, 15
nngs: 290
13x13: 39

And full results:

./regress.sh . strategy.tst --experimental-semeai
45 unexpected PASS!
./regress.sh . lazarus.tst --experimental-semeai
4 unexpected PASS!
14 unexpected FAIL: Correct 'Q15|T5|H5', got 'P13'
16 unexpected FAIL: Correct '!L17|J5|K5|K6', got 'L17'
./regress.sh . trevorb.tst --experimental-semeai
430 unexpected PASS!
./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 . nicklas1.tst --experimental-semeai
301 unexpected FAIL: Correct 'H3|H6', got 'J8'
./regress.sh . trevor.tst --experimental-semeai
461 unexpected PASS!
./regress.sh . nngs.tst --experimental-semeai
250 unexpected FAIL: Correct '!S15', got 'S15'
290 unexpected PASS!
2040 unexpected PASS!
./regress.sh . strategy3.tst --experimental-semeai
113 unexpected FAIL: Correct 'P1', got 'S9'
135 unexpected PASS!
./regress.sh . global.tst --experimental-semeai
46 unexpected PASS!
./regress.sh . strategy4.tst --experimental-semeai
188 unexpected PASS!


Index: engine/owl.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/owl.c,v
retrieving revision 1.92
diff -u -r1.92 owl.c
--- engine/owl.c        19 Jun 2002 22:30:04 -0000      1.92
+++ engine/owl.c        20 Jun 2002 08:45:40 -0000
@@ -88,8 +88,13 @@
   int local_owl_node_counter;

   char safe_move_cache[BOARDMAX];
+
+ /* This is used to organize the owl stack. */
+  int restore_from;
+  int number_in_stack;
 };

+
 static int result_certain;

 /* Statistics. */
@@ -223,7 +228,7 @@
                      struct local_owl_data *owla,
                      struct local_owl_data *owlb, int komaster,
                      int *resulta, int *resultb,
-                     int *move, int pass);
+                     int *move, int pass, int owl_phase);
 static int semeai_move_value(int move, struct local_owl_data *owla,
                             struct local_owl_data *owlb,
                             int raw_value);
@@ -232,15 +237,18 @@
 static int matches_found;
 static char found_matches[BOARDMAX];

-static void reduced_init_owl(struct local_owl_data **owl);
+static void reduced_init_owl(struct local_owl_data **owl,
+                            int at_bottom_of_stack);
 static void init_owl(struct local_owl_data **owl, int target1, int target2,
                     int move, int use_stack);
-
 static struct local_owl_data *owl_stack = NULL;
 static int owl_stack_size = 0;
 static int owl_stack_pointer = 0;
-static void push_owl(struct local_owl_data **owl);
+static void push_owl(struct local_owl_data **owla,
+                    struct local_owl_data **owlb);
+static void do_push_owl(struct local_owl_data **owl);
 static void pop_owl(struct local_owl_data **owl);
+
 static int catalog_goal(struct local_owl_data *owl, int goal_worm[MAX_WORMS]);


@@ -249,14 +257,13 @@
  * CRITICAL, analyzes the semeai, assuming that the player
  * of the (apos) dragon moves first.
  *
- * owl_phase determines whether owl moves are being generated
+ * owl determines whether owl moves are being generated
  * or simple liberty filling is taking place.
  *
  * semeai_focus can be either owla, owlb or EMPTY. If it is an owl,
  * then owl attack and defense moves for that owl are given
  * priority.
  */
-static int owl_phase;

 void
 owl_analyze_semeai(int apos, int bpos, int *resulta, int *resultb, int *move,
@@ -264,25 +271,24 @@
 {
   int semeai_focus;

-  static struct local_owl_data owla;
-  static struct local_owl_data owlb;
+  struct local_owl_data *owla;
+  struct local_owl_data *owlb;

   gg_assert(board[apos] == OTHER_COLOR(board[bpos]));
-  owl_phase = owl;
   count_variations = 1;
   TRACE("owl_analyze_semeai: %1m vs. %1m\n", apos, bpos);
   if (owl) {
-    struct local_owl_data *owla_ptr = &owla;
-    struct local_owl_data *owlb_ptr = &owlb;
-    init_owl(&owla_ptr, apos, NO_MOVE, NO_MOVE, 0);
-    init_owl(&owlb_ptr, bpos, NO_MOVE, NO_MOVE, 0);
-    owl_make_domains(&owla, &owlb);
+    init_owl(&owla, apos, NO_MOVE, NO_MOVE, 1);
+    init_owl(&owlb, bpos, NO_MOVE, NO_MOVE, 0);
+    owl_make_domains(owla, owlb);
   }
   else {
-    owla.local_owl_node_counter        = 0;
-    owlb.local_owl_node_counter        = 0;
-    owl_mark_worm(apos, NO_MOVE, &owla);
-    owl_mark_worm(bpos, NO_MOVE, &owlb);
+    reduced_init_owl(&owla, 1);
+    reduced_init_owl(&owlb, 0);
+    owla->local_owl_node_counter       = 0;
+    owlb->local_owl_node_counter       = 0;
+    owl_mark_worm(apos, NO_MOVE, owla);
+    owl_mark_worm(bpos, NO_MOVE, owlb);
   }
   if (stackp > 0)
     semeai_focus = NO_MOVE;
@@ -293,8 +299,8 @@
   else
     semeai_focus = NO_MOVE;

-  do_owl_analyze_semeai(apos, bpos, &owla, &owlb, EMPTY,
-                       resulta, resultb, move, 0);
+  do_owl_analyze_semeai(apos, bpos, owla, owlb, EMPTY,
+                       resulta, resultb, move, 0, owl);
 }

 /* It is assumed that the 'a' player moves first, and
@@ -316,7 +322,7 @@
                      struct local_owl_data *owla,
                      struct local_owl_data *owlb, int komaster,
                      int *resulta, int *resultb,
-                     int *move, int pass)
+                     int *move, int pass, int owl_phase)
 {
   int color = board[apos];
   int other = OTHER_COLOR(color);
@@ -332,7 +338,6 @@
   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;
@@ -342,7 +347,6 @@
   int k;
   int m, n;
   int same_dragon;
-  int save_owl_phase = owl_phase;
   SGFTree *save_sgf_dumptree = sgf_dumptree;
   int save_count_variations = count_variations;
   int move_value;
@@ -364,6 +368,9 @@
   global_owl_node_counter++;
   owla->local_owl_node_counter++;

+  gg_assert(board[apos] == owla->color);
+  gg_assert(board[bpos] == owlb->color);
+
   if ((stackp <= owl_branch_depth) && (hashflags & HASH_SEMEAI)
       && (!pass) && owl_phase) {
     found_read_result = get_read_result2(SEMEAI, EMPTY, 0,
@@ -813,7 +820,6 @@
   /* Now we are ready to try moves. Turn on the sgf output ... */
   sgf_dumptree = save_sgf_dumptree;
   count_variations = save_count_variations;
-  memcpy(saved_goal, owla->goal, sizeof(saved_goal));
   for (k = 0; k < 2*MAX_SEMEAI_MOVES+2; k++) {
     int mpos = moves[k].pos;

@@ -827,9 +833,10 @@
        && stackp < MAX_SEMEAI_DEPTH
        && semeai_trymove(mpos, color, moves[k].name, apos, bpos,
                          owl_phase, moves[k].value)) {
-      if (1)
-       if (debug & DEBUG_SEMEAI)
-         dump_stack();
+      if (owl_phase)
+       push_owl(&owla, &owlb);
+      if (debug & DEBUG_SEMEAI)
+       dump_stack();
       if (board[bpos] == EMPTY) {
        this_resultb = DEAD;
        this_resulta = ALIVE;
@@ -842,13 +849,15 @@
        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);
+                             &this_resultb, &this_resulta, NULL, 0, owl_phase);
       }

       if (this_resultb == DEAD && this_resulta == ALIVE) {
-       memcpy(owla->goal, saved_goal, sizeof(saved_goal));
+       if (owl_phase) {
+         pop_owl(&owlb);
+         pop_owl(&owla);
+       }
        popgo();
-       owl_phase = save_owl_phase;
        *resulta = ALIVE;
        *resultb = DEAD;
        if (move) *move = mpos;
@@ -873,9 +882,11 @@
        best_move = mpos;
        best_move_k = k;
       }
-      memcpy(owla->goal, saved_goal, sizeof(saved_goal));
+      if (owl_phase) {
+       pop_owl(&owlb);
+       pop_owl(&owla);
+      }
       popgo();
-      owl_phase = save_owl_phase;
     }
   }

@@ -893,7 +904,7 @@
   /* If no move was found, then pass */
   if (best_resulta == UNKNOWN) {
     do_owl_analyze_semeai(bpos, apos, owlb, owla, komaster,
-                         resultb, resulta, NULL, 1);
+                         resultb, resulta, NULL, 1, owl_phase);
     SGFTRACE2(PASS_MOVE, UNKNOWN, "No move found");
     if (move) *move = PASS_MOVE;
     READ_RETURN_SEMEAI(read_result, move, PASS_MOVE, *resulta, *resultb);
@@ -1432,7 +1443,7 @@
        dump_stack();

       /* We have now made a move. Analyze the new position. */
-      push_owl(&owl);
+      push_owl(&owl, NULL);
       mw[mpos] = 1;
       number_tried_moves++;
       owl->lunches_are_current = 0;
@@ -2012,7 +2023,7 @@
        dump_stack();

       /* We have now made a move. Analyze the new position. */
-      push_owl(&owl);
+      push_owl(&owl, NULL);
       mw[mpos] = 1;
       number_tried_moves++;
       owl->lunches_are_current = 0;
@@ -4093,7 +4104,7 @@
   /* FIXME: We want to use the full init_owl here too (cf. similar
    * remark below).
    */
-  reduced_init_owl(&owl);
+  reduced_init_owl(&owl, 1);

   owl->color = OTHER_COLOR(board[str]);
   owl->local_owl_node_counter = 0;
@@ -4493,27 +4504,39 @@
  * init_owl() also in owl_substantial.
  */
 static void
-reduced_init_owl(struct local_owl_data **owl)
+reduced_init_owl(struct local_owl_data **owl, int at_bottom_of_stack)
 {
   if (owl_stack_size == 0) {
     owl_stack_size = owl_reading_depth + 2;
     owl_stack = malloc(owl_stack_size * sizeof(*owl_stack));
     gg_assert(owl_stack != NULL);
   }
-  *owl = &owl_stack[0];
+
+  if (at_bottom_of_stack) {
+    owl_stack_pointer = 0;
+    *owl = &owl_stack[0];
+  }
+  else {
+    owl_stack_pointer++;
+    *owl = &owl_stack[owl_stack_pointer];
+  }
+  owl_stack[owl_stack_pointer].number_in_stack = owl_stack_pointer;
 }


 /*
  * If use_stack is set, the stack is initialized, and the return value
  * of *owl is a pointer to the bottom of the stack.
+ *
+ * at_bottom_of_stack = 1 means **owl will be initialized at the bottom
+ *     of the stack
+ * (otherwise, it will be set at the lowest available spot in the stack)
  */
 static void
 init_owl(struct local_owl_data **owl, int target1, int target2, int move,
-         int use_stack)
+         int at_bottom_of_stack)
 {
-  if (use_stack)
-    reduced_init_owl(owl);
+  reduced_init_owl(owl, at_bottom_of_stack);

   (*owl)->local_owl_node_counter = 0;
   (*owl)->lunches_are_current = 0;
@@ -4528,29 +4551,63 @@
  * Storage of owl data
  ***********************/

+/* Push owl data one step upwards in the stack. Gets called from
+ * push_owl.
+ */
+static void
+do_push_owl(struct local_owl_data **owl)
+{
+  gg_assert(&owl_stack[(*owl)->number_in_stack] == *owl);
+
+  /* Copy the owl data. */
+  owl_stack_pointer++;
+  owl_stack[owl_stack_pointer] = **owl;
+
+  /* Needed for stack organization: */
+  owl_stack[owl_stack_pointer].number_in_stack = owl_stack_pointer;
+  owl_stack[owl_stack_pointer].restore_from = (*owl)->number_in_stack;
+
+  /* Finally move the *owl pointer. */
+  *owl = &owl_stack[owl_stack_pointer];
+}
+
 /* Push owl data one step upwards in the stack. The stack is dynamically
- * reallocated if it is too small.
+ * reallocated if it is too small. Second argument is used from the
+ * semeai code; use NULL otherwise.
+ *
+ * If you use push_owl with two arguments, later call
+ * pop_owl(owlb); pop_owl(owla);
+ * in this order!
  */
 static void
-push_owl(struct local_owl_data **owl)
+push_owl(struct local_owl_data **owla, struct local_owl_data **owlb)
 {
-  gg_assert(*owl == &owl_stack[owl_stack_pointer]);
   /* Do we need to enlarge the stack? */
   if (owl_stack_pointer == owl_stack_size - 1) {
+    int num_a = (*owla)->number_in_stack;
+    int num_b = 0;
+    if (owlb)
+      num_b = (*owlb)->number_in_stack;
     if (0)
-      gprintf("Have to enlarge owl stack!");
-    owl_stack_size++;
+      gprintf("Have to enlarge owl stack! (size %d, owl_stack %d, stackp 
%d)\n",
+             owl_stack_size, owl_stack_pointer, stackp);
+    if (owlb)
+      owl_stack_size += 2;
+    else
+      owl_stack_size++;
     owl_stack = realloc(owl_stack, owl_stack_size * sizeof(*owl_stack));
     gg_assert(owl_stack != NULL);
-    *owl = &owl_stack[owl_stack_pointer];
+    *owla = &owl_stack[num_a];
+    if (owlb)
+      *owlb = &owl_stack[num_b];
   }

-  /* Copy the owl data. */
-  owl_stack_pointer++;
-  owl_stack[owl_stack_pointer] = **owl;
-  *owl = &owl_stack[owl_stack_pointer];
+  do_push_owl(owla);
+  if (owlb)
+    do_push_owl(owlb);
 }

+
 /* Retrieve owl data from the stack. The local_owl_node_counter field
  * is not reset.
  */
@@ -4559,8 +4616,10 @@
 {
   int nodes = (*owl)->local_owl_node_counter;
   gg_assert(*owl == &owl_stack[owl_stack_pointer]);
+
+  *owl = &owl_stack[(*owl)->restore_from];
+
   owl_stack_pointer--;
-  *owl = &owl_stack[owl_stack_pointer];
   (*owl)->local_owl_node_counter = nodes;
 }