hgm wrote: ↑Sat Jun 25, 2022 3:51 pm
To make the most of the table, you would want each higher depth to survive about 3 times longer (if the EBF = 3) than the next-lower depth. Because the time it takes to reach a transposition is proportional to the size of the sub-tree. Your method of using the number of probes as the timescale could work optimally, if you replace d=N not after N misses, but after 3^N misses. But a byte-size counter is not able to count far enough as would be needed for d > 5.
I changed my current implementation to
Code: Select all
return (++e0.Age - e0.Depth * e0.Depth) > (++e1.Age - e1.Depth * e1.Depth) ? index : index ^ 1;
which I equivalent to what you suggested but assuming an EBF of 2. It would work as intended for depths up to 16. 3^N might be even better but this should already be a big improvement over what I originally did.
But it proved quite hard to prove that superiority in self play. Even with 8 cores playing games all day I can't really simulate enough long time control games to prove it's worth. On shorter time controls (e.g. 5s+200ms increment or even 10s+2s) both versions perform equal.
So I resolved to do a synthetic test: Search the 300 WAC positions to the fixed depth of 20. With 50MB hashsize the new code needs 20% less nodes on average. And the advantage really starts to shine when you limit TT to use only 5 MB of space.
My original code took 196 minutes to complete. The revised version with the depth squared completed after 136 minutes. I didn't test a version with the 3^N you suggested because it would have required bigger changes.
This is why I like the 'undercut replacement': there the event that determines whether you will replace is the number of probes on the next-lower depth (rather than any depth). And the frequency of such probes will also decrease with the EBF when the depth gets higher. And even when you don't want to replace on every such probe, but (say) on half of those, you could make that statistical, and replace with a 50% probability. (E.g. based on the lowest bit of the node counter.) Then you don't need an aging counter in the entry at all, saving space, and avoiding dirtying the cache line other that when a replacement occurs.
That's clever!
I'm currently running the same synthetic test (hashsize=5MB, depth=20) for the undercut approach and it's too early to say for sure but even the most simple implementation is already looking good!
Code: Select all
static int Index(in ulong hash, int newDepth)
{
int index = (int)(hash % (ulong)_table.Length);
ref HashEntry e0 = ref _table[index];
ref HashEntry e1 = ref _table[index ^ 1];
if (e0.Hash == hash)
return index;
if (e1.Hash == hash)
return index ^ 1;
//chose the shallower entry unless the new entry's depth is just one lower
//this is how we prevent stale, deep entries from sticking around forever.
return (e0.Depth < e1.Depth || e0.Depth == newDepth + 1) ? index : index ^ 1;
}
Would be perfect not only for Leorik but especially for MinimalChess.
I found it....
