Re: Incremental Data Structures

[Darren Cook <darren@xxxxxxxxxxxxxx>]

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


Generally I've found a handful of obscure errors when running the second
version, that otherwise would not have been found. I remember Micheal Reiss
saying that Go4++ lost a game to Go Intellect in last years FOST Cup because
it mistakenly used old data. Obscure errors seem to appear at the worst
possible moments...

Also, your intuition can easily be wrong. A few weeks back I was trying to
speed up a tactical search routine by having it cache results at the top
plys. I was expecting at least a 50% speed increase, and instead got a 10%
slowdown. Further investigation found that extra caching gave a 10% speedup
but the overhead made it 20% slower.

One more reason to time and compare: when you manage to get a large speedup
in bottleneck code it feels great - at last you have concrete proof that
you're a brilliant programmer ;-).

Darren