Author: Robert Hyatt
Date: 08:47:59 06/03/98
Go up one level in this thread
On June 03, 1998 at 07:20:16, Guido Schimmels wrote:
>
>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
ok... several do that... when you said 32 bits for hash, I was thinking
of
32 bits for the complete signature. Not storing 32 bits of a 64 bit
hash
key. If you do a single-probe algorithm, then storing 32 and using part
of
the remaining 32 is not bad, so long as the table is big enough to use a
reasonable part of the entire 64 bits.
but for the non-hash, you need the following:
move. can be stored as roughly 8 bits or so, if you use an offset move
generator and store an index into the moves rather than the move itself.
it is probably possible to reduce this slightly.
score. good question on how many bits. 16 would give you +/- 32767
which
is plenty for a program using centipawns.
That leaves 8 bits at least, six to store depth below this node and two
bits
for the type of position. if he compresses the move to 6 bits, or if he
uses less than 16 bits for the score, that would leave a couple of bits
for
other things like "extend this node based on previous threats found" and
so forth.
but it's very tight. I use 96 bits myself, to avoid compressing the
move,
plus I use fractional plies, which means that I need a bigger "draft"
field
as well...
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.