[computer-go] Chains and liberties - performance

[Arend Bayer <arend.bayer@xxxxxx>]

On Sun, 14 Nov 2004, Mark Boon wrote:

> I've done a quick implementation along the lines I described. I found that
> along with the marking of the merged chain in the chain array, all I need to
> do is adding those same points to an array of integers. Although it has to
> do this for all stones in the chain, I don't see how keeping cyclic lists is
> going to beat that. I may be wrong of course. (And I have somehow gotten to
> hate making linked-lists, so I suppose I'm a bit biased here.)

> I'm not too enthousiastic about the speed. A quick test seemed to point to a
> little over 0.5 million moves per second, including taking back those same
> moves. 2 uSec per move doesn't compare too well with my ladder-module, which
> is more than twice the speed and does a whole lot more. So using it for
> ladders is not an option. But maybe for the other tactial readers and
> life-and-death it is, provided I can optimize the current implementation
> still.

Just as a data point:
For a life and death test set (owl.tst) of GNU Go, I get 296000 moves
per second. According to a profile run, gnugo spends 14.2 % of that time
updating the board data, and 3.3% in the undo function. So that would be
1.7 Million moves per second for the board library alone.
This is on a Pentium M 1.4GHz (appr. as fast as a Pentium 2.4GHz on
usual benchmarks, but I dont know about gnugo).

Here is the data it keeps track of in this time:

/* Incremental string data. */
(Only one copy for each string.)
struct string_data {
  int color;                       /* Color of string, BLACK or WHITE */
  int size;                        /* Number of stones in string. */
  int origin;                      /* Coordinates of "origin", i.e. */
                                   /* "upper left" stone. */
  int liberties;                   /* Number of liberties. */
  int libs[MAX_LIBERTIES];         /* Coordinates of liberties. */
  int neighbors;                   /* Number of neighbor strings */
  int neighborlist[MAXCHAIN];      /* List of neighbor string numbers.  */
};

static int string_number[BOARDMAX];
(The id of each string for each board positioin to refer to the data
above.)

static int next_stone[BOARDMAX];
(The circular list to traverse a string that Gunnar talked about.)

Plus of course some (cheap) global data (ko position, "komaster" state,
64bit hash value, # of captured stones).


Arend

_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/