Page 1 of 1
Eval hashtable replacement scheme
Posted: Tue Oct 08, 2019 9:01 am
by PK
Hi,
Yes, you hear me all right. Currently I am writing a commercial chess app, coded in a slow interpreted language - this has been a requirement and is non-negotiable - so some optimisations are in order. I wonder whether any of you has tried something more sophisticated than always replacing eval hashtable entries. My current attempt is a two-tier table, replacement scheme the same as with killer moves. It works for the first few plies, then it saturates, as a normal table would. Has any of you tried other improvements?
Re: Eval hashtable replacement scheme
Posted: Tue Oct 08, 2019 10:35 am
by hgm
You would want to keep those entries which have the largest probability to be needed again during the time you can store them. The way you search through the tree causes these to be the most-recently generated entries. A least-recent written scheme like used for killers does exactly that, and might therefore be theoretically optimal.
Even if you would know the remaining depth of the corresponding node by storing it in the table, there would be no reason to prefer hanging on to deeper entries, as the work spent on eval is always the same. In fact you might prefer to replace evals from nodes far away from the leaves, as they have little hope on being needed again any time soon, an are probably just wasting precious table space. But if you do that, you might as well not have stored them in the first place (so that the need to record the depth also disappears). So this could be a refinement: refrain from storing evals in the table of interal nodes. (Of course if your engine doesn't evaluate in internal nodes, you would automatically do that.)
Re: Eval hashtable replacement scheme
Posted: Tue Oct 08, 2019 2:03 pm
by mar
Does your scheme really pay off in terms of speedup?
I'd expect that eval cache helps mostly in qs nodes anyway so my guess is tweaking the size of the eval table should be sufficient.
But of course, if the scripting language you use is, say 10-20 times slower than native code...
Perhaps you could even revive the old lazy eval idea.
Out of curiosity, which scripting language do you use and why can't you simply use a native engine and simply expose it to the script?
This way you flush 400+ elo down the toilet right at the start, but I don't know what the goal is (assume a chess playing application).
We're not talking GM level of play at mobile platforms, right?
Re: Eval hashtable replacement scheme
Posted: Wed Oct 09, 2019 6:21 am
by PK
No, not much speed gain, 1% for 10 minutes of coding, more if searches are short. Of course I'm not aiming for GM strength (more like a NM plus many weak levels), the app is indeed meant for casual players on cell phones.
Out of curiosity, I tested this scheme in a full-blown C++ engine, with the same eval hashtable size, bench from several positions to depth 16. Result:
Code: Select all
// 39489276 nodes searched in 37703 ms, speed 1047349 nps (Score: 0.871829) always replace
// 39489276 nodes searched in 37125 ms, speed 1063655 nps (Score: 0.885402) killer-like replacement
So again, the gain is marginal, but detectable.
Re: Eval hashtable replacement scheme
Posted: Sun Oct 13, 2019 1:17 pm
by tomitank
PK wrote: ↑Wed Oct 09, 2019 6:21 am
No, not much speed gain, 1% for 10 minutes of coding, more if searches are short. Of course I'm not aiming for GM strength (more like a NM plus many weak levels), the app is indeed meant for casual players on cell phones.
I think it's unnecessary, but you know..
..here is my chess mobile application (writed in JavaScript, html, css. Max. strength: ~2800 elo):
Android:
https://play.google.com/store/apps/deta ... y.hu&hl=en
iOS:
https://apps.apple.com/app/sakk/id1150654415
The online version coming soon..