Re: Incremental Data Structures

["Serge Boisse STNA 7P (33) 562 14 5731" <boisse@xxxxxxxxxxxx>]

David Mechner wrote:
> 
> Each revertable object in our program knows how to store a copy of
> itself, and does so just before it's changed (but at most once each
> turn). To backtrack a move we just copy back the saved versions for that
> turn. We implement the system in C++ with a "Revertable" base class,
> some macros, and an auxilliary list of all the objects that were changed
> each turn. The efficiency of this method over recomputation depends on
> how much state information you keep, and the extent to which it stays
> the same from move to move, which varies from program to program.
> 

I use roughly the same idea in my program "spirit of go", writen in Java (under
developpment, 10000 lines of code written but not completed yet).
The data structures are updated incrementally each time you add or remove a
stone.

I use this for the following :
	- blocks (strings) creation/destruction/update/fusion
	- territories (same operations as with blocks)
	- surrounded areas (areas surrounded by blocks of same color), may
	  include several eyes inside)
	- groups (several savour of them)
	- eyes (true and false)
	- results of simulations (tries to capture frontier blocks of an eye)
	- life/death status of blocks and eyes.

> From-scratch recomputation has the advantage that it adds no complexity
> to the program, and requires no thought to design or implement. it has
> the disadvantage that it subsequently puts constant (and to my mind
> insidious) pressure on you not to try any computationally expensive
> algorithms as part of your state update because you have to throw away
> and redo all that work every time you read or backtrack a move.
> 
Right.

> Incremental update done by storing changes adds substantial complexity
> to the program, and requires a great deal of effort to design and
> implement. It has the advantage that, if done well, is nearly
> transparent and puts no pressure on you to steer clear of complex or
> expensive algorithms, allowing you to concentrate on generating the
> information that you think best allows you to solve problems in go.

Wrong. it is not transparent at all if the structure is complex : for instance
wxhen you add, then remove the same stone, the result will have the same
structure, but the objets might have different names/adress. That is, you cannot
easyly compare an object to an other that results from a search at a
different depth. I solve this by cloning the structure when (and only when) I
need to compare it with something recorded elsewhere. This can be a painstaking
task.  
But averall I agree that incrmental update is better, although you MUST have a
way of fast recovering in case of a crash during play, for instance : I use
the java ability of saving (serializing) objets states on disk for doing this.

> 
> So the best choice for you depends on your goals, on how ambitious your
> project is, on how much state information you're planning to maintain.
> If it's just string lists, liberty lists, etc., go for incremental.
> Efficiency on that level doesn't matter anyway.
> 
> In our program we do very expensive reading to establish the life and
> death status of groups. The plans (to live or kill) that we generate
> this way generally stay the same from move to move so avoiding redoing
> all this work each time we read or backtrack a move seems to justify the
> added complexity of an incremental update (though we haven't done any
> experiments to verify this intuition).
> 
> -David
> 
> --
> David A. Mechner            Center for Neural Science
> mechner@xxxxxxxxxxxxxxxxx         4 Washington Place, New York, NY 10003
> 212.998.3580                http://cns.nyu.edu/~mechner/

-- 
         ______________________
        / Let java be with me !\           \\\|/// 
        \______________________/ O       \\  ^ ^  // 
                                   o o    (  @ @  ) 
 +--------------------------------------oOOo-(_)-oOOo----+
 |  Serge Boisse                                         |
 |  SERVICE TECHNIQUE DE LA NAVIGATION AERIENNE (STNA)   |
 |  PHIDIAS project, http://www.stna.dgac.fr/phidias     |
 |  tel: (33)562 14 5731                                 |
 |  mailto:boisse@xxxxxxxxxxxxxxxxx                           |
 |  homepage:  http://www.mygale.org/~boisse             |
 +-----------------------------------------------Oooo----+ 
                                         oooO   (   ) 
                                         (   )   ) / 
                                          \ (   (_/ 
                                           \_)