search

benini / scid

Other
44 stars 14 forks source link

[Question] How does the opening tree/explorer work? #153

Closed Pesky01 closed 11 months ago

Pesky01 commented 11 months ago

Tried reading the code but couldn't put it together.

How does scid retrieve all games on my board so fast (~1s) for a 5 million game DB? I thought this would be too compute inefficient but do you iterate over every position of every game but use shortcuts (i.e incompatible irreversible moves/home pawn data) to break early from checking the rest of the game? I thought final material would also be used for shortcut, but since pawns can promote you can't know if that's a early stop?

I also thought it was just a large hash table on-disk, but for that many unique positions it would be very memory inefficient.

benini commented 11 months ago

The database Index is fully loaded into memory and includes three Bloom filters: https://github.com/benini/scid/blob/github/src/searchpos.h#L100 StoredLine uses the first moves of the game. HomePawn take advantage of the fact that pawns can never go back to the intitial rank. FinalMatSig uses the final material. By using these filters, the number of games that need to be read from the disk and searched is greatly reduced.