Transposition table utilizattion

[cdani]

Also a node can be stored two times, one when entering if it was not found, to store the evaluation of the position (a la Stockfish), and one on exit with the result. Hence some more "stored" than "nodes".

[D Sceviour]

What percentage might be expected for a full hash hit from the initial position, Signature match + draft sufficient to use? 10%?

[jeffreyan11]

I don't keep that exact statistic, but for 256 MB hash and depth 16 I get 9% hash score cuts (match, sufficient draft, and correct bound/score for an immediate cutoff).

[cdani]

What percentage might be expected for a full hash hit from the initial position, Signature match + draft sufficient to use? 10%?

Code: Select all

                                                          % found               % cutoff    
                                                          over found            over found % cutoff
hash           nodes       stored   not found       found +not found     Cutoff +not found over found
128 MB	 53.425.849   65.716.083  36.862.078  18.983.223  34%        4.846.332     8.7%      25.5%
256 MB	 64.437.112   78.582.936  43.534.378  23.853.827  35%        6.025.260     8.9%      25.3%
1024 MB  118.011.879  143.221.524  77.990.897  45.678.716  37%       10.985.678     8.9%      24.0%
4096 MB   74.634.324   88.762.678  48.235.382  29.907.519  38%        7.269.798     9.3%      24.3%

Is important also to note that I use hash also in quiescence.

[MathAddict]

I get only 2-3% tthits (ie. hits with sufficient draft and bound for cutoff) at start position. I understand there must be something wrong with my hash table, is there a way to debug this?

[Sven]

I get only 2-3% tthits (ie. hits with sufficient draft and bound for cutoff) at start position. I understand there must be something wrong with my hash table, is there a way to debug this?

Hi Rian,

welcome at TalkChess!

May I assume that you have already double-checked that your hash key calculation is correct? If you are not sure about this then you could add an assertion "incremental hash key == hash key from scratch" after the point where you have incrementally updated the hash key. That helps to find a few bugs in that part.

May I also assume that your search uses iterative deepening? Without it you might get a lower number of hits.

Which is your replacement strategy?

EDIT: other typical sources of error include, for instance,
- accidental swapping of "lower bound" and "upper bound" for the type of hash table scores,
- wrong storing/retrieving of mate scores (o.k., not in your case of the starting position),
- or maybe simple bugs in calculating the index of hash table elements from the hash key.

You could print the number, or percentage, of used HT entries to watch how much gets stored there.

[MathAddict]

Yes, I have validated my incremental hashing and my search uses ID.
I always replace unless unless the Key is the same, ie.

Code: Select all

if(newkey!=oldkey)
{
    replace();
}

I also tried not replacing if old key's draft is greater than new key draft, but that didn't help.
As for having the wrong bound checking, I always return score if bound was exact, or return score when bound=alpha and score<=alpha OR bound=beta and score>=beta. Is this correct?
Also thanks for the fast reply.

EDIT:
I store bound=alpha when it was a fail low, bound=beta when there was a beta cutoff and bound=exact otherwise.

[hgm]

I also tried not replacing if old key's draft is greater than new key draft, but that didn't help.

Indeed, that is usually very detrimental. And that can be easily understood. The reason you can produce a new result with a lower draft is that the higher draft in the table could not be used to cause a hash cutoff despite its sufficient draft, due to a bound type that was not usable in view of the most-recent root score. So you would quickly poison the table with useless entries that are very difficult to replace because of their high draft.

Note that 'TT hit' usually means just a key match, and does not imply the draft or bound was good enough to cause a cutoff. The latter would be called 'TT cutoffs', and it is not surprising that you get a far smaller percentage for those. Most of the TT hits in an ID context are caused by retracing the tree of the previous iteration, where every hit will have a draft that is just one lower as what you needed, and you only use the move. Sufficient-draft hits only occur on true transpositions, and it turns out that with alpha-beta there aren't too many of those. (Apparently most manoeuvres have a 'natural order' of the moves needed to accomplish them, and playing them in any order can already be refuted in an alternative way before you actually get to playing the transposition.)

[MathAddict]

Even if I count all hits with key match only, I get 16% hitrate (start position for 2.5 secs), I don't know if this is normal or lower than normal.

[syzygy]

I also tried not replacing if old key's draft is greater than new key draft, but that didn't help.

Indeed, that is usually very detrimental. And that can be easily understood. The reason you can produce a new result with a lower draft is that the higher draft in the table could not be used to cause a hash cutoff despite its sufficient draft, due to a bound type that was not usable in view of the most-recent root score. So you would quickly poison the table with useless entries that are very difficult to replace because of their high draft.

Note that 'TT hit' usually means just a key match, and does not imply the draft or bound was good enough to cause a cutoff. The latter would be called 'TT cutoffs', and it is not surprising that you get a far smaller percentage for those. Most of the TT hits in an ID context are caused by retracing the tree of the previous iteration, where every hit will have a draft that is just one lower as what you needed, and you only use the move. Sufficient-draft hits only occur on true transpositions, and it turns out that with alpha-beta there aren't too many of those. (Apparently most manoeuvres have a 'natural order' of the moves needed to accomplish them, and playing them in any order can already be refuted in an alternative way before you actually get to playing the transposition.)

You're thinking of the case where the new position is the old position. I think Rian is talking about the case where the new key differs from the old key, i.e. different positions. In that case, not always replacing means that the hash table may fill up with positions that have fallen out of the "minimal tree" and are thus of no help.