Author: Eugene Nalimov
Date: 19:27:41 01/29/04
Go up one level in this thread
On January 29, 2004 at 22:19:53, Ed Trice wrote: > >> >>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. It looks that our approach is better :-) All 5-men TBs (more than 30Gb positions) are compressed into ~7.5Gb. No binary searches on probing are necessary, too. Andrew Kadatch wrote good compression/decompression code. Make the simple experiment: uncompress on of your tables, and compress it using DATACOMP.EXE (which is used to compress our TBs). Thanks, Eugene
This page took 0 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.