Re: [gnugo-devel] BUG in board.c in 3.7, but not in 3.6

[Gunnar Farnebäck]

I wrote:
> Lukasz wrote:
> > I think my program generates the bug.
> > Do You think it will be fixed soon?
> 
> This was broken in 3.6 too, but doesn't necessarily end in a crash,
> dependent on the compiler.
> 
> You can work around it yourself by increasing the value of MAX_STRINGS
> in board.h. To avoid being hit by the next limitation (truncating
> search in do_trymove()) you also need some machinery to stop cycling
> around in triple ko. Actually, if you fix that problem you probably
> don't need to increase MAX_STRINGS either.

The patch attached to http://trac.gnugo.org/gnugo/ticket/64, repeated
below, improves the value of MAX_STRINGS, adds assertions to get more
understandable crashes, and documents how high MAX_STRINGS needs to be
set to be on the safe side.

It's less clear that it's worth the memory cost to actually increase
it to a safe level, however.

/Gunnar

Index: engine/board.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/board.c,v
retrieving revision 1.115
diff -u -r1.115 board.c
--- engine/board.c      8 Oct 2005 08:19:42 -0000       1.115
+++ engine/board.c      10 Jan 2006 14:04:04 -0000
@@ -3106,6 +3106,7 @@
       string[next_string].origin = pos;
       string[next_string].mark = 0;
       next_string++;
+      PARANOID1(next_string < MAX_STRINGS, pos);
     }
   }
   
@@ -3462,6 +3463,7 @@
   /* Get the next free string number. */
   PUSH_VALUE(next_string);
   s = next_string++;
+  PARANOID1(s < MAX_STRINGS, pos);
   string_number[pos] = s;
   /* Set up a size one cycle for the string. */
   next_stone[pos] = pos;
Index: engine/board.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/board.h,v
retrieving revision 1.29
diff -u -r1.29 board.h
--- engine/board.h      8 Oct 2005 08:19:42 -0000       1.29
+++ engine/board.h      10 Jan 2006 14:04:04 -0000
@@ -47,14 +47,26 @@
 #define MAX_LIBERTIES 8
 
 
-/* This is an upper bound of the number of strings that can exist on
- * the board simultaneously.  
- * FIXME: This is not sufficiently large;  above stackp==0, the incremental 
- *   board code doesn't necessarily re-use all indices.  This is a problem
- *   only in very pathological cases, and is extremely unlikely to occur in
- *   practice.
+/* This is an upper bound on the number of strings that can exist on
+ * the board simultaneously. Since each string must have at least one
+ * liberty and each empty point can provide a liberty to at most four
+ * strings, at least one out of five board points must be empty.
+ *
+ * FIXME: This is not sufficiently large. Above stackp==0, the
+ *        incremental board code doesn't re-use the entries for
+ *        removed or merged strings, while new strings require new
+ *        entries. This is a problem only in very pathological cases,
+ *        and is extremely unlikely to occur in practice.
+ *
+ *        Actually, in the not all that pathological case of a
+ *        repeated triple ko cycle, each move creates a new string and
+ *        thus makes use of one more string, which relatively quickly
+ *        will exhaust the available strings. For a safe upper bound
+ *        MAX_STRINGS should be set to
+ *        MAX_STACK + 4 * MAX_BOARD * MAX_BOARD / 5.
+ *        It's not clear that it's worth the extra memory, however.
  */
-#define MAX_STRINGS (2 * MAX_BOARD * MAX_BOARD / 3)
+#define MAX_STRINGS (4 * MAX_BOARD * MAX_BOARD / 5)
 
 /* Per gf: Unconditional_life() can get very close to filling the 
  * entire board under certain circumstances. This was discussed in