Eval hashtable replacement scheme

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
PK
Posts: 820
Joined: Mon Jan 15, 2007 10:23 am
Location: Warsza
Contact:

Eval hashtable replacement scheme

Post by PK » Tue Oct 08, 2019 7:01 am

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?

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

Re: Eval hashtable replacement scheme

Post by hgm » Tue Oct 08, 2019 8:35 am

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.)

mar
Posts: 1992
Joined: Fri Nov 26, 2010 1:00 pm
Location: Czech Republic
Full name: Martin Sedlak

Re: Eval hashtable replacement scheme

Post by mar » Tue Oct 08, 2019 12:03 pm

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? :)
Martin Sedlak

PK
Posts: 820
Joined: Mon Jan 15, 2007 10:23 am
Location: Warsza
Contact:

Re: Eval hashtable replacement scheme

Post by PK » Wed Oct 09, 2019 4: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.

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.

tomitank
Posts: 200
Joined: Sat Mar 04, 2017 11:24 am
Location: Hungary

Re: Eval hashtable replacement scheme

Post by tomitank » Sun Oct 13, 2019 11:17 am

PK wrote:
Wed Oct 09, 2019 4: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..

Post Reply