[gnugo-devel] Unconditional safety search

[Gunnar Farnebäck]

In the testcase endgame:1010, the position is this:

   A B C D E F G H J
 9 . . . . . . . . . 9
 8 . O O O O O O . . 8
 7 . X O X X X O O . 7
 6 . X X . . X X O O 6
 5 . . . . + . . X X 5
 4 . . . . . . X X X 4
 3 . . + X X X X O O 3
 2 . . . X O O O O . 2
 1 . . . X O . . . . 1
   A B C D E F G H J

White fails to play A7 and instead plays A8 because the B8 dragon is
considered somewhat unsafe and A8 is supposed to be a safer move. This
is of course nonsensical but it's not all that easy to solve in a good
way. The problem with the safety estimation is that it's based only on
eyespace properties and it's difficult to make those heuristics both
sharp and robust. On average there's less to lose by underestimating
safety than by overestimating it but in this position it's a mistake.

In the appended patch (see also
http://trac.gnugo.org/gnugo/ticket/215) a step towards solving this is
taken by introducing a new reading paradigm, unconditional safety
search. This is intended to read until a dragon is either captured or
becomes unconditionally alive (see engine/unconditional.c). It's also
supposed not to be selective but really try all local moves. In
sufficiently complex positions it will certainly run out of nodes, in
which case safety will not be declared. But if it can determine that
the opponent has no way to stop the dragon from becoming
unconditionally alive, that should really be the case, and we could
robustly overrule the eyespace based safety estimation.

In this initial implementation the search is very crude and
inefficient, and can only be run through the new GTP command
static_safety. Try e.g. "static_safety E2" in the position above. In
contrast to traditional reading in GNU Go it's not done by depth first
search but with width first search, aiming to try proof number
search. To see more of the search tree you can run these GTP
commands:

loadsgf regression/games/endgame15.sgf
start_sgftrace
static_safety E2
finish_sgftrace vars.sgf

Have fun trying it out.

/Gunnar

diff --git a/engine/liberty.h b/engine/liberty.h
index 05edaf3..6249af2 100644
--- a/engine/liberty.h
+++ b/engine/liberty.h
@@ -447,6 +447,7 @@ void find_unconditionally_meaningless_moves(int 
unconditional_territory[BOARDMAX
 int unconditionally_meaningless_move(int pos, int color,
                                     int *replacement_move);
 void unconditional_move_reasons(int color);
+int static_safety(int d);

 void find_superstring(int str, int *num_stones, int *stones);
 void find_superstring_conservative(int str, int *num_stones, int *stones);
diff --git a/engine/unconditional.c b/engine/unconditional.c
index 3f35cd1..2f05393 100644
--- a/engine/unconditional.c
+++ b/engine/unconditional.c
@@ -697,6 +697,291 @@ unconditional_move_reasons(int color)
     }
 }

+
+/************ Unconditional Safety Search ****************/
+
+/* FIXME: Move this code to a file of its own. */
+
+/* FIXME: Dynamic size/allocation of unconditional safety search tree. */
+#define MAX_USS_NODES 10000
+
+/* Node struct for unconditional safety search (uss). */
+/* FIXME: More efficient storage of children. */
+struct uss_node {
+  int solved;                                /* Node is solved. */
+  int value;                                 /* Safe or unsafe when 
solved. */
+  short child_moves[MAX_BOARD * MAX_BOARD];
+  int child_nodes[MAX_BOARD * MAX_BOARD];
+  int num_children;
+};
+
+/* Tree struct for unconditional safety search (uss). */
+/* FIXME: Add hashtable to detect and join transpositions. */
+struct uss_tree {
+  struct uss_node nodes[MAX_USS_NODES];
+  short moves_of_interest[MAX_BOARD * MAX_BOARD];
+  int num_moves_of_interest;
+  int next_node;
+  int color;
+  int target;
+};
+
+/* Global search tree. */
+static struct uss_tree tree;
+
+/* Find an existing node or make a new one. */
+/* FIXME: Transposition detection would go here. */
+static int
+uss_find_node(struct uss_tree *tree, int color)
+{
+  int k;
+  int unconditional_territory[BOARDMAX];
+  int move;
+  int node = tree->next_node;
+  SGFTree *save_sgf_dumptree = sgf_dumptree;
+  int save_count_variations = count_variations;
+  tree->next_node++;
+
+  /* Not solved yet. */
+  tree->nodes[node].solved = 0;
+  tree->nodes[node].value = 0;
+
+  if (board[tree->target] == EMPTY) {
+    /* The dragon origin has been captured, give up any hope that the
+     * dragon is safe.
+     */
+    tree->nodes[node].solved = 1;
+    tree->nodes[node].value = 0;
+  }
+  else {
+    /* Check whether the dragon has become unconditionally alive. Turn
+     * off sgf traces so that sgf output for the unconditional safety
+     * search becomes sane.
+     */
+    sgf_dumptree = NULL;
+    count_variations = 0;
+    unconditional_life(unconditional_territory, tree->color);
+    sgf_dumptree = save_sgf_dumptree;
+    count_variations = save_count_variations;
+
+    if (unconditional_territory[tree->target] > 0) {
+      /* Dragon is safe. */
+      tree->nodes[node].solved = 1;
+      tree->nodes[node].value = 1;
+    }
+  }
+
+  /* Find child moves. */
+  tree->nodes[node].num_children = 0;
+  for (k = 0; k < tree->num_moves_of_interest; k++) {
+    move = tree->moves_of_interest[k];
+    if (board[move] == EMPTY
+       && is_legal(move, color)) {
+      tree->nodes[node].child_moves[tree->nodes[node].num_children] = move;
+      tree->nodes[node].child_nodes[tree->nodes[node].num_children] = 0;
+      tree->nodes[node].num_children++;
+    }
+  }
+
+  /* No legal moves, the opponent wins. */
+  if (tree->nodes[node].num_children == 0) {
+    tree->nodes[node].solved = 1;
+    tree->nodes[node].value = (color != tree->color);
+  }
+
+  return node;
+}
+
+/* Recursive function to search one line to the bottom. I.e. dragon
+ * becomes unconditionally alive, is captured, or no more moves.
+ */
+static void
+do_safety_search(struct uss_tree *tree, int node, int color)
+{
+  int k;
+  int best_child = -1;
+  int success;
+  int move;
+  int unsolved_child_found = 0;
+  int safe_child_found = 0;
+  int unsafe_child_found = 0;
+
+  struct uss_node *n = &tree->nodes[node];
+  if (n->solved)
+    return;
+
+  /* Choose a child to explore. First take any unexplored child, if
+   * none repeat search of a non-solved one.
+   */
+  /* FIXME: Add intelligent move ordering! */
+  for (k = 0; k < n->num_children; k++) {
+    if (n->child_nodes[k] == 0) {
+      best_child = k;
+      break;
+    }
+
+    if (best_child == -1 && !tree->nodes[n->child_nodes[k]].solved)
+      best_child = k;
+  }
+
+  /* There has to be a move, otherwise the node would already have
+   * been solved.
+   */
+  gg_assert(best_child >= 0);
+
+  /* Make the move. */
+  /* FIXME: The attacker should be allowed to break ko rules, but not
+   * the defender.
+   */
+  move = n->child_moves[best_child];
+  success = trymove(move, color, "do_safety_search", move);
+  gg_assert(success);
+
+  /* If not previously explored, find and record the new node. */
+  if (!n->child_nodes[best_child]) {
+    n->child_nodes[best_child] = uss_find_node(tree, OTHER_COLOR(color));
+  }
+
+  /* If we're not out of nodes, recurse. */
+  if (tree->next_node < MAX_USS_NODES)
+    do_safety_search(tree, n->child_nodes[best_child], OTHER_COLOR(color));
+  popgo();
+
+  /* Examine status of child nodes. */
+  for (k = 0; k < n->num_children; k++) {
+    if (n->child_nodes[k] == 0)
+      unsolved_child_found = 1;
+    else if (!tree->nodes[n->child_nodes[k]].solved)
+      unsolved_child_found = 1;
+    else if (tree->nodes[n->child_nodes[k]].value == 1)
+      safe_child_found = 1;
+    else
+      unsafe_child_found = 1;
+  }
+
+  /* Update solvedness status of this node. */
+  if (color == tree->color) {
+    if (safe_child_found) {
+      n->solved = 1;
+      n->value = 1;
+    }
+    else if (!unsolved_child_found) {
+      n->solved = 1;
+      n->value = 0;
+    }
+  }
+  else {
+    if (unsafe_child_found) {
+      n->solved = 1;
+      n->value = 0;
+    }
+    else if (!unsolved_child_found) {
+      n->solved = 1;
+      n->value = 1;
+    }
+  }
+}
+
+/* Top level call for unconditional safety search. Node 0 is the base
+ * position.
+ */
+static int
+safety_search(struct uss_tree *tree, int color)
+{
+  uss_find_node(tree, color);
+  while (tree->next_node < MAX_USS_NODES && !tree->nodes[0].solved) {
+    do_safety_search(tree, 0, color);
+  }
+
+  gprintf("Static safety search used %d nodes.\n", tree->next_node);
+
+  return tree->nodes[0].value;
+}
+
+/* Determine static safety of a dragon. This is a rather conservative
+ * estimation of safety but should be quite reliable when safety is
+ * declared. Use unconditional safety search to determine the safety
+ * of the dragon.
+ */
+int
+static_safety(int d)
+{
+  int color = board[d];
+  int eyespaces[BOARDMAX];
+  int pos;
+  int dr;
+
+  memset(eyespaces, 0, sizeof(eyespaces));
+
+  d = dragon[d].origin;
+
+  /* Set up unconditional search tree. */
+  tree.next_node = 0;
+  tree.num_moves_of_interest = 0;
+  tree.target = d;
+  tree.color = color;
+
+  /* Find search area as surrounding eyes and the stones of the dragon. */
+  /* FIXME: This probably isn't quite enough, e.g. lunches should also
+   * be included and likely outer liberties.
+   */
+  if (color == BLACK) {
+    for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
+      if (!ON_BOARD(pos))
+       continue;
+
+      if (black_eye[pos].color == BLACK
+         && black_eye[pos].origin == pos
+         && find_eye_dragons(pos, black_eye, BLACK, &dr, 1) == 1
+         && is_same_dragon(dr, d)) {
+       eyespaces[pos] = 1;
+      }
+    }
+  }
+  else {
+    for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
+      if (!ON_BOARD(pos))
+       continue;
+
+      if (white_eye[pos].color == WHITE
+         && white_eye[pos].origin == pos
+         && find_eye_dragons(pos, white_eye, WHITE, &dr, 1) == 1
+         && is_same_dragon(dr, d)) {
+       eyespaces[pos] = 1;
+      }
+    }
+  }
+
+  for (pos = BOARDMIN; pos < BOARDMAX; pos++) {
+    if (!ON_BOARD(pos))
+      continue;
+    if ((color == BLACK
+        && black_eye[pos].color == BLACK
+        && eyespaces[black_eye[pos].origin])
+       || (color == WHITE
+           && white_eye[pos].color == WHITE
+           && eyespaces[white_eye[pos].origin])) {
+      tree.moves_of_interest[tree.num_moves_of_interest++] = pos;
+    }
+    if (board[pos] == color
+       && dragon[pos].origin == d) {
+      tree.moves_of_interest[tree.num_moves_of_interest++] = pos;
+    }
+  }
+
+  if (1) {
+    int k;
+    gprintf("Moves of interest: ");
+    for (k = 0; k < tree.num_moves_of_interest; k++)
+      gprintf("%1m ", tree.moves_of_interest[k]);
+    gprintf("\n");
+  }
+
+  /* Perform the unconditional safety search. */
+  return safety_search(&tree, OTHER_COLOR(color));
+}
+
+
 /*
  * Local Variables:
  * tab-width: 8
diff --git a/interface/play_gtp.c b/interface/play_gtp.c
index 8e33963..3705ead 100644
--- a/interface/play_gtp.c
+++ b/interface/play_gtp.c
@@ -165,6 +165,7 @@ DECLARE(gtp_set_search_diamond);
 DECLARE(gtp_set_search_limit);
 DECLARE(gtp_showboard);
 DECLARE(gtp_start_sgftrace);
+DECLARE(gtp_static_safety);
 DECLARE(gtp_surround_map);
 DECLARE(gtp_tactical_analyze_semeai);
 DECLARE(gtp_test_eyeshape);
@@ -305,6 +306,7 @@ static struct gtp_command commands[] = {
   {"set_search_limit",        gtp_set_search_limit},
   {"showboard",                    gtp_showboard},
   {"start_sgftrace",               gtp_start_sgftrace},
+  {"static_safety",                gtp_static_safety},
   {"surround_map",            gtp_surround_map},
   {"tactical_analyze_semeai", gtp_tactical_analyze_semeai},
   {"test_eyeshape",           gtp_test_eyeshape},
@@ -2374,6 +2376,35 @@ gtp_unconditional_status(char *s)
 }


+/************************
+ * Static safety        *
+ ************************/
+
+/* Function:  Determine the static safety of a dragon
+ * Arguments: vertex
+ * Fails:     invalid vertex, empty vertex
+ * Returns:   1 if dragon is statically safe and 0 if not.
+ */
+
+static int
+gtp_static_safety(char *s)
+{
+  int i, j;
+  int safe;
+
+  if (!gtp_decode_coord(s, &i, &j))
+    return gtp_failure("invalid coordinate");
+
+  if (board[POS(i, j)] == EMPTY)
+    return gtp_failure("empty coordinate");
+
+  silent_examine_position(EXAMINE_DRAGONS);
+  safe = static_safety(POS(i, j));
+
+  return gtp_success("%d", safe);
+}
+
+
 /***********************
  * combination attacks *
  ***********************/