Re: [gnugo-devel] CGF games

[Gunnar Farneback]

Dan forwarded a message from Hiroshi Yamashita:
> Ando-kun Igo played mirror Go.
> GnuGo vs. Ando was very interesting game.

GNU Go was black and white played mirror go all the way to move 205,
when black finally played tengen and broke the symmetry. However, GNU
Go was kind of lucky to play tengen with profit (in this case it won a
semeai). It could very well have happened that tengen had ended up as
dame, giving an equal score on the board and a white win by komi.

To test this hypothesis I have implemented a --mirror option for GNU
Go and played a series of 50 games where white plays mirror go as long
as it can. Komi is the default 5.5. The results are very clear: white
won 36 games or 72%. The conclusion is that we need to implement some
anti-mirror strategies, the easiest and most important of which is to
play tengen sometime early when white is mirroring in an even game.

Detailed results:
Game 1: W+5.5
Game 2: B+37.5
Game 3: W+1.5
Game 4: W+5.5
Game 5: W+4.5
Game 6: W+1.5
Game 7: W+4.5
Game 8: W+9.5
Game 9: B+32.5
Game 10: W+3.5
Game 11: W+1.5
Game 12: W+5.5
Game 13: B+19.5
Game 14: W+9.5
Game 15: W+3.5
Game 16: B+3.5
Game 17: B+1.5
Game 18: B+5.5
Game 19: W+5.5
Game 20: W+5.5
Game 21: W+9.5
Game 22: B+5.5
Game 23: W+3.5
Game 24: W+2.5
Game 25: B+11.5
Game 26: W+2.5
Game 27: W+4.5
Game 28: B+0.5
Game 29: W+5.5
Game 30: W+4.5
Game 31: W+4.5
Game 32: W+1.5
Game 33: W+21.5
Game 34: W+4.5
Game 35: B+25.5
Game 36: B+1.5
Game 37: W+5.5
Game 38: W+7.5
Game 39: W+4.5
Game 40: B+21.5
Game 41: W+0.5
Game 42: W+10.5
Game 43: W+5.5
Game 44: W+5.5
Game 45: W+5.5
Game 46: W+2.5
Game 47: B+2.5
Game 48: W+4.5
Game 49: B+0.5
Game 50: W+0.5

Below follows the patch implementing the --mirror option. There's a
companion option --mirror-limit which takes as argument the maximum
number of stones on the board before mirroring is disabled. This is
potentially useful for playing a mirror go fuseki. Whenever symmetry
is destroyed so that mirroring can't continue, the option is
automatically disabled.

- new options --mirror and --mirror-limit
- new global variables play_mirror_go and mirror_stones_limit
- new static functions find_mirror_move() and
  test_symmetry_after_move() in genmove.c

/Gunnar

Index: engine/genmove.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/genmove.c,v
retrieving revision 1.46
diff -u -r1.46 genmove.c
--- engine/genmove.c    18 Aug 2002 02:56:40 -0000      1.46
+++ engine/genmove.c    27 Aug 2002 20:23:07 -0000
@@ -54,6 +54,9 @@
 static int revise_semeai(int color);
 static int revise_thrashing_dragon(int color, float advantage);
 
+static int find_mirror_move(int *move, int color);
+static int test_symmetry_after_move(int move, int color);
+
 void sgfShowConsideredMoves(void);
 
 
@@ -346,6 +349,15 @@
   /* Prepare pattern matcher and reading code. */
   reset_engine();
 
+  /* If in mirror mode, try to find a mirror move. */
+  if (play_mirror_go
+      && (mirror_stones_limit < 0
+         || stones_on_board(WHITE | BLACK) <= mirror_stones_limit)
+      && find_mirror_move(move, color)) {
+    TRACE("genmove() recommends mirror move at %1m\n", *move);
+    return 1.0;
+  }
+
   /* Find out information about the worms and dragons. */
   start_timer(1);
   examine_position(color, EXAMINE_ALL);
@@ -683,6 +695,63 @@
   return 1;
 }
 
+
+/* Look for a mirror move. First try the mirror of the last move. If
+ * none is available, test all moves to see if one makes the board
+ * symmetric.
+ *
+ * To be able to deal with handicap stones we use a somewhat weak
+ * definition of symmetry.
+ */
+#define MIRROR_MOVE(pos) POS(board_size - 1 - I(pos), board_size - 1 - J(pos))
+
+static int
+find_mirror_move(int *move, int color)
+{
+  int last_move = get_last_move();
+  int mirror_move;
+  if (last_move != NO_MOVE) {
+    mirror_move = MIRROR_MOVE(last_move);
+    if (test_symmetry_after_move(mirror_move, color)) {
+      *move = mirror_move;
+      return 1;
+    }
+  }
+  else {
+    for (mirror_move = BOARDMIN; mirror_move < BOARDMAX; mirror_move++) {
+      if (ON_BOARD(mirror_move)
+         && test_symmetry_after_move(mirror_move, color)) {
+       *move = mirror_move;
+       return 1;
+      }
+    }
+  }
+  
+  return 0;
+}
+
+static int
+test_symmetry_after_move(int move, int color)
+{
+  int pos;
+  int result = 1;
+
+  if (board[move] != EMPTY)
+    return 0;
+  if (!trymove(move, color, "find_mirror_move", NO_MOVE, EMPTY, NO_MOVE))
+    return 0;
+  
+  for (pos = BOARDMIN; pos <= MIRROR_MOVE(pos); pos++) {
+    if (!(board[pos] == EMPTY ^ board[MIRROR_MOVE(pos)])) {
+      result = 0;
+      break;
+    }
+  }
+  
+  popgo();
+
+  return result;
+}
 
 /*
  * Local Variables:
Index: engine/globals.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/globals.c,v
retrieving revision 1.25
diff -u -r1.25 globals.c
--- engine/globals.c    29 May 2002 09:26:49 -0000      1.25
+++ engine/globals.c    27 Aug 2002 20:23:07 -0000
@@ -137,6 +137,9 @@
 int capture_all_dead    = 0;    /* capture all dead opponent stones */
 int play_out_aftermath  = 0;    /* make everything unconditionally settled */
 
+int play_mirror_go      = 0;    /* try to play mirror go if possible */
+int mirror_stones_limit = -1;   /* but stop at this number of stones */
+
 float best_move_values[10];
 int   best_moves[10];
 
Index: engine/gnugo.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/gnugo.h,v
retrieving revision 1.60
diff -u -r1.60 gnugo.h
--- engine/gnugo.h      6 Aug 2002 19:04:11 -0000       1.60
+++ engine/gnugo.h      27 Aug 2002 20:23:13 -0000
@@ -268,6 +268,8 @@
 extern int allow_suicide;            /* allow opponent to make suicide moves */
 extern int capture_all_dead;         /* capture all dead opponent stones */
 extern int play_out_aftermath; /* make everything unconditionally settled */
+extern int play_mirror_go;           /* try to play mirror go if possible */
+extern int mirror_stones_limit;      /* but stop at this number of stones */
 
 #if EXPERIMENTAL_READING
 extern int defend_by_pattern;  /* use patterns for tactical reading defense */
Index: interface/main.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/interface/main.c,v
retrieving revision 1.43
diff -u -r1.43 main.c
--- interface/main.c    22 Jul 2002 16:49:26 -0000      1.43
+++ interface/main.c    27 Aug 2002 20:23:26 -0000
@@ -126,7 +126,9 @@
       OPT_CAPTURE_ALL_DEAD,
       OPT_PLAY_OUT_AFTERMATH,
       OPT_ATTACK_BY_PATTERN,
-      OPT_DEFEND_BY_PATTERN
+      OPT_DEFEND_BY_PATTERN,
+      OPT_MIRROR,
+      OPT_MIRROR_LIMIT
 };
 
 /* names of playing modes */
@@ -231,13 +233,13 @@
   {"decide-dragon-data",  required_argument, 0, OPT_DECIDE_DRAGON_DATA},
   {"decide-semeai",  required_argument, 0, OPT_DECIDE_SEMEAI},
   {"decide-tactical-semeai", required_argument, 0, OPT_DECIDE_TACTICAL_SEMEAI},
-  {"decide-position", no_argument,       0, OPT_DECIDE_POSITION},
+  {"decide-position", no_argument,      0, OPT_DECIDE_POSITION},
   {"decide-eye",     required_argument, 0, OPT_DECIDE_EYE},
   {"decide-combination", no_argument,   0, OPT_DECIDE_COMBINATION},
   {"life",           no_argument,       0, OPT_LIFE},
   {"life-eyesize",   required_argument, 0, OPT_LIFE_EYESIZE},
   {"nofusekidb",     no_argument,       0, OPT_NOFUSEKIDB},
-  {"nofuseki",       no_argument,         0, OPT_NOFUSEKI},
+  {"nofuseki",       no_argument,       0, OPT_NOFUSEKI},
   {"nojosekidb",     no_argument,       0, OPT_NOJOSEKIDB},
   {"debug-influence", required_argument, 0, OPT_DEBUG_INFLUENCE},
   {"showtime",       no_argument,       0, OPT_SHOWTIME},
@@ -247,6 +249,8 @@
   {"profile-patterns", no_argument,     0, OPT_PROFILE_PATTERNS},
   {"attack-by-pattern", no_argument,    0, OPT_ATTACK_BY_PATTERN},
   {"defend-by-pattern", no_argument,    0, OPT_DEFEND_BY_PATTERN},
+  {"mirror",         no_argument,       0, OPT_MIRROR},
+  {"mirror-limit",   required_argument, 0, OPT_MIRROR_LIMIT},
   {NULL, 0, NULL, 0}
 };
 
@@ -777,6 +781,14 @@
 
 #endif
 
+      case OPT_MIRROR:
+        play_mirror_go = 1;
+        break;
+
+      case OPT_MIRROR_LIMIT:
+        mirror_stones_limit = atoi(gg_optarg);
+        break;
+
       case 'v':
        show_version();
        return EXIT_SUCCESS;
@@ -1258,6 +1270,8 @@
    --nofusekidb            turn off fuseki database\n\
    --nofuseki              turn off fuseki moves entirely\n\
    --nojosekidb            turn off joseki database\n\
+   --mirror                try to play mirror go\n\
+   --mirror-limit <n>      stop mirroring when n stones on board\n\
 Scoring:\n\
    --score estimate        estimate score at loaded position\n\
    --score finish          generate moves to finish game, then score\n\