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

[Arend Bayer <arend.bayer@xxxxxx>]

On Sat, 14 May 2005, Peter Drake wrote:

> 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?

No. 1 is clearly better for speed (it's not only the saved memcpy(),
which is fast, but also much better processor cache behaviour).

Gunnar and me have described before on this list how 1) is implemented in
GNU Go: keeping an array of (pointer, old value)-pairs of all values that
got changed in the course of incrementally updating the board data. You
should be able to find in the archive of this list.

Arend

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