Author: Dave Gomboc
Date: 10:30:42 02/27/99
Go up one level in this thread
On February 26, 1999 at 14:02:28, Dann Corbit wrote: >I have a notion about hashing I thought I might toss out. > >If you took (say) a 20 bit hash to create a million element table, those table >entries could be LRU caches instead of just lists. Each LRU cache would keep >the hottest entries on top, and the old ones would get flushed to disk. My >notion is to create a permanent hash file of (x) terabytes. I know that >conceivably, it would rapidly grow to infinite size. I doubt if that is >practially the case, however, since the real number of chess positions examined >in games is definitely very finite. > >Dumb idea? I know disk is thousands of times slower than ram, but if cache hits >were high it seems it might be a good idea [probably need a few hundred megs of >physical ram to make it practical]. Basically, you would never have a hash >collision. Either the position is there calculated already or it is not, and if >not, then you calc it and save it. I don't see a need for closed addressing (that is, more than one hash entry per slot). If you are using a 64-bit encoding for a chess state, then as long as you're not approaching 2^64 entries, just use open addressing. If you are approaching that, use a bigger (e.g. 128-bit) encoding. Unless, of course, there is some particular advantage of closed addressing that I'm missing. If there are fixed maximum sizes on the buckets, you're not doing better than open addressing anyway, and if there aren't, you're probably wasting much of the memory for pointers from entry to entry, and again open addressing would do better. BTW, if you're doing this on NT, NT 5 supports sparse files. You could make a big file, say 2^128 entries, and NT will (with some overhead, of course) only store the parts with real data in them. Now you can just index directly by your encoding, and your disk space isn't all eaten up right at the beginning. I don't know if there's a UNIX equivalent to this or not. Dave Gomboc
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.