computer-go: Data structures

[Peter Drake <drake@xxxxxxxxxx>]

I've been thinking about data structures for representing the board.  
What are people using?

Possibilities that spring to mind:

1) Bitmaps of the board (e.g., one for black stones, one for white 
stones).  I'm using this in the current version of OreGo, and it's 
definitely sufficient for writing a smart board.  This is easy to 
write, fast, small, and very good for pattern matching.  The downside 
is that higher-level information ("How many liberties does the chain 
including this stone have?") has to be recomputed.

2) A network of point objects.  Each one knows its color, its 
neighbors, and perhaps other information.  This seems best at the 
beginning of the game, where move effects are largely local.

3) A collection of chain objects, perhaps in combination with one of 
the above.  Each chain would know its color, its size, number of 
liberties, neighboring chains, etc.  Without too much work, each chain 
could know if it is unconditionally alive, so it won't be necessary to 
recompute this after each move.  Plenty of other heuristic information 
could be stored with chains in a smart program, and chains could be 
associated with more vague "group" objects.  The downside of this more 
complicated structure is that it may be very difficult to support an 
"undo" operation, which is necessary for any kind of backtracking 
search.

Peter Drake
Assistant Professor of Computer Science
Lewis & Clark College
http://www.lclark.edu/~drake/