Author: Dan Newman
Date: 11:00:47 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? What I do is store the two entries together at the same hash table index so I need not make any further index calculations, and hope the second entry gets pulled into cache when I access the first. I access the depth preferred table first and quit there if it's a match. I don't know, though, if that's the best policy... >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? > So far I've just ignored those details. It does seem a mistake to trash a perfectly good entry for another position with the useless lower depth entry... The only drawback to fixing this is the extra code to compare the keys of the new depth entry with the old to see if they are for the same position. >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 The trick here is to store an "age" field in the hash table entry. I think many use 3-bits for this, I think I'm using 4-bits. Every time you begin a new search, you increment the "age" variable and use that when you store to the table (I think I have something at the top of my iterative deepening function like "age = (age + 1) & 15;"). Now, when you probe and find the old entry is of a different "age", you can just trash it. -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.