[gnugo-devel] semeai patch

[Gunnar Farneback]

This patch does a little cleaning and adds comments to the semeai code
in owl.c. Additionally some minor tuning and two new semeai tests.

- semeai code revisions
- owl tuning
- new test cases

I don't have current breakage but before the latest patches went into
CVS it was

nngs1:20        FAIL S13 [F17]            - accidental
semeai:46       FAIL ALIVE DEAD T11 [...] - new test
nando:6         PASS 0 [0]                - haven't checked

/Gunnar

Index: engine/dragon.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/dragon.c,v
retrieving revision 1.110
diff -u -r1.110 dragon.c
--- engine/dragon.c     27 Mar 2003 10:33:11 -0000      1.110
+++ engine/dragon.c     10 May 2003 18:22:38 -0000
@@ -1259,7 +1259,7 @@
  * This function loops over the topologically false and half eye
  * vertices and calls connected_to_eye() for each adjoining string to
  * determine whether they all have external connection to an eye. The
- * result is stored in the array false_eye_territory[] array.
+ * result is stored in the false_eye_territory[] array.
  */
 static void
 analyze_false_eye_territory(void)
Index: engine/owl.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/owl.c,v
retrieving revision 1.157
diff -u -r1.157 owl.c
--- engine/owl.c        9 May 2003 22:44:38 -0000       1.157
+++ engine/owl.c        10 May 2003 18:22:42 -0000
@@ -346,8 +346,13 @@
   do_owl_analyze_semeai(apos, bpos, owla, owlb, EMPTY, NO_MOVE,
                        resulta, resultb, move, 0, owl);
 
-  *semeai_result_certain = result_certain;
+  if (semeai_result_certain)
+    *semeai_result_certain = result_certain;
 
+  /* FIXME: We throw away information about ko results here. We need
+   * to do this until the callers are prepared to deal with ko
+   * results.
+   */
   if (resulta) {
     if (*resulta != 0)
       *resulta = ALIVE;
@@ -427,12 +432,6 @@
   if (!move)
     move = &dummy_move;
   
-  shape_offensive_patterns.initialized = 0;
-  shape_defensive_patterns.initialized = 0;
-  
-  global_owl_node_counter++;
-  local_owl_node_counter++;
-
   ASSERT1(board[apos] == owla->color, apos);
   ASSERT1(board[bpos] == owlb->color, bpos);
 
@@ -443,6 +442,7 @@
 
       if (rr_get_result1(*read_result) != 0)
        *move = rr_get_move(*read_result);
+      
       *resulta = rr_get_result1(*read_result);
       *resultb = rr_get_result2(*read_result);
 
@@ -457,6 +457,12 @@
     }
   }
 
+  global_owl_node_counter++;
+  local_owl_node_counter++;
+
+  shape_offensive_patterns.initialized = 0;
+  shape_defensive_patterns.initialized = 0;
+  
 #if 0
   wormsa = catalog_goal(owla, goal_wormsa);
   wormsb = catalog_goal(owlb, goal_wormsb);
@@ -466,9 +472,6 @@
   common_liberty.pos = NO_MOVE;
   backfill_outside_liberty.pos = NO_MOVE;
   backfill_common_liberty.pos = NO_MOVE;
-  /* turn off the sgf file and variation counting */
-  sgf_dumptree = NULL;
-  count_variations = 0;
   for (k = 0; k < MAX_SEMEAI_MOVES; k++) {
     moves[k].pos = 0;
     moves[k].value = -1;
@@ -478,8 +481,14 @@
   ASSERT1(other == board[bpos], bpos);
   memset(mw, 0, sizeof(mw));
 
-  /* Look for a tactical attack. We seek a semeai worm of owlb
-   * which can be attacked. If such exists, we declare victory.  
+  /* Turn off the sgf file and variation counting. */
+  sgf_dumptree = NULL;
+  count_variations = 0;
+  
+  /* Look for a tactical attack. We seek a semeai worm of owlb which
+   * can be attacked. If such exists and is considered critical, we
+   * declare victory. If it's not considered critical we add the
+   * attacking move as a high priority move to try.
    */
 
   {
@@ -498,8 +507,6 @@
          sgf_dumptree = save_sgf_dumptree;
          count_variations = save_count_variations;
          SGFTRACE_SEMEAI(upos, WIN, WIN, "tactical win found");
-         close_pattern_list(color, &shape_defensive_patterns);
-         close_pattern_list(color, &shape_offensive_patterns);
          READ_RETURN_SEMEAI(read_result, move, upos, WIN, WIN);
        }
        else if (find_defense(semeai_worms[sworm], NULL)) {
@@ -630,10 +637,7 @@
        break;
     
     /* Now we review the moves already considered, while collecting
-     * them into a single list. If no owl moves are found, we end the owl
-     * phase. If no owl move of value > 30 is found, we want to be sure that we
-     * have included a move that fills a liberty. If no such move is found, we
-     * will have to add it later.
+     * them into a single list. 
      */
 
     if (!I_look_alive) {
@@ -665,25 +669,29 @@
     }
 
     if (level < 10) {
-     /* If no owl moves were found on two consecutive moves,
-       turn off the owl phase. */
-     if (moves[0].pos == NO_MOVE) {
-       if (owl_phase == 1)
-         owl_phase = 2;
-       else if (owl_phase == 2)
-         owl_phase = 0;
-     }
-     else owl_phase = 1;
-   }
+      /* If no owl moves were found on two consecutive moves,
+       * turn off the owl phase.
+       */
+      if (moves[0].pos == NO_MOVE) {
+       if (owl_phase == 1)
+         owl_phase = 2;
+       else if (owl_phase == 2)
+         owl_phase = 0;
+      }
+      else
+       owl_phase = 1;
+    }
   }
-  /* now we look for a move to fill a liberty.
-   */
 
   if (1 && verbose) {
     showboard(0);
     goaldump(owla->goal);
     goaldump(owlb->goal);
   }
+  
+  /* Now we look for a move to fill a liberty. This is only
+   * interesting if the opponent doesn't already have two eyes.
+   */
   if (!you_look_alive
       && !safe_outside_liberty_found && moves[0].value < 100) {
     int pos;
@@ -719,6 +727,12 @@
     }
   }
 
+  /* Add the best liberty filling move available. We first want to
+   * play outer liberties, second backfilling moves required before
+   * filling an outer liberty. If no such moves are available we try
+   * to fill a mutual liberty or play a corresponding backfilling
+   * move.
+   */
   if (!you_look_alive) {
     if (safe_outside_liberty_found
        && outside_liberty.pos != NO_MOVE) {
@@ -766,20 +780,24 @@
   tested_moves = 0;
   for (k = 0; k < MAX_SEMEAI_MOVES; k++) {
     int mpos = moves[k].pos;
+    if (mpos == NO_MOVE)
+      break;
 
+    /* Do not try too many moves. */
+    /* FIXME: Replace the hardcoded 6 below with a proper DEPTH constant. */
     if (tested_moves > 2
        || (stackp > semeai_branch_depth2 && tested_moves > 1)
        || (stackp > semeai_branch_depth && tested_moves > 0)) {
       /* If allpats, try and pop to get the move in the sgf record. */
-      if (allpats && mpos!= NO_MOVE
-         && trymove(mpos, color, moves[k].name, apos, komaster, kom_pos)) {
+      if (!allpats)
+       break;
+      else if (trymove(mpos, color, moves[k].name, apos, komaster, kom_pos)) {
        semeai_add_sgf_comment(moves[k].value, owl_phase);
        popgo();
       }
       continue;
     }
-    if (mpos != NO_MOVE 
-       && count_variations < semeai_node_limit
+    if (count_variations < semeai_node_limit
        && stackp < MAX_SEMEAI_DEPTH
        && komaster_trymove(mpos, color, moves[k].name, apos,
                            komaster, kom_pos,
@@ -800,7 +818,14 @@
       owlb->lunches_are_current = 0;
       owl_update_boundary_marks(mpos, owlb);
 
+      /* Do a recursive call to read the semeai after the move we just
+       * tried. If dragon b was captured by the move, call
+       * do_owl_attack() to see whether it sufficed for us to live.
+       */
       if (board[bpos] == EMPTY) {
+       /* FIXME: Are all owl_data fields and relevant static
+         * variables properly set up for a call to do_owl_attack()?
+        */
        this_resulta = REVERSE_RESULT(do_owl_attack(apos, NULL, NULL, owla,
                                                    new_komaster, new_kom_pos,
                                                    0));
@@ -820,6 +845,7 @@
       
       popgo();
 
+      /* Does success require ko? */
       if (ko_move) {
        if (this_resulta != 0)
          this_resulta = KO_B;
@@ -835,6 +861,7 @@
       }
       
       if (this_resultb == WIN && this_resulta == WIN) {
+       /* Ideal result, no need to try any more moves. */
        *resulta = WIN;
        *resultb = WIN;
        *move = mpos;
@@ -844,6 +871,13 @@
        close_pattern_list(color, &shape_offensive_patterns);
        READ_RETURN_SEMEAI(read_result, move, mpos, WIN, WIN);
       }
+      /* We consider our own safety most important and attacking the
+       * opponent as a secondary aim. This means that we prefer seki
+       * over a ko for life and death.
+       *
+       * FIXME: If our dragon is considerably smaller than the
+       * opponent dragon, we should probably prefer ko over seki.
+       */
       else if (this_resulta > best_resulta
               || (this_resulta == best_resulta
                   && this_resultb > best_resultb)) {
@@ -879,7 +913,7 @@
     READ_RETURN_SEMEAI(read_result, move, PASS_MOVE, WIN, 0);
   }
   
-  /* If no move was found, then pass */
+  /* If no move was found, then pass. */
   if (tested_moves == 0) {
     do_owl_analyze_semeai(bpos, apos, owlb, owla, komaster, kom_pos,
                          resultb, resulta, NULL, 1, owl_phase);
@@ -948,8 +982,15 @@
 
   return 0;
 }
-      
-  
+
+
+/* Review the moves in owl_moves[] and add them into semeai_moves[].
+ * This is used to merge multiple sets of owl moves into one move
+ * list, while revising the values for use in semeai reading.
+ *
+ * We also record whether the moves include an outer or common liberty
+ * in the semeai.
+ */
 static void
 semeai_review_owl_moves(struct owl_move_data owl_moves[MAX_MOVES],
                        struct local_owl_data *owla,
@@ -961,27 +1002,31 @@
                        int guess_same_dragon, int value_bonus,
                        int *critical_semeai_worms)
 {
-  int upos;
+  int move;
   int move_value;
   int same_dragon;
   int k;
   
   for (k = 0; k < MAX_MOVES-1; k++) {
-    upos = owl_moves[k].pos;
-    if (upos == NO_MOVE)
+    move = owl_moves[k].pos;
+    if (move == NO_MOVE)
       break;
-       
-    if (liberty_of_goal(upos, owlb)
-       && safe_move(upos, color)) {
-      if (!liberty_of_goal(upos, owla))
+
+    /* Does the move fill a liberty in the semeai? */
+    if (liberty_of_goal(move, owlb)
+       && safe_move(move, color)) {
+      if (!liberty_of_goal(move, owla))
        *safe_outside_liberty_found = 1;
       else
        *safe_common_liberty_found = 1;
     }
 
+    /* For some types of owl moves we don't have same_dragon
+     * information recorded and need to guess.
+     */
     if (guess_same_dragon) {
-      if (liberty_of_goal(upos, owla)
-         || second_liberty_of_goal(upos, owla))
+      if (liberty_of_goal(move, owla)
+         || second_liberty_of_goal(move, owla))
        same_dragon = 1;
       else
        same_dragon = 0;
@@ -989,20 +1034,21 @@
     else
       same_dragon = owl_moves[k].same_dragon;
 
-    mw[upos] = 1;
-    move_value = (semeai_move_value(upos, owla, owlb, owl_moves[k].value,
+    mw[move] = 1;
+    move_value = (semeai_move_value(move, owla, owlb, owl_moves[k].value,
                                    critical_semeai_worms)
                  + value_bonus);
-    owl_add_move(semeai_moves, upos, move_value, owl_moves[k].name, 
+    owl_add_move(semeai_moves, move, move_value, owl_moves[k].name, 
                 same_dragon, owl_moves[k].escape,
                 NO_MOVE, MAX_SEMEAI_MOVES);
-    TRACE("Added %1m %d\n", upos, move_value);
+    TRACE("Added %1m %d\n", move, move_value);
   }
 }
 
-/* Returns the number of liberties gained by the first goal minus the
- * number of liberties lost by the second goal when a move is played
- * at move (if positive, zero otherwise). Used for sorting the moves.
+/* Try to estimate the value of a semeai move. This has two
+ * components. The first is the change in the total number of
+ * liberties for strings involved in the semeai. The second is a bonus
+ * for attacks and defenses of critical semeai worms.
  */
 
 static int
@@ -1073,10 +1119,7 @@
 
 
 
-/* If (pos) points to an empty intersection, returns true if
- * this spot is adjacent to an element of the owl goal.
- */
-
+/* Is the vertex at pos adjacent to an element of the owl goal? */
 static int
 liberty_of_goal(int pos, struct local_owl_data *owl)
 {
@@ -1088,6 +1131,7 @@
   return 0;
 }
 
+/* Is the vertex at pos a second liberty of the owl goal? */
 static int
 second_liberty_of_goal(int pos, struct local_owl_data *owl)
 {
Index: patterns/komoku.sgf
===================================================================
RCS file: /cvsroot/gnugo/gnugo/patterns/komoku.sgf,v
retrieving revision 1.13
diff -u -r1.13 komoku.sgf
--- patterns/komoku.sgf 16 Apr 2003 21:13:37 -0000      1.13
+++ patterns/komoku.sgf 10 May 2003 18:22:42 -0000
@@ -166,11 +166,15 @@
 )
 
 (;B[pf]MA[lh]
-(;W[qc]MA[lh]C[:-,shape(3)];B[rc]MA[lh];W[pc]MA[lh]C[U]
+(;W[qc]MA[lh]C[:-,shape(3)]
+(;B[rc]MA[lh];W[pc]MA[lh]C[U]
 (;B[re]MA[lh]C[:-,shape(8)];W[kc]MA[jg]C[
 ])
 
 (;B[rb]MA[kg];W[kc]MA[jg];B[qj]MA[jk])
+)
+
+(;B[pc]MA[lh]C[0])
 )
 
 (;W[lc]MA[lh]C[0])
Index: patterns/owl_attackpats.db
===================================================================
RCS file: /cvsroot/gnugo/gnugo/patterns/owl_attackpats.db,v
retrieving revision 1.80
diff -u -r1.80 owl_attackpats.db
--- patterns/owl_attackpats.db  2 May 2003 15:04:59 -0000       1.80
+++ patterns/owl_attackpats.db  10 May 2003 18:22:45 -0000
@@ -3624,6 +3624,7 @@
 
 
 Pattern A1105
+# gf Added n classification. (3.3.20)
 
 O..
 XO*        connect against double threat
@@ -3631,7 +3632,7 @@
 x..
 ---
 
-:8,-,value(85)
+:8,n,value(85)
 
 Oa.
 XO*
Index: patterns/owl_defendpats.db
===================================================================
RCS file: /cvsroot/gnugo/gnugo/patterns/owl_defendpats.db,v
retrieving revision 1.94
diff -u -r1.94 owl_defendpats.db
--- patterns/owl_defendpats.db  9 May 2003 22:44:38 -0000       1.94
+++ patterns/owl_defendpats.db  10 May 2003 18:22:47 -0000
@@ -2499,6 +2499,23 @@
 ;!oplay_defend(*,A)
 
 
+Pattern D640
+# gf New pattern. (3.3.20)
+# Compare D720.
+
+?O*.o       try to make eye on edge
+O....
+-----
+
+:8,-,value(56)
+
+?O*bo
+Oa...
+-----
+
+;!obvious_false_oeye(a) && !oplay_attack(b,*,*)
+
+
 #########################################################
 #                                                       #
 #            Make eyeshape in the center                #
@@ -4649,12 +4666,13 @@
 
 Pattern D1139
 # tm New Pattern (3.1.20) (see nngs:110)
+# gf Added n classification. (3.3.20)
 
 ?*
 XO
 OX
 
-:8,bE,value(75)
+:8,bEn,value(75)
 
 ?*
 aO
Index: regression/semeai.tst
===================================================================
RCS file: /cvsroot/gnugo/gnugo/regression/semeai.tst,v
retrieving revision 1.36
diff -u -r1.36 semeai.tst
--- regression/semeai.tst       29 Apr 2003 03:17:13 -0000      1.36
+++ regression/semeai.tst       10 May 2003 18:22:47 -0000
@@ -238,6 +238,10 @@
 #? [ALIVE DEAD (A15|A11|B11|C14|C13|D12|D11|D10|D9|B9|A9)]
 44 owl_analyze_semeai A12 A16
 #? [ALIVE DEAD (A17|B17|C16|D16|E15|E14|F13|F12|F11|F10|F9|F8|B9|A9)]
+45 owl_analyze_semeai Q12 S11
+#? [ALIVE ALIVE (PASS|R8|R9|T11|T9|R11|R10)]
+46 owl_analyze_semeai S11 Q12
+#? [ALIVE ALIVE (PASS|T11|T9|R9|T10|R10|R11)]
 
 loadsgf games/semeai/semeai12.sgf
 45 owl_analyze_semeai B5 A9
Index: regression/games/semeai/semeai9.sgf
===================================================================
RCS file: /cvsroot/gnugo/gnugo/regression/games/semeai/semeai9.sgf,v
retrieving revision 1.2
diff -u -r1.2 semeai9.sgf
--- regression/games/semeai/semeai9.sgf 4 Apr 2003 10:42:28 -0000       1.2
+++ regression/games/semeai/semeai9.sgf 10 May 2003 18:22:49 -0000
@@ -5,6 +5,6 @@
 GN[White (W) vs. Black (B)]
 DT[2000-06-10]
 SY[Cgoban 1.9.2]TM[30:00(5x1:00)];
-AW[ja][na][pa][ab][bb][cb][jb][nb][ob][pb][qb][rb][cc][dc][ec][jc][mc][ed][fd][jd][md][fe][je][ke][me][bf][ff][gf][lf][mf][nf][of][pf][qf][rf][sf][bg][gg][ah][bh][ch][gh][ci][gi][hi][aj][bj][cj][gj][ij][ck][gk][hk][ik][jk][gl][jl][am][bm][cm][em][fm][gm][jm][cn][dn][gn][jn][kn][ln][mn][nn][on][pn][qn][rn][sn][do][eo][go][jo][ep][fp][gp][jp][aq][fq][gq][jq][ar][br][fr][gr][kr][lr][mr][nr][or][bs][fs][gs][ks][ms]
-AB[ma][ra][lb][mb][sb][lc][nc][oc][pc][qc][rc][ad][bd][ld][be][ce][de][le][af][df][kf][dg][eg][kg][lg][mg][ng][og][pg][qg][rg][sg][eh][ph][rh][ei][qi][ri][si][ej][ek][al][bl][cl][dl][el][il][dm][im][in][ao][bo][io][po][qo][ro][so][bp][cp][ip][kp][lp][mp][np][op][cq][dq][iq][kq][pq][dr][ir][jr][pr][ds][is][os]
+AW[ja][na][pa][ab][bb][cb][jb][nb][ob][pb][qb][rb][cc][dc][ec][jc][mc][ed][fd][jd][md][fe][je][ke][me][bf][ff][gf][lf][mf][nf][of][pf][qf][rf][sf][bg][gg][ah][bh][ch][gh][ph][qh][rh][sh][ci][gi][hi][pi][aj][bj][cj][gj][ij][pj][ck][gk][hk][ik][jk][pk][gl][jl][pl][rl][am][bm][cm][em][fm][gm][jm][qm][rm][cn][dn][gn][jn][rn][sn][do][eo][go][jo][ep][fp][gp][jp][aq][fq][gq][jq][ar][br][fr][gr][kr][lr][mr][nr][or][bs][fs][gs][ks][ms]
+AB[ma][ra][lb][mb][sb][lc][nc][oc][pc][qc][rc][ad][bd][ld][be][ce][de][le][af][df][kf][dg][eg][kg][lg][mg][ng][og][pg][qg][rg][sg][eh][oh][ei][oi][ri][ej][oj][rj][ek][ok][rk][al][bl][cl][dl][el][il][ol][sl][dm][im][om][pm][in][pn][qn][ao][bo][io][po][ro][so][bp][cp][ip][kp][lp][mp][np][op][pp][qp][cq][dq][iq][kq][pq][dr][ir][jr][pr][ds][is][os]
 )