[gnugo-devel] minor ko threat selection tuning

[Paul Pogonyshev]

- extra care is now taken not to waste points on tiny ko threats
- ko threats with large enough followup values are always preffered to
  threats with arbitrary large reverse followups
- twogtp.py fixed to handle jigo in endgame contests

see the comments in the patch for more information.

regression breakage:

./regress.sh . trevord.tst
600 unexpected PASS!
620 unexpected PASS!

both passes are good.

i've also run endgame contests on `honinbo' and `meijin' subdirectories
of i-don't-remember-whose game collection. only non-resigned games were
used, `--endgame' parameter was set to 10 moves.

/home/paul/games/honinbo/honinbo-1956-6.sgf: B+1.5 B+2.5 Difference: 1.0
/home/paul/games/honinbo/honinbo-1957-6.sgf: W+7.5 W+6.5 Difference: 1.0
/home/paul/games/honinbo/honinbo-1962-3.sgf: B+5.5 B+6.5 Difference: 1.0
/home/paul/games/honinbo/honinbo-1988-3.sgf: B+22.5 B+5.5 Difference: -17.0
/home/paul/games/honinbo/honinbo-1996-6.sgf: W+4.5 W+3.5 Difference: 1.0
/home/paul/games/meijin/meijin-1981-1.sgf: W+1.5 W+0.5 Difference: 1.0

the only negative change is accidential and is due to an uncovered
problem. basically, gnu go lacks a detect_seki_blunder() function (it
filled an outside liberty, allowing opponent to make seki). if gnu go
hadn't blundered, the difference would have been 0.0.

finally, the patch solves the position it was intended to solve. see the
attached sgf file, move 265. patched version prefers R5 to S8, saving
one point. certainly there are more severe mistakes in the game (some
recent cvs vs. 3.2), but i knew how to fix this particular one :)

Paul


p.s. i had to merge the patch with current gnu go source code, hopefully
     i didn't break anything (at least the passes are still there). i
     took back the changes in indentation of case labels in
     reevaluate_ko_threats() made by Gunnar since it seems more consistent
     with the rest of the code.


Index: engine/value_moves.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/value_moves.c,v
retrieving revision 1.95
diff -u -p -r1.95 value_moves.c
--- engine/value_moves.c        29 May 2003 04:13:47 -0000      1.95
+++ engine/value_moves.c        2 Jun 2003 20:32:09 -0000
@@ -2862,7 +2862,7 @@ remove_top_move(int move)
  * ko capture.
  */
 static void
-reevaluate_ko_threats(int ko_move, int color)
+reevaluate_ko_threats(int ko_move, int color, float ko_value)
 {
   int ko_stone = NO_MOVE;
   int opp_ko_move;
@@ -2871,6 +2871,9 @@ reevaluate_ko_threats(int ko_move, int c
   int type, what;
   int threat_does_work = 0;
   int ko_move_target;
+  int num_good_threats = 0;
+  int good_threats[BOARDMAX];
+  int best_threat_quality = -1;
   float threat_size;
 
   ko_move_target = get_biggest_owl_target(ko_move);
@@ -2885,6 +2888,8 @@ reevaluate_ko_threats(int ko_move, int c
   
   TRACE("Reevaluating ko threats.\n");
   for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
+    int threat_quality = 0;
+
     if (!ON_BOARD(pos) || pos == ko_move)
       continue;
     if (move[pos].additional_ko_value <= 0.0) 
@@ -2893,6 +2898,14 @@ reevaluate_ko_threats(int ko_move, int c
     /* Otherwise we look for the biggest threat, and then check whether
      * it still works after ko has been resolved.
      */
+
+    /* `additional_ko_value' includes reverse followup. While it is good to
+     * play ko threats which eliminate other threats in turn, we should
+     * always prefer threats that are larger than the value of the ko.
+     */
+    if (move[pos].followup_value < ko_value)
+      threat_quality = -1;
+
     threat_size = 0.0;
     type = -1;
     what = -1;
@@ -2902,33 +2915,34 @@ reevaluate_ko_threats(int ko_move, int c
        break;
       if (!(move_reasons[r].type & THREAT_BIT))
        continue;
+
       switch (move_reasons[r].type) {
-        case ATTACK_THREAT:
-        case DEFEND_THREAT:
-          if (worm[move_reasons[r].what].effective_size
-              > threat_size) {
-            threat_size = worm[move_reasons[r].what].effective_size;
-            type = move_reasons[r].type;
-            what = move_reasons[r].what;
-          }
-          break;
-        case OWL_ATTACK_THREAT:
-        case OWL_DEFEND_THREAT:   
-        case SEMEAI_THREAT:
-          if (dragon[move_reasons[r].what].effective_size
-              > threat_size) {
-            threat_size = dragon[move_reasons[r].what]\
-             .effective_size;
-            type = move_reasons[r].type;
-            what = move_reasons[r].what;
-          }
-          break;
-        default:
-          /* This means probably someone has introduced a new threat type
-           * without adding the corresponding case above.
-           */
-          gg_assert(0);
-          break;
+      case ATTACK_THREAT:
+      case DEFEND_THREAT:
+       if (worm[move_reasons[r].what].effective_size
+           > threat_size) {
+         threat_size = worm[move_reasons[r].what].effective_size;
+         type = move_reasons[r].type;
+         what = move_reasons[r].what;
+       }
+       break;
+      case OWL_ATTACK_THREAT:
+      case OWL_DEFEND_THREAT:   
+      case SEMEAI_THREAT:
+       if (dragon[move_reasons[r].what].effective_size
+           > threat_size) {
+         threat_size = dragon[move_reasons[r].what]\
+           .effective_size;
+         type = move_reasons[r].type;
+         what = move_reasons[r].what;
+       }
+       break;
+      default:
+       /* This means probably someone has introduced a new threat type
+        * without adding the corresponding case above.
+        */
+       gg_assert(0);
+       break;
       }
     } 
     /* If there is no threat recorded, the followup value is probably
@@ -2944,24 +2958,28 @@ reevaluate_ko_threats(int ko_move, int c
        if (!find_defense(ko_stone, &opp_ko_move))
          threat_does_work = 1;
        else {
+         int threat_wastes_point = 0;
+         if (whose_area(OPPOSITE_INFLUENCE(color), pos) != EMPTY)
+           threat_wastes_point = 1;
+
          if (trymove(opp_ko_move, OTHER_COLOR(color),
                      "reevaluate_ko_threats", ko_move, EMPTY, NO_MOVE)) {
            switch (type) {
-              case ATTACK_THREAT:
-                threat_does_work = attack(what, NULL);
-                break;
-              case DEFEND_THREAT:
-                threat_does_work = (board[what] != EMPTY
-                                    && find_defense(what, NULL));
-                break;
-              case OWL_ATTACK_THREAT:
-              case OWL_DEFEND_THREAT:
-                /* Should we call do_owl_attack/defense here?
-                 * Maybe too expensive? For the moment we just assume
-                 * that the attack does not work if it concerns the
-                 * same dragon as ko_move. (Can this really happen?)
-                 */
-                threat_does_work = (ko_move_target != what);
+           case ATTACK_THREAT:
+             threat_does_work = attack(what, NULL);
+             break;
+           case DEFEND_THREAT:
+             threat_does_work = (board[what] != EMPTY
+                                 && find_defense(what, NULL));
+             break;
+           case OWL_ATTACK_THREAT:
+           case OWL_DEFEND_THREAT:
+             /* Should we call do_owl_attack/defense here?
+              * Maybe too expensive? For the moment we just assume
+              * that the attack does not work if it concerns the
+              * same dragon as ko_move. (Can this really happen?)
+              */
+             threat_does_work = (ko_move_target != what);
            }
            popgo();
            
@@ -2974,6 +2992,37 @@ reevaluate_ko_threats(int ko_move, int c
                threat_does_work = 0;
              }
            }
+
+           /* If we are fighting a tiny ko (1 - 2 points only), we pay
+            * extra attention to select threats that don't waste points.
+            * In particular, we don't play threats inside of opponent
+            * territory if they can be averted on a dame intersection.
+            */
+           if (ko_value < 1.0
+               && threat_does_work
+               && threat_quality >= 0
+               && (type == ATTACK_THREAT || type == DEFEND_THREAT)) {
+             int averting_pos;
+
+             if (type == ATTACK_THREAT)
+               find_defense(what, &averting_pos);
+             else
+               attack(what, &averting_pos);
+
+             /* `averting_pos' can be NO_MOVE sometimes, at least when
+              * when the the threat is a threat to attack. It is not
+              * clear what to do in such cases.
+              */
+             if (averting_pos != NO_MOVE) {
+               int averting_wastes_point = 0;
+               if (whose_territory(OPPOSITE_INFLUENCE(color), averting_pos)
+                   != EMPTY)
+                 averting_wastes_point = 1;
+               threat_quality = averting_wastes_point - threat_wastes_point;
+               if (threat_quality < 0)
+                 threat_does_work = 0;
+             }
+           }
          }
        }
        popgo();
@@ -2981,14 +3030,25 @@ reevaluate_ko_threats(int ko_move, int c
     }
     
     if (threat_does_work) {
-      TRACE("%1m: %f + %f = %f\n", pos, move[pos].value,
-           move[pos].additional_ko_value,
-           move[pos].value + move[pos].additional_ko_value);
-      move[pos].value += move[pos].additional_ko_value;
+      if (threat_quality == best_threat_quality)
+       good_threats[num_good_threats++] = pos;
+      else if (threat_quality > best_threat_quality) {
+       best_threat_quality = threat_quality;
+       num_good_threats = 0;
+       good_threats[num_good_threats++] = pos;
+      }
+      else
+       DEBUG(DEBUG_MOVE_REASONS,
+             "%1m: no additional ko value (threat does not work as ko 
threat)\n", pos);
     }
-    else
-      DEBUG(DEBUG_MOVE_REASONS,
-           "%1m: no additional ko value (threat does not work as ko 
threat)\n", pos);
+  }
+
+  for (k = 0; k < num_good_threats; k++) {
+    pos = good_threats[k];
+    TRACE("%1m: %f + %f = %f\n", pos, move[pos].value,
+         move[pos].additional_ko_value,
+         move[pos].value + move[pos].additional_ko_value);
+    move[pos].value += move[pos].additional_ko_value;
   }
 }
 
@@ -3073,7 +3133,7 @@ find_best_move(int *the_move, float *val
      */
     if (bestval > 0.0 && is_illegal_ko_capture(best_move, color)) {
       TRACE("Move at %1m would be an illegal ko capture.\n", best_move);
-      reevaluate_ko_threats(best_move, color);
+      reevaluate_ko_threats(best_move, color, bestval);
       redistribute_points();
       time_report(2, "  reevaluate_ko_threats", NO_MOVE, 1.0);
       ko_values_have_been_added = 1;
Index: interface/gtp_examples/twogtp.py
===================================================================
RCS file: /cvsroot/gnugo/gnugo/interface/gtp_examples/twogtp.py,v
retrieving revision 1.6
diff -u -p -r1.6 twogtp.py
--- interface/gtp_examples/twogtp.py    13 May 2003 17:10:11 -0000      1.6
+++ interface/gtp_examples/twogtp.py    2 Jun 2003 20:32:10 -0000
@@ -470,8 +470,12 @@ class GTP_match:
                print "White:", self.white
            game1.play("")
            result1 = game1.result()[0]
-           plain_result1 = re.search(r"([BW]\+)([0-9]*\.[0-9]*)", result1)
-           result1_float = float(plain_result1.group(2))
+           if result1 != "0":
+               plain_result1 = re.search(r"([BW]\+)([0-9]*\.[0-9]*)", result1)
+               result1_float = float(plain_result1.group(2))
+           else:
+               plain_result1 = re.search(r"(0)", "0")
+               result1_float = 0.0
            if result1[0] == "B":
                result1_float *= -1
            if verbose:
@@ -483,8 +487,13 @@ class GTP_match:
            result2 = game2.result()[1]
            if verbose:
                print "Result:", result2
-           plain_result2 = re.search(r"([BW]\+)([0-9]*\.[0-9]*)", result2)
-           result2_float = float(plain_result2.group(2))
+           if result2 != "0":
+               plain_result2 = re.search(r"([BW]\+)([0-9]*\.[0-9]*)", result2)
+               result2_float = float(plain_result2.group(2))
+           else:
+               plain_result2 = re.search(r"(0)", "0")
+               result2_float = 0.0
+
            if result2[0] == "B":
                result2_float *= -1
            results.append(result1_float - result2_float)

1.sgf
Description: Text document