Author: Guido Schimmels
Date: 04:20:16 06/03/98
Go up one level in this thread
On June 02, 1998 at 13:03:47, Robert Hyatt wrote:
>On June 02, 1998 at 10:27:07, Guido Schimmels wrote:
>
>>
>>On May 30, 1998 at 09:56:25, Robert Hyatt wrote:
>>
>>>there are at least a couple of things that could make Fritz far more
>>>sensitive to hash table size than other programs:
>>>
>>>(1) a poor replacement strategy. If this is true, then a larger table
>>>reduces replacement, which would produce better performance.
>>>
>>>(2) using the table for other things besides the normal score/best move/
>>>etc. If this is true, replacing *any* entry could be bad, depending on
>>>what is stored in the table.
>>>
>>>no one knows what Fritz does, but one of the above reasons is almost
>>>certain to be correct. I'd suspect (2) myself, since replacement
>>>strategies are well-known now.
>>
>>Hi Bob !
>>
>>Thoughts on (1):
>>I heard, when the hashtable is only %60 full, Fritz5 already starts to
>>suffer
>>seriously. Sounds like poor replacement strategie to me.
>>Remember Fritz5 is 200,000 nps on Pentium MMX 200. A single instruction
>>added to such a fast program causes measurable slow down.
>>Sophisticated replacement would drop that number significantly
>> - at least if he does q-search hashing which I think he does -
>>Frans Morsch may think, RAM is cheap, it's not worth it.
>>
>>Thoughts on (2):
>>Maybe he stores some carefully chosen flags, who knows.
>>But Fritz uses 64-bit entries (32-bit key / 32 bit
>>move|score|depth|flags
>>I guess), so not much bits left - if any -
>>
>>- Guido
>
>If he really stores a 32bit hash signature, he is really *playing with
>fire*. That is provably bad with some simple simulations or tests.
>Several
>of us ran several such tests a few years ago and posted the results in
>r.g.c.c.. (or r.g.c as it was then). 32 bits is not nearly enough to
>prevent significant numbers of collisions.
>
>I suppose it is possible he does a "single probe" algorithm to drive the
>speed up, but the danger is serious, particularly in endgames where the
>depth can go wild. IE in a king and 3 pawn vs king and 3 pawn game this
>morning I was seeing 40+ ply searches at 20 seconds per move. That
>gives
>plenty of paths to produce collisions that will wreck things...
>A few years ago< hashtables used to be much smaller than now.
When Fritz has 64 MB hash he'll use 54 bits of the 64-bit hashkey
effectively:
64 MB------------------------------- 26 bit
8 bytes/position---------------- - 3
two tables (black/white)---- - 1
-------------------------------------32 + 22 = 54
(8 bytes/position is definitly true for Fritz, the rest is my guess)
Collisions might be one reason for Fritz to like big tables so much -
but AFAIK Frans does it the same way on the dedicated hardware he also
programes , where he has only small tables. So maybe he knows some
tricks
we don't :-{ (less than 32 bits for move|score|depth|flags ?)
By the way, I read an article by Donninger (from 1995 I think)
where he says some desperados use 16-bit signatures in
their tables, but he didn't name them.
-Guido
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.