Author: Dan Newman
Date: 17:32:51 09/21/98
Go up one level in this thread
On September 21, 1998 at 19:44:55, James Robertson wrote: >On September 21, 1998 at 19:33:18, John Coffey wrote: > >>>You should also have two hash tables, one with an "always overwrite" >replacement >>>policy and another with a replacement policy based on depth. Almost everybody I >>>know agrees that this is the best way to do things on a PC. >> >>When I studied hashing for other types of applications, the rule would be that >>if you has two items with the same hash key, then you would store the second >>in the next available empty slot. > >It is just a waste of time. Most tables will hold so few positions that there >will be a lot of positions that could fill the same slot (i.e. have the same >index), and since no position is of any more importance than any other >position, there are no tangible rewards at all for doing this. There have been all sorts of different replacement policies tried, all with the notion that the information just gained about a position might well be more valuable than that currently stored in its corresponding hash table entry. For instance, if a hash table entry is for a position that was searched to a shallow depth, we might well want to replace it with one that was searched to a greater depth--because it's score probably more accurate and the information was probably obtained at a higher cost. 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. > >>This requires more data to keep track of >>where the next item is (could be a byte offset.) >> >>John Coffey
This page took 0.01 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.