Probing the transposition table at depth 0

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
gonzaloarro
Posts: 11
Joined: Sat Aug 31, 2019 2:23 am
Full name: Gonzalo Arro

Probing the transposition table at depth 0

Post by gonzaloarro » Fri Nov 29, 2019 10:29 pm

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.

Sven
Posts: 3830
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Probing the transposition table at depth 0

Post by Sven » Fri Nov 29, 2019 11:26 pm

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.
Sven Schüle (engine author: Jumbo, KnockOut, Surprise)

gonzaloarro
Posts: 11
Joined: Sat Aug 31, 2019 2:23 am
Full name: Gonzalo Arro

Re: Probing the transposition table at depth 0

Post by gonzaloarro » Sat Nov 30, 2019 12:12 am

Sven wrote:
Fri Nov 29, 2019 11:26 pm
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
Posts: 59
Joined: Fri Jun 17, 2016 2:14 pm
Location: Colorado, USA
Full name: John Stanback

Re: Probing the transposition table at depth 0

Post by jstanback » Sat Nov 30, 2019 4:35 pm

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

User avatar
silentshark
Posts: 237
Joined: Sat Mar 27, 2010 6:15 pm
Contact:

Re: Probing the transposition table at depth 0

Post by silentshark » Sat Nov 30, 2019 5:22 pm

jstanback wrote:
Sat Nov 30, 2019 4:35 pm
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.

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

Re: Probing the transposition table at depth 0

Post by hgm » Sun Dec 01, 2019 9:44 am

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.

Post Reply