Re: [computer-go] Data structures for Go

[Arend Bayer <arend.bayer@xxxxxx>]

On Wed, 8 Oct 2003, Heikki Levanto wrote:

> On Wed, Oct 08, 2003 at 01:20:12PM -0500, Richard Brown wrote:
> > Here's a vote for linked lists of points.  [...]
>
> Here is a different vote. In Gnu Go we keep things in arrays. Used to be
> 2-D arrays to reflect the board, but we optimized that into 1-D arrays.
> Mostly to save time in passing coordinates as parameters.
>
> We do not do much of undo in our reading, rather we push the whole
> structure into a stack, and instead of undoing, we merely pop it back.
>
> This works quite nicely and effectively.

This is mostly incorrect. 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
- For each string:
  - Its size.
  - The number and a list of liberties.
  - 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. It may sound crude but is actually elegant to
use. [I should add that this was all present already when I joined the
project, so I am not praising my own work :).]

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.

Regards,
Arend


-- 
Arend Bayer, Flodelingsweg 27a, 53121 Bonn, 0228-9813803
arend.bayer@xxxxxxxxxxxxxxxxx

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