Probing the transposition table at depth 0

[gonzaloarro]

I was trying to see how a different size for the transposition table affects the hit rate when I noticed that I was actually getting a really low hit rate.
For the starting position it was something like 6% at depth 12. It didn't change much in middlegame positions, maybe +1% or +2%. I read that normal values are around 20%, so definitely something was wrong.
After I examined my code I think I found the issue. In the alpha beta routine when the engine is at depth 0, it first probe the hash table and, if it was a miss, only then it calls the quiescence search algorithm. I noticed that other engines don't probe the hash table at depth 0, they go directly to the quiescence search. If I do this, I get normal hit rates (around 20%).
Testing a few different positions I couldn't see a clear winner, sometimes an approach takes longer but for other positions it is faster. So my question is: is there something wrong with probing the hash table at depth 0? doing this doesn't mean that I will cut off more nodes?

In case you want more information:

• hash table size: 128mb (5.5 million entries).

• I don't probe or store the table inside the qsearch.

• Engine: MORA CHESS ENGINE https://github.com/gonzaloarro/MORA-CHESS-ENGINE

[Sven]

Depth 0 actually belongs to qsearch. Since you don't store anything in the TT during qsearch you also can't expect to find anything with depth 0 there. You will find some transpositions where the current position at depth 0 had already been visited at a higher depth, but that will have a minor effect. Since most nodes are depth 0 nodes most of your probes are wasted, so it is better not to probe at depth 0 if you don't store during qsearch.

[gonzaloarro]

Depth 0 actually belongs to qsearch. Since you don't store anything in the TT during qsearch you also can't expect to find anything with depth 0 there. You will find some transpositions where the current position at depth 0 had already been visited at a higher depth, but that will have a minor effect. Since most nodes are depth 0 nodes most of your probes are wasted, so it is better not to probe at depth 0 if you don't store during qsearch.

When the engine searchs at depth 0, finding transpositions visited at a higher depth in the TT is what I was aiming for. I thought the effect was bigger, but as you mentioned clearly it is not.
I still have the problem of the pv being overwritten sometimes (I recover the pv from the TT) so that makes difficult to test changes in my TT scheme because I get different results. That's why I wanted to know if there was something wrong with this approach.
Anyways, I'm gonna fix the issue.

Thanks for your response!

[jstanback]

In Wasp I get some benefit by storing positions in Qsearch at depth=0, but only if a move increased alpha. I probe the hash table for depth >= 0.

John

[silentshark]

In Wasp I get some benefit by storing positions in Qsearch at depth=0, but only if a move increased alpha. I probe the hash table for depth >= 0.

John

For me, just probing (not storing) in Qsearch was best, but not a lot in it.

[hgm]

Note that getting a high hit TT hit rate is not a useful purpose in itself. As mentioned, probing at d=0 will have a very low chance for success if you don't store at d=0, much lower than probing at depth for which you also do store. But sometimes it might, and in that case you save the effort of a QS, which might have been expensive to do. So it all depends on how much time you gain on average on a hit and how much time you waste on a miss, as well as on the fraction of hits. This again depends on how efficient or heavily pruned your QS is, and on how efficient your hash probing scheme is. Selling something cheap on the side can increase your profits, even though it reduces your average profit margin. But you have to avoid selling stuff at a loss.

If the problem is that the d=0 TT probes that are misses are very slow, and thus waste comparatively much time, it might be possible to improve this by smarter TT organization. In the face of low hit probability you should try to prevent probes that need to come from RAM, as these will be slow. To achieve that you could maintain a 'filter table' for the TT that is small enough to fit in the CPU cache, where you store (on every TT store) the upper byte of the hash key hashed by the appropriate number of low bits of that key, in an always-replace scheme. At low remaining depth you could then first probe that table to see if the upper byte matches, and refrain from probing the TT itself when it doesn't. This should reduce the number of expensive 'hopeless' probes by a factor 256 through a cheap test.