Re: Incremental Data Structures

[David Mechner <mechner@xxxxxxxxxxxxxxxxx>]

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.  

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. 

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. 

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/