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

[Don Dailey <drd@xxxxxxx>]

Hi Peter,

If the amount of work your program does making a move is significant
(you have a fairly complex data structure), then you should seriously
consider making your life simple, just copy state and apply a move to
the next state.  It will save you a lot of time debugging and free you
up greatly to experiment.

If your program is of the style where it needs to very rapidly
traverse the game tree, then you will probably have to have a very
simple data structure that is incrementally updated and downdated to a
global board.

Apparently Dave Fotland (from his post) uses both methods.

Stuart Yeates suggested a hybrid approach which is interesting, but
will no doubt cause some debugging nightmares if you are not careful.
If you have good bookeeping skills, you can have great fun with
pointers to the parts of the data structure that do not change.

- Don




   From: Peter Drake <drake@xxxxxxxxxxxxxxxxx>
   Date: Sat, 14 May 2005 20:10:42 -0700

   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/