Re: [chessx-developer] First steps in developing a native database

[Michal R. <mr...@kd...>]

Rico Zenklusen,  =C5=9Broda, 19 wrze=C5=9Bnia 2007:

>I think that the main problem when having false hits, is not how they
>enlarge the number of candidate games to look for but that they force
>you to look through all candidate games (including the real hits) which
>is not always necessary when using other types of indices. I also agree
>that finding all hits for a particular position in about a minute is for
>most applications sufficient. When using position searches for the
>implementation of variation trees, it is unfortunately too much.
>Furthermore in the way how I use scid I experienced that position search
>is the operation which causes the most of waiting time. Therefore it
>would be nice to give the option of activating specialized position
>search indices. But I agree that a position search as proposed by
>Richard is much better suited for default use.
I didn't suggest to use algorithm that requires a minute to find position. =
I=20
just said that brute search of all games can be done in less than minute. M=
y=20
tests in Scid showed that is searches some 250.000 of games in a second.
Most positions in database appear less than 1.000 times. So, assuming=20
Richard's algorithm (or anything similar) gives us twice as many false hits=
=20
as correct ones (in reality this is much much less), we have just 3 x 1.000=
=20
games to look for. This is quick enough to be done immediately even on a sl=
ow=20
computer.
Also, this seems a reasonable way in terms of search time/index size ratio.=
=20
You can store whole positions but this will require much more space.

In fact, I think we can assume that even limiting search to 100.000 of game=
s=20
may be enough to make tree fast enough. I will write about this idea in a=20
separate thread.

>If we are really able to search a particular position in some 200.000
>games in a second so narrowing the search should be enough, but I am not
>sure if we can do that. As soon as the core part of the database is
>implemented we can test this.
My tests were based on 3M database in Scid. My results showed 270.000 -=20
350.000 games per second were searched on a 4 years old computer (Athlon=20
2400).

=2D-=20
Michal Rudolf