Re: Incremental Data Structures

[Tim Klinger <klinger@xxxxxxxxxx>]

At 05:10 AM 8/20/98 +0200, you wrote:
>>>straightforward design and easy to use, but I would think its performance
>>>in a search examining many positions would not be all that good.
>>...
>>meant search specifically in the context of our program, then an answer
>>would require implementing it both ways and comparing.  This isn't
>>something we've done or plan to do.
>
>Why? IMHO here is how you should go about implementing any incremental
>updating or caching algorithm ('the speedup').

>1.Write it without the speedup.
>  [Optional: time it now. Is it slow enough to be worth speeding up?]

>2.Write a second version with the speedup, that also still does it the slow
>way. After every move check that the updated data is exactly the same.
>
>3.Write a third version that just does the speedup.
>
>4.Get a large set of game records, and have each of your three versions play
>every move in every game, with timing. The most important one is the second
>version - it must make it through the entire test set without any
differences.
>  [NB. The way you test of course depends on what you are trying to speed up]
>
>5.Look at the timing and decide if it was really worth it.

Sure.  I didn't mean that it isn't fruitful to compare specific algorithms
in this way.  But, in our scheme the decision about whether or not a data
structure is incrementally updated is made at the class level not the
algorithm level.  For each class the decision is a function of how objects
usually change from move to move and how hard it is to detect a change that
might impact a given object.  For instance, we know that blocks only grow
by playing a move that merges them with other blocks of the same color and
only disappear when captured.  Our experience tells us that most moves do
not affect most blocks and the only moves that do involve an occupancy
change on an adjacent point.  So, we make blocks incremental (revertable).

>Obscure errors seem to appear at the worst
>possible moments...

Usually during an important demo...

Tim