[gnugo-devel] semeai patch

[Gunnar Farnebäck]

The function find_moves_to_make_seki() in semeai.c invokes semeai
reading to determine whether tactically critical but owl dead stones
can in fact live in seki.

The appended patch extends this function to also consider tactically
dead stones inside the eye of single-eyed opponent dragons. Regression
results:

13x13:42        PASS N3 [N3|N2|L4|L3|L2|L1|M1|N1|M4]
semeai:115      PASS alive [alive]
century2002:85  FAIL B19 [N9]
century2002:180 PASS T9 [T9]
seki:1106       PASS C1 [C1]
seki:2020       PASS alive [alive]
seki:2050       PASS alive [alive]
olympiad2004:16 PASS A7 [A7|A6|E4|A5]
olympiad2004:17 PASS A7 [A7|A6|E4|A5]
8 PASS
1 FAIL
Total nodes: 1636570142 3025412 12970508 (+1% +1.8% +0.58%)

As discussed in an earlier message century2002:85 is rather a PASS
than a FAIL, although the choice of B19 can be questioned. But that is
in any case a problem with the semeai reading. That this patch causes
the semeai reading to be invoked in the first place is a definite
improvement.

I think olympiad2004:16,17 both pass mostly accidentally but here too
it's an improvement that the semeai reading gets consulted.

The remaining passes are all real and good. Check up some of them if
you want to know more exactly what kind of positions this patch helps
with.

In my opinion this patch is clearly worth the cost in speed.

- find_moves_to_make_seki() extended to examine the case of dead stones
  inside the eye of single-eyed dragons

/Gunnar

Index: engine/semeai.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/semeai.c,v
retrieving revision 1.72
diff -u -r1.72 semeai.c
--- engine/semeai.c     24 Aug 2004 15:24:30 -0000      1.72
+++ engine/semeai.c     22 Sep 2004 15:39:55 -0000
@@ -310,9 +310,110 @@
            }
          }
 
-         /* FIXME: What should we do if none of the tried attacks worked? */
-         if (k == liberties)
-           dragon2[d].semeai_attack_point = defend_move;
+         if (k == liberties) {
+           DEBUG(DEBUG_SEMEAI,
+                 "No move to attack in semeai (%1m vs %1m), seki assumed.\n",
+                 str, opponent);
+           dragon2[d].semeai_attack_point = NO_MOVE;
+           update_status(str, ALIVE, ALIVE_IN_SEKI);
+         }
+       }
+
+       DEBUG(DEBUG_SEMEAI, "Move to prevent seki at %1m (%1m vs %1m)\n",
+             dragon2[d].semeai_attack_point, opponent, str);
+
+       dragon2[d].semeai_attack_certain = certain;
+       dragon2[d].semeai_attack_target = opponent;
+      }
+    }
+  }
+
+  /* Now look for dead strings inside a single eyespace of a living dragon.
+   *
+   * FIXME: Clearly this loop should share most of its code with the
+   *        one above. It would also be good to reimplement so that
+   *        moves invading a previously empty single eyespace to make
+   *        seki can be found.
+   */
+  for (str = BOARDMIN; str < BOARDMAX; str++) {
+    if (IS_STONE(board[str]) && is_worm_origin(str, str)
+       && !find_defense(str, NULL)
+       && dragon[str].status == DEAD
+       && DRAGON2(str).hostile_neighbors == 1) {
+      int k;
+      int color = board[str];
+      int opponent = NO_MOVE;
+      int certain;
+      struct eyevalue reduced_genus;
+
+      for (k = 0; k < DRAGON2(str).neighbors; k++) {
+       opponent = dragon2[DRAGON2(str).adjacent[k]].origin;
+       if (board[opponent] != color)
+         break;
+      }
+
+      ASSERT1(opponent != NO_MOVE, opponent);
+
+      if (dragon[opponent].status != ALIVE)
+       continue;
+
+      /* FIXME: These heuristics are used for optimization.  We don't
+       *        want to call expensive semeai code if the opponent
+       *        dragon has more than one eye elsewhere.  However, the
+       *        heuristics might still need improvement.
+       */
+      compute_dragon_genus(opponent, &reduced_genus, str);
+      if (DRAGON2(opponent).moyo_size > 10 || min_eyes(&reduced_genus) > 1)
+       continue;
+
+      owl_analyze_semeai(str, opponent, &resulta, &resultb,
+                        &defend_move, 1, &certain);
+
+      /* Do not trust uncertain results. In fact it should only take a
+       * few nodes to determine the semeai result, if it is a proper
+       * potential seki position.
+       */
+      if (resulta != 0 && certain) {
+       int d = dragon[str].id;
+       DEBUG(DEBUG_SEMEAI, "Move to make seki at %1m (%1m vs %1m)\n",
+             defend_move, str, opponent);
+       dragon2[d].semeais++;
+       update_status(str, CRITICAL, CRITICAL);
+       dragon2[d].semeai_defense_point = defend_move;
+       dragon2[d].semeai_defense_certain = certain;
+       dragon2[d].semeai_defense_target = opponent;
+
+       /* We need to determine a proper attack move (the one that
+        * prevents seki).  Currently we try the defense move first,
+        * and if it doesn't work -- all liberties of the string.
+        */
+       owl_analyze_semeai_after_move(defend_move, OTHER_COLOR(color),
+                                     str, opponent, &resulta, NULL,
+                                     NULL, 1, NULL, 0);
+       if (resulta != WIN)
+         dragon2[d].semeai_attack_point = defend_move;
+       else {
+         int k;
+         int libs[MAXLIBS];
+         int liberties = findlib(str, MAXLIBS, libs);
+
+         for (k = 0; k < liberties; k++) {
+           owl_analyze_semeai_after_move(libs[k], OTHER_COLOR(color),
+                                         str, opponent, &resulta, NULL,
+                                         NULL, 1, NULL, 0);
+           if (resulta != WIN) {
+             dragon2[d].semeai_attack_point = libs[k];
+             break;
+           }
+         }
+
+         if (k == liberties) {
+           DEBUG(DEBUG_SEMEAI,
+                 "No move to attack in semeai (%1m vs %1m), seki assumed.\n",
+                 str, opponent);
+           dragon2[d].semeai_attack_point = NO_MOVE;
+           update_status(str, ALIVE, ALIVE_IN_SEKI);
+         }
        }
 
        DEBUG(DEBUG_SEMEAI, "Move to prevent seki at %1m (%1m vs %1m)\n",