Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Hashkey collisions (typical numbers)

Author: Vincent Diepeveen

Date: 07:54:10 04/09/04

Go up one level in this thread


On April 09, 2004 at 10:50:52, Vincent Diepeveen wrote:

>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?

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

>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.