Author: Dan Newman
Date: 19:02:04 09/21/98
Go up one level in this thread
On September 21, 1998 at 21:18:17, Dan Newman wrote: >On September 21, 1998 at 20:49:18, John Coffey wrote: > >>On September 21, 1998 at 20:32:51, Dan Newman wrote: >> >>>Many of us believe that a two level hash table (each entry having two >>>slots, one always replace, the other replace if the draft (depth searched) >>>is greater) works well on the PC--perhaps better than anything else tried >>>so far... >>> >>>Re-hashing can also work well depending on the architecture of the machine. >>>I think Bob Hyatt has said that Cray Blitz "re-hashes" up to 7x, for >>>instance (he's able to grab all 8 entries in one go). >>> >>>-Dan. >>> >> >>What is meant "re-hashes up to 7x?" > >The idea of re-hashing is that if the entry you were going to store at >is already used, you generate a new hash table index (by some technique) >and look there. If that entry is also used, you can do this again, and >so on. IIRC, Bob has said that Cray Blitz will do this up to 7 times. >One trick for generating new hash table indices is to simply add an >offset to the old one. To reduce the number of colisions by using the >same offset all the time, you can just use a selected chunk of bits from >your hashcode as the offset to add. (I think this is what Bob said he >does in Cray Blitz--and on lookup he can grab all 8 entries at once.) > >> >>Why would the two slot method work best? You would take twice as much space >>and have to look at twice as many entries? What if your dual entries have >>conflicting information for the same nodes? >> Oops, I missed the last two questions. You still get the same number of entries for the same amount of space. There is the extra overhead of looking at two entries when the first entry doesn't match, but that may be offset by the benefit of getting hits that you wouldn't have gotten. If both entries are for the same node I just look at the first (depth replacement) entry. I'm not sure this is the best idea though... -Dan. >>John Coffey > >I think the reasons for a two level hash table are 1) the memory >bandwidth on the PC is rather low and a lot of rehashing may have >diminishing returns, 2) you get some of the same benefits that >re-hashing gives you, and 3) the search benefits from the always >replace entry--it favors recently visited positions which may be more >likely to be hit in the search in current part of the game and it >also allows retention for a longer period of time of entries that >get pushed out of the table with the depth replacement scheme. > >-Dan.
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.