Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Hashkey collisions (typical numbers)

Author: Vincent Diepeveen

Date: 07:50:52 04/09/04

Go up one level in this thread


On April 08, 2004 at 15:01:45, Robert Hyatt wrote:

Substantiate your claim Hyatt.

How could even if 0.x in 1 billion hash errors modify hashtable hit rates?

Just admit his qsearch is better and as a result of that he researches his tree
more. Your qsearch is rude & quick and of course do not improve your main search
a lot.


>On April 08, 2004 at 02:51:09, Tony Werten wrote:
>
>>On April 07, 2004 at 14:43:02, Robert Hyatt wrote:
>>
>>>On April 07, 2004 at 14:22:38, Vincent Diepeveen wrote:
>>>
>>>>On April 07, 2004 at 14:16:31, Robert Hyatt wrote:
>>>>
>>>>>On April 07, 2004 at 11:27:47, Vincent Diepeveen wrote:
>>>>>
>>>>>>On April 07, 2004 at 11:04:23, Robert Hyatt wrote:
>>>>>>
>>>>>>>On April 07, 2004 at 10:54:40, Tony Werten wrote:
>>>>>>>
>>>>>>>>On April 07, 2004 at 10:48:23, Renze Steenhuisen wrote:
>>>>>>>>
>>>>>>>>>
>>>>>>>>>>>>>>I'm sure it was some implementation bug with Renze.
>>>>>>>>>
>>>>>>>>>Anyone,
>>>>>>>>>
>>>>>>>>>I only store result from the main search, so no NULL-move and no Qsearch
>>>>>>>>>results.
>>>>>>>>>I get a TT-hit ratio of 11.73%, of which a part will generate cut-offs.
>>>>>>>>>    (I call something a tt-hit when an entry is found with the same hashkey,
>>>>>>>>>     draft does not need to be sufficient)
>>>>>>>>
>>>>>>>>Hmm, I'm sorry but that's way too low. You probably have a problem with your
>>>>>>>>hashkey.
>>>>>>>>
>>>>>>>>In XiniX I get a hitrate of at least 60% in normal search, >20% in qsearch.
>>>>>>>
>>>>>>>That can't be right unless you are talking positions like Fine 70...
>>>>>>>
>>>>>>>Too many have run that experiment over the years and 30% is the _highest_ number
>>>>>>>I have ever seen reported in opening/middlegame positions.
>>>>>>
>>>>>>Xinix is a very efficient searching program with a good qsearch.
>>>>>>
>>>>>>Better qsearch means more efficient main search.
>>>>>
>>>>>Has absolutely _nothing_ to do with number of "transpositions" however...
>>>>
>>>>It actually does, because in crafty your fliprate is like 5% or so i remember
>>>>and probably hasn't changed much sincethen. It is a result of not storing in
>>>>qsearch and doing little in qsearch.
>>>\
>>>
>>>Here is +real+ data:
>>>
>>>3r4/pbr2pkp/1p1qp1p1/3n4/P1BP1PN1/1P4Q1/5RPP/3R2K1 b - - 0 1
>>>
>>>              time=1:00  cpu=391%  mat=0  n=134503927  fh=92%  nps=2.24M
>>>              ext-> chk=3336967 cap=373397 pp=44255 1rep=256105 mate=3433
>>>              predicted=0  nodes=134503927  evals=39178023  50move=6
>>>              endgame tablebase-> probes=0  hits=0
>>>              hashing-> 24%(raw) 19%(depth)  80%(sat)  99%(pawn)
>>>              hashing-> 0%(exact)  14%(lower)  1%(upper)
>>
>>In XiniX 46% in normal search, 13% in qsearch.
>>
>>Altough qsearch hits are very nice (almost always a cutoff) this is one of those
>>positions where it might not pay off. There also doesn't seem to be anything
>>going on in this position ( or I didn't search long enough ) wich lowers the
>>hitrates. (bm a6 ?)
>>
>>>
>>>for that search, I got 24% raw hits.  That is pure hash signature matches,
>>>whether the info was useful or not.  very few were exact entries (no surprise
>>>for a program that uses PVS since most searches fail high or low), 14% were
>>>lower bound values which means the search stopped with a fail high, 1% was an
>>>upper bound value which means the search stopped with a fail low at this point.
>>>The other 9% were useless because of the draft (depth remaining).  The "sat"
>>>value simply says that the table was 80% utilized during the search, that 20% of
>>>the entries were not modified at all.  The hash size was 12 million entries or
>>>192M bytes (16 bytes per entry).
>>>
>>>Here is how it looks for fine #70 as an extreme example:
>>>
>>>8/k7/3p4/p2P1p2/P2P1P2/8/8/K7 w - - 0 1
>>>
>>>              time=1:00  cpu=234%  mat=1  n=60933197  fh=88%  nps=1.01M
>>>              ext-> chk=6896348 cap=47387 pp=350507 1rep=105017 mate=2957
>>>              predicted=0  nodes=60933197  evals=23142373  50move=0
>>>              endgame tablebase-> probes=143144  hits=143144
>>>              hashing-> 59%(raw) 53%(depth)  49%(sat)  99%(pawn)
>>>              hashing-> 1%(exact)  42%(lower)  4%(upper)
>>>
>>
>>:)))
>>
>>97% in search, 48% in qsearch.
>
>This is one reason I had hoped you would "join" the paper on hash collisions.
>Your program is obviously a big departure from what I do in Crafty.  It would be
>interesting to see how hash collision errors affects what you do...
>
>
>>
>>remarks:
>>Solution found at ply 16, speed 736Kn/s ( he, it can be fast ), test stopped
>>after 5 secs ( reached maxdepth=30 ), no EGTB
>>
>>Thinking about it. If Crafty would store nodes with depth<=0 it would probably
>>get a higher hitrate in normal search as well, but loose a lot of speed. In
>>XiniX I have lost that speed already by design choice, so it doesn't matter that
>>much.
>>
>>Can you check ? Store the first ply in qsearch ( but don't probe ) and see if
>>the hitrate goes up.
>>
>>Tony
>>
>>
>>>There the raw hit rate was 59%.  Lots of tb hits so here is the same test with
>>>egtbs turned totally off:
>>>
>>>              time=1:00  cpu=360%  mat=1  n=137657341  fh=85%  nps=2.29M
>>>              ext-> chk=17777360 cap=371216 pp=1119055 1rep=203863 mate=2094
>>>              predicted=0  nodes=137657341  evals=52311875  50move=0
>>>              endgame tablebase-> probes=0  hits=0
>>>              hashing-> 53%(raw) 49%(depth)  83%(sat)  99%(pawn)
>>>              hashing-> 0%(exact)  39%(lower)  6%(upper)
>>>
>>>
>>>>
>>>>In software doing checks in qsearch and storing them the fliprate is < 1%
>>>>usually.
>>>
>>>What is "fliprate"?  My fh % shows the same information, namely how often I fail
>>>high on the first move assuming I fail high at all...
>>>
>>>
>>>
>>>>
>>>>Xinix belongs to that group.
>>>>
>>>>>That is simply a characteristic of the tree being searched and its size and
>>>>>number of branches...
>>>>>
>>>>>If you get over 30% hash hits, something odd is going on in the middle game.  IE
>>>>>horrible move ordering or something...
>>>>
>>>>In contradiction a very good move ordering happens. He just researches the same
>>>>tree time and again.
>>>>
>>>>In crafty you do not. You just keep searching new trees because of the instable
>>>>qsearch+eval scores you get back.
>>>>
>>>>Each new iteration something <= alfa flips to >= beta, causing you a ply down to
>>>>research for a <= alfa node possibly suddenly entire new trees you didn't search
>>>>before.
>>>>
>>>>So a higher % there is a direct result from a more efficient search + storing in
>>>>qsearch.
>>>>
>>>>>
>>>>>>
>>>>>>
>>>>>>>
>>>>>>>>
>>>>>>>>Tony
>>>>>>>>
>>>>>>>>>
>>>>>>>>>the tt_retrieve code retrieves a move, which I call the TT_MOVE_SUGGESTION.
>>>>>>>>>
>>>>>>>>>could someone provide me with a % of TT_MOVE_SUGGESTIONs in a search?
>>>>>>>>>
>>>>>>>>>Cheers...



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.