Re: computer-go: Data structures

[David Fotland <fotland@xxxxxxxxxxxxxxx>]

Most people use one dimensional arrays sized with a single unused edge 
around it,
approximately 20x21.  I like Handtalk's approach of storing a chain number, 
with the
LSB of the number being the color of the chain.  Most of the board 
information is
per-chain, and is in the chain object.

Many Faces uses a one dimensional (19x19) array of chain numbers.

Slightly out of date (1993) information on Many Faces' representation is in 
the paper
Knowledge Representation in Many Faces of Go, at
http://www.smart-games.com/knowpap.txt

David

At 09:10 AM 2/21/2003 -0800, Peter Drake wrote:
> 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/