[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

RE: [computer-go] Core data structures: modify or copy?

I keep one copy of the data that is used for tactical search and needs to be
fast.  This data is local to the last move, so it is easy and fast to
incrementally change it.  The data includes:

Per point: group number, number of adjacent points empty, black, and white,
list of adjacent groups by color,
list of adjacent empty points

Per group (block): color, size, liberty count, list of liberties, list of
adjacent enemy groups

Tactical search has to be as fast as possible, so I prefer incremental.
Full board search is slow, so additional
data used by the full board search can be copied or recreated as needed.

David

> -----Original Message-----
> From: computer-go-bounces@xxxxxxxxxxxxxxxxx 
> [mailto:computer-go-bounces@xxxxxxxxxxxxxxxxx] On Behalf Of Peter Drake
> Sent: Saturday, May 14, 2005 8:11 PM
> To: computer-go@xxxxxxxxxxxxxxxxx
> Subject: [computer-go] Core data structures: modify or copy?
> 
> 
> I'm once again playing with the core data structures in my Go program.
> 
> There must, of course, be a data structure to represent the board.   
> If there is to be any kind of search, there are two options:
> 
> 1) Maintain only one copy of the board, making and undoing all moves  
> here.
> 2) Make a new copy at each node.
> 
> #1 might require some extensive winding and unwinding, especially in  
> a best-first search such as proof-number search.  #2 uses a lot of  
> time copying (or rederiving) information on blocks, liberties, etc.
> 
> Any arguments for one over the other?
> 
> Peter Drake
> Assistant Professor of Computer Science
> Lewis & Clark College
> http://www.lclark.edu/~drake/
> 
> 
> _______________________________________________
> computer-go mailing list
> computer-go@xxxxxxxxxxxxxxxxx 
> http://www.computer-go.org/mailman/listinfo/computer-go/
> 


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