Hashing question

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
kdjones
Posts: 9
Joined: Mon Feb 08, 2016 6:06 pm
Location: Nova Scotia, Canada

Hashing question

Post by kdjones » Tue Feb 23, 2016 1:13 am

Lecture notes for April 24, 1997
Hashing and Move Ordering
by David Eppstein, Dept. of Information & Computer Science, UC Irvine

"Don't hash the positions very near the leaves of the search tree, there are too many of them (they'll take away hash table space from more valuable positions) and you're not saving much time by avoiding searching them."

Is this statement true and proven by anyone :?:

AlvaroBegue
Posts: 920
Joined: Tue Mar 09, 2010 2:46 pm
Location: New York
Full name: Álvaro Begué (RuyDos)

Re: Hashing question

Post by AlvaroBegue » Tue Feb 23, 2016 1:28 am

kdjones wrote:Lecture notes for April 24, 1997
Hashing and Move Ordering
by David Eppstein, Dept. of Information & Computer Science, UC Irvine

"Don't hash the positions very near the leaves of the search tree, there are too many of them (they'll take away hash table space from more valuable positions) and you're not saving much time by avoiding searching them."

Is this statement true and proven by anyone :?:
I think that's false: There are engines that even store QS nodes in the transposition table! But of course it might have been true in 1997, when memory was less abundant.

This is one of the things that you need to try and test thoroughly.
Last edited by AlvaroBegue on Tue Feb 23, 2016 1:29 am, edited 1 time in total.

kbhearn
Posts: 411
Joined: Thu Dec 30, 2010 3:48 am

Re: Hashing question

Post by kbhearn » Tue Feb 23, 2016 1:29 am

No. I believe stockfish hashes all the way to qsearch (i think some engines do omit qsearch though). Replacement strategies can make sure that mostly you're only replacing other low depth nodes and while it's not saving much effort per hit, you'll be getting a lot more hits to make up for that.

bob
Posts: 20550
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Hashing question

Post by bob » Tue Feb 23, 2016 4:37 am

kdjones wrote:Lecture notes for April 24, 1997
Hashing and Move Ordering
by David Eppstein, Dept. of Information & Computer Science, UC Irvine

"Don't hash the positions very near the leaves of the search tree, there are too many of them (they'll take away hash table space from more valuable positions) and you're not saving much time by avoiding searching them."

Is this statement true and proven by anyone :?:
"near the leaves" sounds reasonable. If you consider three types of nodes; (a) interior nodes (depth > 0), (b) frontier nodes (depth = 0) and then leaf nodes (anything beyond depth = 0 nodes, then you might discover that probing the hash table saves you a bit of tree space, but it also has a significant cost for the memory access. I have not tested in quite a while, but the last time I did, I found that hashing in q-search reduced the tree search by about 10%, but then it slowed the search by about 10%, so it was a wash.

I elected to not hash in q-search, because if you begin to overwrite hash entries at a significant rate, that also has a detrimental effect that adds on to the already found 10% performance loss.

Best advice? Test. YMMV. I hash up to but not including depth=0 nodes, which are the first layer of the q-search.

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

Re: Hashing question

Post by hgm » Tue Feb 23, 2016 7:33 am

kdjones wrote:"Don't hash the positions very near the leaves of the search tree, there are too many of them (they'll take away hash table space from more valuable positions) and you're not saving much time by avoiding searching them."
The point is that you also don't save much time by avoiding searching positions close to the root, when their daughter nodes are all in the hash table. You can then get a d=20 result by just doing a d=1 search to probe all the daughters.

So indeed, the statement is pure nonsense. No matter how small the hash table, the available space is used most effectively by distributing it equally over all drafts, i.e. as many d=1 positions as d=15 positions. A valid reason for not storing below a certain depth could be memory bandwidth. OTOH, a more effective way to combat that bottleneck might be to have a dedicated hash table for leave nodes that fits entirely in cache.

bob
Posts: 20550
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Hashing question

Post by bob » Wed Feb 24, 2016 5:45 pm

hgm wrote:
kdjones wrote:"Don't hash the positions very near the leaves of the search tree, there are too many of them (they'll take away hash table space from more valuable positions) and you're not saving much time by avoiding searching them."
The point is that you also don't save much time by avoiding searching positions close to the root, when their daughter nodes are all in the hash table. You can then get a d=20 result by just doing a d=1 search to probe all the daughters.

So indeed, the statement is pure nonsense. No matter how small the hash table, the available space is used most effectively by distributing it equally over all drafts, i.e. as many d=1 positions as d=15 positions. A valid reason for not storing below a certain depth could be memory bandwidth. OTOH, a more effective way to combat that bottleneck might be to have a dedicated hash table for leave nodes that fits entirely in cache.
I've experimented with the dedicated hash table, both for normal and pawn hashes, and while it actually offers a little improvement for a single-threaded search, it is a performance killer for SMP since you now have N copies of this with N threads. You are primarily using L3 for this since L1 and L2 are likely too small, and since L3 is shared, the pressure on it goes way up. In my case with dual 10 core processors, even with 24mb of L3, 10 times anything reasonable becomes pretty large, particularly if you do this for both pawns, and frontier hashing. Not to mention that some use per-thread history counters (I don't) not to mention all the per-thread board state and search state info.

Post Reply