Re: [gnugo-devel] The killer heuristic

[Evan Berggren Daniel]

On Fri, 24 Jan 2003, I wrote:

> > Nice. Do I understand the patch correctly that you don't use this
> > heuristic in defend1, defend2, attack2, attack3? Any reason for this?
>
> I don't use it in those functions because it actually hurt the move
> ordering.  Actually, I suppose that info was from the first version of the
> patch, so that might be different now.  I'll try it out.  However, in
> general I think the tactical move ordering is fairly good.  It might be
> interesting to collect statistics on how much room for improvement is left
> (ie, what sort of numbers the ideal ordering would produce).

The same is true for then new version of the patch.  The basic reason is
that for the low liberty count functions, any move changes the local
position so drastically that the the killer heuristic doesn't help much.
For the higher count ones, and presumably even more so for the owl code,
any one move has only a small impact on the position, so information about
good moves is likely transferable across branches of the tree.

> > Tiny little detail:
> >
> > > @@ -1014,6 +1015,9 @@
> > >
> > >    RTRACE("Can we rescue %1m?\n", str);
> > >
> > > +  if (move && ON_BOARD(*move) && board[*move] == EMPTY)
> > > +    xpos = *move;
> > > +
> > The ON_BOARD(*move) is redundant.
>
> I suppose you're right.  It got added while I was tracking down bad
> pointers.

Of course, it didn't much help with that either...  Actually, the
ON_BOARD() and the board[*move] tests are redundant, since all that is
done is comparison of the form move == killer in order_moves.

The following patch changes that and fixes a couple comments.  It is a
replacement for the original patch.

Evan Daniel

Index: engine/reading.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/reading.c,v
retrieving revision 1.101
diff -u -r1.101 reading.c
--- engine/reading.c    18 Jan 2003 11:39:45 -0000      1.101
+++ engine/reading.c    24 Jan 2003 20:15:43 -0000
@@ -188,7 +188,8 @@
 static void double_atari_chain2_moves(int str,
                                      struct reading_moves *moves);
 static void order_moves(int str, struct reading_moves *moves,
-                       int color, const char *funcname, int first_move);
+                       int color, const char *funcname, int first_move,
+                       int killer);
 static int simple_ladder_attack(int str, int *move, int komaster, int kom_pos);
 static int simple_ladder_defend(int str, int *move, int komaster, int kom_pos);
 static int in_list(int move, int num_moves, int *moves);
@@ -1004,7 +1005,7 @@
 static int
 do_find_defense(int str, int *move, int komaster, int kom_pos)
 {
-  int xpos;
+  int xpos = NO_MOVE;
   int dcode = 0;
   int liberties;
   int found_read_result;
@@ -1014,6 +1015,9 @@

   RTRACE("Can we rescue %1m?\n", str);

+  if (move)
+    xpos = *move;
+
   /* We first check if the number of liberties is larger than four. In
    * that case we don't cache the result and to avoid needlessly
    * storing the position in the hash table, we must do this test
@@ -1158,7 +1162,7 @@
   break_chain_moves(str, &moves);
   set_up_snapback_moves(str, lib, &moves);

-  order_moves(str, &moves, color, read_function_name, 0);
+  order_moves(str, &moves, color, read_function_name, 0, NO_MOVE);

   for (k = 0; k < moves.num; k++) {
     int new_komaster;
@@ -1229,7 +1233,7 @@
 defend2(int str, int *move, int komaster, int kom_pos)
 {
   int color, other;
-  int xpos;
+  int xpos = NO_MOVE;
   int liberties;
   int libs[2];
   int liberties2;
@@ -1240,6 +1244,7 @@
   int savecode = 0;
   int k;
   int r;
+  int suggest_move = NO_MOVE;

   SETUP_TRACE_INFO("defend2", str);
   reading_node_counter++;
@@ -1281,8 +1286,8 @@

   if (stackp <= backfill_depth)
     special_rescue2_moves(str, libs, &moves);
-
-  order_moves(str, &moves, color, read_function_name, 0);
+
+  order_moves(str, &moves, color, read_function_name, 0, NO_MOVE);

   for (k = 0; k < moves.num; k++) {
     int new_komaster;
@@ -1295,13 +1300,15 @@
                         komaster, kom_pos, &new_komaster, &new_kom_pos,
                         &ko_move, stackp <= ko_depth && savecode == 0)) {
       if (!ko_move) {
-       int acode = do_attack(str, NULL, new_komaster, new_kom_pos);
+       int acode = do_attack(str, &suggest_move, new_komaster,
+           new_kom_pos);
        popgo();
        CHECK_RESULT(savecode, savemove, acode, xpos, move,
                     "defense effective - A");
       }
       else {
-       if (do_attack(str, NULL, new_komaster, new_kom_pos) != WIN) {
+       if (do_attack(str, &suggest_move, new_komaster,
+             new_kom_pos) != WIN) {
          savemove = xpos;
          savecode = KO_B;
        }
@@ -1341,7 +1348,7 @@
   }

   /* Only order and test the new set of moves. */
-  order_moves(str, &moves, other, read_function_name, saved_num_moves);
+  order_moves(str, &moves, other, read_function_name, saved_num_moves, 
NO_MOVE);

   for (k = saved_num_moves; k < moves.num; k++) {
     int new_komaster;
@@ -1353,13 +1360,15 @@
                         komaster, kom_pos, &new_komaster, &new_kom_pos,
                         &ko_move, stackp <= ko_depth && savecode == 0)) {
       if (!ko_move) {
-       int acode = do_attack(str, NULL, new_komaster, new_kom_pos);
+       int acode = do_attack(str, &suggest_move, new_komaster,
+           new_kom_pos);
        popgo();
        CHECK_RESULT(savecode, savemove, acode, xpos, move,
                     "defense effective - B");
       }
       else {
-       if (do_attack(str, NULL, new_komaster, new_kom_pos) != WIN) {
+       if (do_attack(str, &suggest_move, new_komaster,
+             new_kom_pos) != WIN) {
          savemove = xpos;
          savecode = KO_B;
        }
@@ -1416,7 +1425,7 @@
   }

   /* Only order and test the new set of moves. */
-  order_moves(str, &moves, other, read_function_name, saved_num_moves);
+  order_moves(str, &moves, other, read_function_name, saved_num_moves, 
NO_MOVE);

   for (k = saved_num_moves; k < moves.num; k++) {
     int new_komaster;
@@ -1428,13 +1437,15 @@
                         komaster, kom_pos, &new_komaster, &new_kom_pos,
                         &ko_move, stackp <= ko_depth && savecode == 0)) {
       if (!ko_move) {
-       int acode = do_attack(str, NULL, new_komaster, new_kom_pos);
+       int acode = do_attack(str, &suggest_move, new_komaster,
+           new_kom_pos);
        popgo();
        CHECK_RESULT(savecode, savemove, acode, xpos, move,
                     "defense effective - A");
       }
       else {
-       if (do_attack(str, NULL, new_komaster, new_kom_pos) != WIN) {
+       if (do_attack(str, &suggest_move, new_komaster,
+           new_kom_pos) != WIN) {
          savemove = xpos;
          savecode = KO_B;
        }
@@ -1460,7 +1471,7 @@
 defend3(int str, int *move, int komaster, int kom_pos)
 {
   int color, other;
-  int xpos;
+  int xpos = NO_MOVE;
   int liberties;
   int libs[3];
   struct reading_moves moves;
@@ -1468,6 +1479,7 @@
   int savemove = 0;
   int savecode = 0;
   int k;
+  int suggest_move = NO_MOVE;

   SETUP_TRACE_INFO("defend3", str);
   reading_node_counter++;
@@ -1505,7 +1517,7 @@
   if (stackp <= backfill2_depth)
     hane_rescue_moves(str, libs, &moves);

-  order_moves(str, &moves, color, read_function_name, 0);
+  order_moves(str, &moves, color, read_function_name, 0, *move);

   for (k = 0; k < moves.num; k++) {
     int new_komaster;
@@ -1521,13 +1533,15 @@
                         &new_komaster, &new_kom_pos,
                         &ko_move, stackp <= ko_depth && savecode == 0)) {
       if (!ko_move) {
-       int acode = do_attack(str, NULL, new_komaster, new_kom_pos);
+       int acode = do_attack(str, &suggest_move, new_komaster,
+           new_kom_pos);
        popgo();
        CHECK_RESULT(savecode, savemove, acode, xpos, move,
                     "defense effective - A");
       }
       else {
-       if (do_attack(str, NULL, new_komaster, new_kom_pos) != WIN) {
+       if (do_attack(str, &suggest_move, new_komaster,
+             new_kom_pos) != WIN) {
          savemove = xpos;
          savecode = KO_B;
        }
@@ -1622,7 +1636,7 @@
   }

   /* Only order and test the new set of moves. */
-  order_moves(str, &moves, other, read_function_name, saved_num_moves);
+  order_moves(str, &moves, other, read_function_name, saved_num_moves, *move);

   for (k = saved_num_moves; k < moves.num; k++) {
     int new_komaster;
@@ -1634,13 +1648,15 @@
                         komaster, kom_pos, &new_komaster, &new_kom_pos,
                         &ko_move, stackp <= ko_depth && savecode == 0)) {
       if (!ko_move) {
-       int acode = do_attack(str, NULL, new_komaster, new_kom_pos);
+       int acode = do_attack(str, &suggest_move, new_komaster,
+           new_kom_pos);
        popgo();
        CHECK_RESULT(savecode, savemove, acode, xpos, move,
                     "defense effective - A");
       }
       else {
-       if (do_attack(str, NULL, new_komaster, new_kom_pos) != WIN) {
+       if (do_attack(str, &suggest_move, new_komaster,
+             new_kom_pos) != WIN) {
          savemove = xpos;
          savecode = KO_B;
        }
@@ -1686,7 +1702,7 @@
     break_chain3_moves(str, &moves);

   /* Only order and test the new set of moves. */
-  order_moves(str, &moves, other, read_function_name, saved_num_moves);
+  order_moves(str, &moves, other, read_function_name, saved_num_moves, *move);

   for (k = saved_num_moves; k < moves.num; k++) {
     int new_komaster;
@@ -1698,13 +1714,15 @@
                         komaster, kom_pos, &new_komaster, &new_kom_pos,
                         &ko_move, stackp <= ko_depth && savecode == 0)) {
       if (!ko_move) {
-       int acode = do_attack(str, NULL, new_komaster, new_kom_pos);
+       int acode = do_attack(str, &suggest_move, new_komaster,
+           new_kom_pos);
        popgo();
        CHECK_RESULT(savecode, savemove, acode, xpos, move,
                     "defense effective - A");
       }
       else {
-       if (do_attack(str, NULL, new_komaster, new_kom_pos) != WIN) {
+       if (do_attack(str, &suggest_move, new_komaster,
+             new_kom_pos) != WIN) {
          savemove = xpos;
          savecode = KO_B;
        }
@@ -1731,13 +1749,14 @@
 defend4(int str, int *move, int komaster, int kom_pos)
 {
   int color, other;
-  int xpos;
+  int xpos = NO_MOVE;
   int liberties;
   int libs[4];
   struct reading_moves moves;
   int savemove = 0;
   int savecode = 0;
   int k;
+  int suggest_move = NO_MOVE;

   SETUP_TRACE_INFO("defend4", str);
   reading_node_counter++;
@@ -1775,7 +1794,7 @@
 #endif
   }

-  order_moves(str, &moves, color, read_function_name, 0);
+  order_moves(str, &moves, color, read_function_name, 0, *move);

   for (k = 0; k < moves.num; k++) {
     int new_komaster;
@@ -1791,13 +1810,15 @@
                         &new_komaster, &new_kom_pos,
                         &ko_move, stackp <= ko_depth && savecode == 0)) {
       if (!ko_move) {
-       int acode = do_attack(str, NULL, new_komaster, new_kom_pos);
+       int acode = do_attack(str, &suggest_move, new_komaster,
+           new_kom_pos);
        popgo();
        CHECK_RESULT(savecode, savemove, acode, xpos, move,
                     "defense effective - A");
       }
       else {
-       if (do_attack(str, NULL, new_komaster, new_kom_pos) != WIN) {
+       if (do_attack(str, &suggest_move, new_komaster,
+             new_kom_pos) != WIN) {
          savemove = xpos;
          savecode = KO_B;
        }
@@ -2838,7 +2859,7 @@
 do_attack(int str, int *move, int komaster, int kom_pos)
 {
   int color = board[str];
-  int xpos;
+  int xpos = NO_MOVE;
   int libs;
   int result = 0;
   int found_read_result;
@@ -2848,6 +2869,9 @@

   ASSERT1(color != 0, str);

+  if (move)
+    xpos = *move;
+
   if (color == 0)      /* if assertions are turned off, silently fails */
     return 0;

@@ -3089,7 +3113,7 @@
   int color = board[str];
   int other = OTHER_COLOR(color);
   int hpos;
-  int xpos;
+  int xpos = NO_MOVE;
   int liberties, r;
   int libs[2];
   int libs2[2];
@@ -3103,6 +3127,7 @@
   int adjacent_liberties = 0;
   int pass;
   int saved_num_moves = 0;
+  int suggest_move = NO_MOVE;

   SETUP_TRACE_INFO("attack2", str);
   reading_node_counter++;
@@ -3223,7 +3248,7 @@
     }

     if (pass != 3) {
-      order_moves(str, &moves, other, read_function_name, saved_num_moves);
+      order_moves(str, &moves, other, read_function_name, saved_num_moves, 
NO_MOVE);

       for (k = saved_num_moves; k < moves.num; k++) {
         int new_komaster;
@@ -3235,7 +3260,8 @@
                             komaster, kom_pos, &new_komaster, &new_kom_pos,
                             &ko_move, stackp <= ko_depth && savecode == 0)) {
           if (!ko_move) {
-           dcode = do_find_defense(str, NULL, new_komaster, new_kom_pos);
+           dcode = do_find_defense(str, &suggest_move, new_komaster,
+               new_kom_pos);
            if (dcode != WIN
                && do_attack(str, NULL, new_komaster, new_kom_pos)) {
              popgo();
@@ -3246,7 +3272,8 @@
              popgo();
           }
           else {
-           if (do_find_defense(str, NULL, new_komaster, new_kom_pos) != WIN
+           if (do_find_defense(str, &suggest_move, new_komaster,
+                 new_kom_pos) != WIN
                && do_attack(str, NULL, new_komaster, new_kom_pos) != 0) {
              savemove = apos;
              savecode = KO_B;
@@ -3288,7 +3315,8 @@
                  popgo();
                  if (trymove(xpos, other, "attack2-D", str, komaster,
                              kom_pos)) {
-                   dcode = do_find_defense(str, NULL, komaster, kom_pos);
+                   dcode = do_find_defense(str, &suggest_move, komaster,
+                       kom_pos);
                    if (dcode != WIN
                        && do_attack(str, NULL, komaster, kom_pos)) {
                      popgo();
@@ -3305,7 +3333,8 @@
              else {
                dcode = do_find_defense(str, NULL, komaster, kom_pos);
                if (dcode != WIN
-                   && do_attack(str, NULL, komaster, kom_pos)) {
+                   && do_attack(str, &suggest_move, komaster,
+                           kom_pos)) {
                  popgo();
                  CHECK_RESULT(savecode, savemove, dcode, apos, move,
                               "attack effective");
@@ -3350,7 +3379,7 @@
   int color = board[str];
   int other = OTHER_COLOR(color);
   int adj, adjs[MAXCHAIN];
-  int xpos;
+  int xpos = NO_MOVE;
   int liberties;
   int libs[3];
   int r;
@@ -3361,6 +3390,7 @@
   int savecode = 0;
   int pass;
   int saved_num_moves = 0;
+  int suggest_move = NO_MOVE;

   SETUP_TRACE_INFO("attack3", str);
   reading_node_counter++;
@@ -3458,7 +3488,7 @@

     if (pass == 0 || pass == 1 || pass == 2) {

-      order_moves(str, &moves, other, read_function_name, saved_num_moves);
+      order_moves(str, &moves, other, read_function_name, saved_num_moves, 
NO_MOVE);

       /* Try the moves collected so far. */
       for (k = saved_num_moves; k < moves.num; k++) {
@@ -3474,7 +3504,8 @@
                             &new_kom_pos, &ko_move,
                             stackp <= ko_depth && savecode == 0)) {
           if (!ko_move) {
-           dcode = do_find_defense(str, NULL, new_komaster, new_kom_pos);
+           dcode = do_find_defense(str, &suggest_move, new_komaster,
+               new_kom_pos);
            if (dcode != WIN
                && do_attack(str, NULL, new_komaster, new_kom_pos)) {
              popgo();
@@ -3485,7 +3516,8 @@
              popgo();
           }
           else {
-           if (do_find_defense(str, NULL, new_komaster, new_kom_pos) != WIN
+           if (do_find_defense(str, &suggest_move, new_komaster,
+                 new_kom_pos) != WIN
                && do_attack(str, NULL, new_komaster, new_kom_pos) != 0) {
              savemove = xpos;
              savecode = KO_B;
@@ -3521,7 +3553,8 @@
                  popgo();
                  if (trymove(xpos, other, "attack3-F", str,
                              komaster, kom_pos)) {
-                   dcode = do_find_defense(str, NULL, komaster, kom_pos);
+                   dcode = do_find_defense(str, &suggest_move, komaster,
+                                   kom_pos);
                    if (dcode != WIN
                        && do_attack(str, NULL, komaster, kom_pos)) {
                      popgo();
@@ -3537,7 +3570,8 @@
              }
              else {
                dcode = do_find_defense(str, NULL, komaster, kom_pos);
-               if (dcode != WIN && do_attack(str, NULL, komaster, kom_pos)) {
+               if (dcode != WIN && do_attack(str, &suggest_move, komaster,
+                               kom_pos)) {
                  popgo();
                  CHECK_RESULT(savecode, savemove, dcode, apos, move,
                               "attack effective");
@@ -3564,7 +3598,7 @@
 {
   int color = board[str];
   int other = OTHER_COLOR(color);
-  int xpos;
+  int xpos = NO_MOVE;
   int r;
   int k;
   int liberties;
@@ -3576,6 +3610,7 @@
   int savecode = 0;
   int pass;
   int saved_num_moves = 0;
+  int suggest_move = NO_MOVE;

   SETUP_TRACE_INFO("attack4", str);

@@ -3645,7 +3680,7 @@
     }

     if (pass == 0 || pass == 1) {
-      order_moves(str, &moves, other, read_function_name, saved_num_moves);
+      order_moves(str, &moves, other, read_function_name, saved_num_moves, 
*move);

       /* Try the moves collected so far. */
       for (k = saved_num_moves; k < moves.num; k++) {
@@ -3675,8 +3710,10 @@
              popgo();
           }
           else {
-           if (do_find_defense(str, NULL, new_komaster, new_kom_pos) != WIN
-               && do_attack(str, NULL, new_komaster, new_kom_pos) != 0) {
+           if (do_find_defense(str, &suggest_move, new_komaster,
+                 new_kom_pos) != WIN
+               && do_attack(str, &suggest_move, new_komaster,
+                       new_kom_pos) != 0) {
              savemove = xpos;
              savecode = KO_B;
            }
@@ -4685,7 +4722,7 @@

   break_chain_moves(str, &moves);
   set_up_snapback_moves(str, lib, &moves);
-  order_moves(str, &moves, color, read_function_name, 0);
+  order_moves(str, &moves, color, read_function_name, 0, NO_MOVE);

   for (k = 0; k < moves.num; k++) {
     int ko_capture;
@@ -4932,7 +4969,7 @@

 static void
 order_moves(int str, struct reading_moves *moves, int color,
-           const char *funcname, int first_move)
+           const char *funcname, int first_move, int killer)
 {
   int string_color = board[str];
   int string_libs = countlib(str);
@@ -5094,6 +5131,8 @@
       else
        moves->score[r] += attack_save_score[5];
     }
+    if (moves->pos[r] == killer)
+      moves->score[r] += 50;
   }

   /* Now sort the moves.  We use selection sort since this array will
@@ -5522,7 +5561,7 @@
   for (k = 0; k < 2; k++)
     ADD_CANDIDATE_MOVE(libs[k], 0, moves);

-  order_moves(str, &moves, other, read_function_name, 0);
+  order_moves(str, &moves, other, read_function_name, 0, NO_MOVE);

   for (k = 0; k < moves.num; k++) {
     int new_komaster;
@@ -5586,7 +5625,7 @@
   moves.num = 1;

   break_chain_moves(str, &moves);
-  order_moves(str, &moves, color, read_function_name, 0);
+  order_moves(str, &moves, color, read_function_name, 0, NO_MOVE);

   for (k = 0; k < moves.num; k++) {
     int new_komaster;