TT hit/miss rates

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
vladstamate
Posts: 161
Joined: Thu Jan 08, 2009 8:06 pm
Location: San Francisco, USA
Contact:

TT hit/miss rates

Post by vladstamate » Thu Feb 25, 2010 6:15 pm

Hi,

I am trying to see how way off mark I am compared with other engines in the TT hit/miss ratio.

From the start position, looking until depth 8, this is what I get

Code: Select all

Cache usage: hits=16009(16.26%) misses=15367(15.61%) conflicts=67063(68.13%)
hits - a value was found and returned
misses - either the depth of the value/move stored in the hash was not good enough or the node type and value do not play well with out current alpha/beta. Basically for some reason the entry is there but we cannot use/trust it. I use the move stored though for move ordering purposes.
conflicts - either I am probing an empty (non-written yet) entry or the full 64 bit hash does not match.

What are typical ratios?

Regards,
Vlad.

micron
Posts: 155
Joined: Mon Feb 15, 2010 8:33 am
Location: New Zealand

Re: TT hit/miss rates

Post by micron » Fri Feb 26, 2010 8:32 am

vladstamate wrote: I am trying to see how way off mark I am compared with other engines in the TT hit/miss ratio.
From the start position, looking until depth 8, this is what I get

Code: Select all

Cache usage: hits=16009(16.26%) misses=15367(15.61%) conflicts=67063(68.13%)
What are typical ratios?
I was interested by your results, having recently tweaked my TT code in the hope of increasing the number of fully useable hits. From the start position, my program reports:

Code: Select all

nominal 7 ply search:
5.2E+4 probes
1.3E+4 hits (score used) 25% [your 'hits']
9.4E+3 hits (move tried) 18% [your 'misses']
2.9E+4 misses            55% [your 'conflicts']

nominal 8 ply search:
2.4E+5 probes
6.5E+4 hits (score used) 27% [your 'hits']
2.9E+4 hits (move tried) 12% [your 'misses']
1.4E+5 misses            60% [your 'conflicts'] 
These percentages are sensitive to details of the replacement policy for the TT. My present policy is:
overwrite the cached node unless incoming_score_is_inexact && we_have_a_cache_hit && search_depth_of_cached_node > search_depth_of_incoming_node.

Robert P.

User avatar
hgm
Posts: 23714
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: TT hit/miss rates

Post by hgm » Fri Feb 26, 2010 9:29 am

Does your replacement policy really matter, for such a shallow search? I would expect the tree to completely fit into the table, without hardly any collisions.

A second question: does that condition you give above really help? If the depth of the new search was less than for the same node in hash, it must mean that the bound of the latter is no good for your current window. But in PVS your whole search will keep using the current (null) window throughout, unless the score at the root changes. (Which happens very infrequently.)

So by keeping the entry with the worthless bound, any subsequent hit on it will have to do the search, no matter what the requested depth was. When you would store the result of the current search, no matter how undeep, at least future hits of lower requested depth could profit from it.

micron
Posts: 155
Joined: Mon Feb 15, 2010 8:33 am
Location: New Zealand

Re: TT hit/miss rates

Post by micron » Sun Feb 28, 2010 8:08 am

You are right. If the TT is virtually empty, the best policy seems to be 'always overwrite'. I wish I had known this earlier. Replacement strategy becomes relevant when the table fills up, which is likely in, for example, an 11-ply search from the start.

The answer to your second question is "yes, it does help my program in wide deep searches". But I don't do PVS yet. When that is implemented, your interesting comments suggest that I might profitably revisit the TT replacement strategy.

jwes
Posts: 778
Joined: Sat Jul 01, 2006 5:11 am

Re: TT hit/miss rates

Post by jwes » Sun Feb 28, 2010 5:52 pm

micron wrote:You are right. If the TT is virtually empty, the best policy seems to be 'always overwrite'. I wish I had known this earlier. Replacement strategy becomes relevant when the table fills up, which is likely in, for example, an 11-ply search from the start..
If the TT is virtually empty, all replacement strategies are approximately the same.

Post Reply