Author: Frank Phillips
Date: 03:44:04 12/22/02
Go up one level in this thread
On December 21, 2002 at 13:57:09, Vincent Diepeveen wrote:
>On December 20, 2002 at 22:05:14, Walter Faxon wrote:
>
>>On December 20, 2002 at 05:40:35, Gerd Isenberg wrote:
>>
>>>On December 19, 2002 at 16:50:32, Dann Corbit wrote:
>>>
>>>>Suppose that we are searching at long time control, and the hash table rapidly
>>>>fills up. This can throw move ordering in the toilet, if we can't find
>>>>transpositions any more.
>>>>
>>>>What sort of replacement scheme is best for very long searches (several
>>>>minutes)?
>>>
>>>Hi Dann,
>>>
>>>I use a two table approach.
>>>
>>>A primary big one, where i replace one of eight with the lowest
>>>timestamp/draft/someFlags priority. Exact entries became a bit more resistance
>>>against overwriting, the same for most left succesors of every root move (pv and
>>>refutations lines).
>>>
>>>A smaller secondary one, with an always replacement scheme.
>>>
>>>In general i don't store or probe in qsearch. I use IID in __every__ interior
>>>node without a move hint from hash.
>>>
>>>Regards,
>>>Gerd
>>
>>
>>Hi, Gerd.
>>
>>Good idea about IID!
>>
>>I have no chess program but it seems to me that one uses hashing for two
>>reasons: (1) to save information that was expensive to compute but may not be
>>immediately useful (closer to the root), and (2) to save information that wasn't
>>very expensive to compute but may be useful very soon (close to the current
>>node). That's why a two-table approach (or a one-table, two types of entry
>>approach) is so often preferred.
>
>Not really.
>
>first there was a concept which most used with a single hash transposition.
>then the 2 table concept was invented, but long before that already 8
>probe concepts were there.
>
>Yet recently cache lines (starting with DDR ram and RDRAM) have increased
>that much in length, that you for free can implement without risk a
>concept of 4 probes in a row.
>
>That's obviously working a lot better than 2 slow accesses to ram at
>random positions.
>
I am confused. Memory access for hash tables should be random - yes?
Nevertheless, will not the following be together in memory. There could be more
elements within the structure of course.
typedef struct trans_record {
TransRecordT top;
#if defined TWO_LEVEL_HASH_TABLE
TransRecordT bottom;
#endif
} HashRecordT;
>>Reason (2) implies that some sort of hashing should be done even in quiescence
>>search. The problem with qsearch hashing nowadays is the memory caching
>>penalty. Nowadays, if you have to wait on a memory access that might only help
>>a little, you might as well do the search directly.
>>
>>Maybe one might use a very small hash table (10K entries, say), reserved for
>>qsearch nodes? (Or nodes beyond a certain depth or with reduced material.)
>>Particularly if you could freeze it all into the cache...
>>
>>I think an older ICCAJ paper detailed experiments with hash node type
>>allocation, but without reference to memory caching penalties.
>>
>>-- Walter
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.