Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Tablebase Space Indexing Improvement?

Author: Ed Trice

Date: 19:19:53 01/29/04

Go up one level in this thread



>
>You just say about encoding but not mention about finding out a position. That
>may be nightmare for your method. As I understand, instead of accessing ramdomly
>any position in database (by few seeking and reading), your method requires to
>read all positions from begining (too many) to get all run length codes and
>compute where the position exactly is.

No, this is actually easy (remember I have done this already for very large
databases with over 100 billion positions already. See
http://www.GothicChess.org/papers.html for more information about it)

What you do is write 4000 bytes to a "disk block" and store the index for the
last entry in a block. So, you have Block 0 for indices 0 to say 14,212, then
Block 1 stores indices 14,213 to 29,682....etc.

You create a file that stores the indices for each block. You convert your
position that you are looking for into an index number. Then you binary search
the block numbers to determine which block you need.

Once you have accecssed the block, you know your index is within the 4000 bytes
of the block. Sparing all of the optimization details (you can store indices
every 128 bytes within each block, and do a binary search on them to really
narrow down your index) you then decompress the data in the block.

You read a byte, and decompress it.

If the value > 58, you know it is a runlength. Determine the run length, then
add this to whatever index you are looking at.

Is your new incremented index >= the index you seek?

If no, you keep looking. If yes, you find your result.

I know this can be down since I have a checkers database that can announce a win
from a distance of 253 plies. With over 21 billion entries encoded in 8 GB
(remember this is distance to mate which is usually 1 bytes per entry without
compressing well) it works fine.




This page took 0.04 seconds to execute

Last modified: Thu, 15 Apr 21 08:11:13 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.