Re: [computer-go] Data structures for Go

[Gunnar Farnebäck <gunnar@xxxxxxxxxxxxxx>]

Arend wrote:
> This is mostly incorrect.

Yes, Heikki seems to be a couple of years out of date.

> In GNU Go, the following data structures are
> kept updated at every move (regardless of which search routine is trying
> the move):
> - For every stone:
>   - The "origin" of the string it belongs to, plus an ID identifying the
>     string.
>   - A pointer to the "next stone" in the string

I might clarify that this is not a pointer in the C sense. Instead we
have a fixed size array of ints, each of which gives the board index
to the "next stone" in the string.

The result is a cyclic representation which allows quick traversal and
simple concatenation.

> - For each string:
>   - Its size.
>   - The number and a list of liberties.

To save memory the list of liberties is truncated if there are more
than 20 of them. This introduces some complexity that isn't strictly
necessary but since such strings are fairly rare in practice (except
when analyzing unconditional status) the performance impact is
limited and we consider the memory savings worthwhile.

>   - The number and list of direct neighboring strings.
> - A (currently 64bit) hash value.
> 
> These are stored in arrays handled manually by pure C.
> 
> They are updated incrementally, and every value that changes is recorded
> (by memory address and old value) in a stack, and is manually set back
> to its old value when a move is undone.
> 
> Of course, you can all go and read it yourself in the sources, the code
> is in engine/board.c, the "change record" is handled with the PUSH_VALUE()
> and POP_MOVE() macros.

I think it's worth showing the relevant macros:

/* Begin a record : adress == NULL */
#define BEGIN_CHANGE_RECORD()\
(change_stack_pointer++)->address = NULL

/* Save a value : store the adress and the value in the stack */
#define PUSH_VALUE(v)\
(change_stack_pointer->address = &(v),\
 (change_stack_pointer++)->value = (v))

#define POP_MOVE()\
  while ((--change_stack_pointer)->address)\
  *(change_stack_pointer->address) =\
  change_stack_pointer->value

Thus when you start making a move you use BEGIN_CHANGE_RECORD, every
time you do a destructive change (which needs undoing) you first use
PUSH_VALUE. Undoing the move is then just a simple call to POP_MOVE.

(If you look in the code you'll find that there are actually two
different stacks because we need to handle data of two different C
types.)

> It may sound crude but is actually elegant to use.

The important point is that it completely does away with all potential
complexities associated with undoing a move. Frankly I don't see a
need for any other undo machinery for incrementally updated data
structures. Full copy is of course an alternative if you're changing a
large fraction of your data but in that case I wouldn't really call it
incrementally updated.

> [I should add that this was all present already when I joined the
> project, so I am not praising my own work :).]

The undo machinery was introduced into GNU Go by Tanguy Urvoy. The
rest of the design and original implementation of the board code was
done by me. 

> Everyone who has no problems applying the GPL to his code is of course
> invited to reuse this code in his own engine. Using recent development
> versions, this should be easy to do by including engine/board.h. As this
> part of GNU Go is (IMHO) pretty well optimized, we think it might be
> generally useful.

Just don't expect it to be small and simple. :-)

Also it's optimized for quick access to liberties and neighbor
strings, so if you for some reason don't make frequent use of such
information a simpler board implementation may very well be faster.

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