Re: [computer-go] Data structures for Go

[Peter Drake <drake@xxxxxxxxxx>]

On Wednesday, October 8, 2003, at 12:23  PM, Don Dailey wrote:

> In my program,  I never explicitly "undo" a move, I  simply keep a new
> separate game state copy for each node visited during the search.
Yes, we've done a similar thing in the Orego code so far.  I see this 
as "functional" style, as commonly used in languages such as Scheme and 
ML.

Proponents of functional programming point out that it's often not 
necessary to copy the ENTIRE data structure, as unchanged portions can 
be shared (via pointers to common destinations) with previous versions. 
 For example, a linked list with one new item can consists of a new 
list node containing a pointer to the old list.  This is safe under 
functional programming because data structures, once created, never 
change -- it is as if they were written in pen, or declared "final" in 
Java.

Unfortunately, this approach is not very good for cyclic data 
structures -- those where, from object A, one can follow a series of 
pointers and get back to A.  Go seems to want such structures in 
several cases.  For example, if a chain A contains a list of 
neighboring enemy chains, each of those will have A in its own list of 
neighboring enemy chains.  I'd like to find a way around this problem.

Also, of course, I'd like to avoid recomputing elaborate structures for 
those parts of the board which haven't changed.

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

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