Author: Robert Hyatt
Date: 12:38:55 09/22/98
Go up one level in this thread
On September 22, 1998 at 12:07:07, Roberto Waldteufel wrote: > >On September 22, 1998 at 08:12:23, Robert Hyatt 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 >> >> >>No... this isn't the way it is implemented... Think of it as a two "level" >>table. one of the two tables is depth-preferred (this is the way it was >>implemented in the "belle" chess hardware and probably in deep thought/ deep >>blue hardware too). You only replace entries in this table if they are from >>an older search, or if the depth (draft) of the current position is greater >>than that of the stored position. The other table is "always" store. I've >>implemented this as follows: >> >> if (depth > draft[entry]) >> move entry from depth-preferred table to "always store" >> store in depth-preferred. >> else >> store in "always store" >> >>in this way, there are no duplicate entries and you take maximum advantage >>of both tables... > >But surely then you need to probe twice in table look-ups, since there are two >possible positions in memory where the entry might be found? Do you access the >depth-preferred table first, and only probe the always-store table if you don't >find a match in the depth-preferred? And when you are storing a position, do you >move the old entry to always store (1st clause of code above) even if it is the >same position with lower depth, rather than a different position at lower depth? >If so, then how do you deal with the possibility of two entries for the same >position at different depths? > very unlikely to happen, but possible. I probe the depth-first table which is a pretty sure guarantee to hold the deepest entries. It is unlikely that both will hold the same one, because if so, I would have gotten a hash hit before searching here most likely. But I don't waste time. If I hit on the depth-preferred table, I don't even probe the other one.. but it would be easy to instrument to see if it would ever happen.. >In the depth preferred table, how do you recognise old entries from searches >that were done so far back in the game to have lost any relavence to the currant >position? This is a poblem I currantly ignore, but I bet I am clogging up the >table to some extent in this way. I am hoping to overhaul all my hashing code in >the near future, so I would like to plan all the details now before I get >started. > >There's more to this hashing thing than I realised! > >Best wishes, >Roberto
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.