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.