Author: Robert Hyatt
Date: 05:14:15 09/22/98
Go up one level in this thread
On September 21, 1998 at 21:50:52, Dan Newman wrote: >On September 21, 1998 at 20:42:46, Roberto Waldteufel wrote: > >> >>On September 21, 1998 at 20:32:51, Dan Newman wrote: >> >>>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 >> >>Do you know if any systematic research or experimentation has been done on >>replacement strategies? If the positions have double entries, that halves the >>number of positions that can be held in the table and doubles the access time >>unless the first probe finds the position being searched for. The advantages >>presumably more than offset these negative effects. Do you know what kind of >>speedup might be expected in going, say, from one table of 1,000,000 entries to >>two tables of 500,000 entries each? I am interested because I may well try to >>implement this in place of my present "one big table" approach. >> >>Best wishes, >>Roberto > >I once read a paper on this subject that found the two level table to >be the best amonst various other schemes--at least I think I read such >a paper... I've looked around and can't find it though. I'll look >some more later... > >It's really not the "positions" that have double entries, it's the >indices that do. So the entries aren't really wasted; they both can >contain info about positions (in my case, sometimes the same position >which is something of a waste I suppose). What I do is put both >entries into a single structure so that they are in contiguous memory, >and I can easily look at both in the same store or probe. (The hash >table is just a big array of these double entry structures.) When I >look at the first entry, the second probably comes along for the ride >(I hope they both fit into a cache line--what is the size of a P6 >cache line? Will 32-bytes fit?). > >I don't really know what the magnitude of the improvement (over a >single entry table) is, just that there probably is at least *some*. >(Chess programmers will jump through all sorts of hoops for a few >percent.) > >-Dan. Don Beal wrote a paper appearing in the JICCA that found that the multiple- probe table was significantly more efficient than one or two-level probes, but only if the table was greatly "over-subscribed" (total nodes searched was at least 10X the total table size).
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.