Winboard Forum

I thinking about introducing a evaluation cache in Snitch.
For those that already implemented one:

• What replacement scheme do you use ?
• What hit rate could I expect in a typical middle game position ?

Regards,

Klaus

Klaus Friedel wrote:I thinking about introducing a evaluation cache in Snitch.
For those that already implemented one:

• What replacement scheme do you use ?
• What hit rate could I expect in a typical middle game position ?

Regards,

Klaus[/list]

Scorpio and Glaurung both use an evaluation cache.
The benefit is small but tangible.

Klaus Friedel wrote:I thinking about introducing a evaluation cache in Snitch.
For those that already implemented one:

• What replacement scheme do you use ?
• What hit rate could I expect in a typical middle game position ?

• Always replace. Perhaps I lack imagination, but I don't see any other reasonable scheme.
• The hit rate depends on a number of factors, including the size of the cache, the time control, and whether you evaluate internal nodes. I've found it to be most useful in fast games, where most of the internal nodes at iteration N have already been evaluated during iteration N-1. In blitz games, a sufficiently big evaluation cache gives me an n/s increase of about 5-10% on x86 CPUs, and nothing at all on the PowerPC G5.

Dann Corbit wrote:Scorpio and Glaurung both use an evaluation cache.

And, of course, Phalanx.

Tord

Tord Romstad wrote:

Klaus Friedel wrote:I thinking about introducing a evaluation cache in Snitch.
For those that already implemented one:

• What replacement scheme do you use ?
• What hit rate could I expect in a typical middle game position ?

• Always replace. Perhaps I lack imagination, but I don't see any other reasonable scheme.
• The hit rate depends on a number of factors, including the size of the cache, the time control, and whether you evaluate internal nodes. I've found it to be most useful in fast games, where most of the internal nodes at iteration N have already been evaluated during iteration N-1. In blitz games, a sufficiently big evaluation cache gives me an n/s increase of about 5-10% on x86 CPUs, and nothing at all on the PowerPC G5.

And, of course, Phalanx.

Tord

5-10% is not that much. I do evaluate internal nodes.
The king safty evaluation of Snitch is quite big. Today I use lazy evaluation so its called only in about 10-20% of the nodes. I'd like to drop lazy evaluation in favor of a eval cache but looking at your experiences it doesn't look that promising.
By the way - anybody using both lazy evaluation and evaluation caching ?

Klaus

Klaus Friedel wrote:5-10% is not that much.

No, it isn't, especially when you consider that it is even less in slow games.

I do evaluate internal nodes. The king safty evaluation of Snitch is quite big. Today I use lazy evaluation so its called only in about 10-20% of the nodes. I'd like to drop lazy evaluation in favor of a eval cache but looking at your experiences it doesn't look that promising.

Perhaps not, but why not give it a try? It is probably just a few dozen lines of code, and takes about 15 minutes to implement. Perhaps your eval is much more expensive than mine, and your speedup will be bigger.

By the way - anybody using both lazy evaluation and evaluation caching ?

Not me. Lazy eval wouldn't work well in Glaurung. The only sensible way to do lazy eval seems to be to compute the biggest evaluation terms first, and to omit the smaller terms if the preliminary score is too far outside the (alpha,beta) window. In my case, the most expensive parts of my eval are also the ones which produce the biggest scores (especially king safety), so lazy eval would be almost worthless.

Tord

Tord Romstad wrote:Not me. Lazy eval wouldn't work well in Glaurung. The only sensible way to do lazy eval seems to be to compute the biggest evaluation terms first, and to omit the smaller terms if the preliminary score is too far outside the (alpha,beta) window. In my case, the most expensive parts of my eval are also the ones which produce the biggest scores (especially king safety), so lazy eval would be almost worthless.

Tord

Same for me. Lazy eval works surprisingly well anyway. As far as I remember you evalaute internal nodes like me. So you should take into account that the eval one ply deeper will not change that much. I do material and PSQ and try to estimate a window the final score will be in by looking at the evaluation one ply earlier.
I have to add that internal nodes are not evaluated lazy.

Klaus

Code: Select all

What replacement scheme do you use ?

What hit rate could I expect in a typical middle game position ?



I use always replace. I have never thought of any other replacement scheme because i couldnt think of a way to choose one position over the other. Since i also store lazy eval score in hash table , may be i have a choice not to overwrite real score with a lazy score.
I think that more interesting is trying many probes (up to 8). For my main hash table this scheme did not work better than the simple two-table approach.

The hitrate is around 25-30% in midgame for me, and 40-50% in late middle game . It can rise up to 70 in the endgame!
My measurements are based on a few blitz games but i think this is enough. Since the table is not cleared between moves, the percentage rises on every move made. I used to be confused when eveyone said their pawnhash table hit was close to 99% when mine usually is 92-93% at best. Well i found out that the problem was i was mearuing things on testsuites, and when i measured it on actual games it was actually 99%.

Code: Select all

Not me. Lazy eval wouldn't work well in Glaurung. The only sensible way to do lazy eval seems to be to compute the biggest evaluation terms first, and to omit the smaller terms if the preliminary score is too far outside the (alpha,beta) window. In my case, the most expensive parts of my eval are also the ones which produce the biggest scores (especially king safety), so lazy eval would be almost worthless.


IIRC you use futility pruning inside qsearch, if i did not miss someting,
this is the same as lazy eval only that it is done before move is made.

Daniel

Daniel Shawul wrote:IIRC you use futility pruning inside qsearch,

I do. I don't really like it, but disabling it slows down my search too much. I hope to replace it with something more accurate some day.

if i did not miss someting, this is the same as lazy eval only that it is done before move is made.

The way I use the terms "lazy eval" and "futility pruning", they are not quite the same. Lazy eval is based on the current position alone, and not the move used to reach the position or the eval of the position one ply further up in the tree. Futility pruning takes a position which have been fully evaluated and a move from this position, and tries to estimate an upper bound for what the score can be after this move is made. The techniques are related, but different.

Tord

Daniel Shawul wrote:

Code: Select all

What replacement scheme do you use ?

What hit rate could I expect in a typical middle game position ?



I use always replace. I have never thought of any other replacement scheme because i couldnt think of a way to choose one position over the other. Since i also store lazy eval score in hash table , may be i have a choice not to overwrite real score with a lazy score.
I think that more interesting is trying many probes (up to 8). For my main hash table this scheme did not work better than the simple two-table approach.

The hitrate is around 25-30% in midgame for me, and 40-50% in late middle game . It can rise up to 70 in the endgame!
My measurements are based on a few blitz games but i think this is enough. Since the table is not cleared between moves, the percentage rises on every move made. I used to be confused when eveyone said their pawnhash table hit was close to 99% when mine usually is 92-93% at best. Well i found out that the problem was i was mearuing things on testsuites, and when i measured it on actual games it was actually 99%.

Code: Select all

Not me. Lazy eval wouldn't work well in Glaurung. The only sensible way to do lazy eval seems to be to compute the biggest evaluation terms first, and to omit the smaller terms if the preliminary score is too far outside the (alpha,beta) window. In my case, the most expensive parts of my eval are also the ones which produce the biggest scores (especially king safety), so lazy eval would be almost worthless.


IIRC you use futility pruning inside qsearch, if i did not miss someting,
this is the same as lazy eval only that it is done before move is made.

Daniel

I use evaluation hash table as well (replace always) and my hit rate is almost identical with yours. I typically see 30+% in the middlegame and much more in the late endgame. I haven't tried multiple probes into the table, this is an interesting idea, probably worth exploring.

regards,
--tom

Here is a update of my eval cache efforts.
Short summary: Does not work for me.

I made a version with lazy eval disabled and allways replace eval cache. But the nps went down 20% (allmost regardles of cache size).
Any combination with a very conservative lazy eval and eval cache only caching the fully evaluated scores gave no improvement.
So for Snitch I will keep lazy eval and toss away the eval cache.

Regards,

Klaus

Why would you want a separate cache for the evaluation if you already have a transposition hash table? You either did not encounter the position before, or you did, in which case you should have stored everything you need to know about it in the hash table. It is the same set of nodes that you would want to preserve in both cases, namely those that gives you the most hits.

For end leaves the evaluation is simply the value of the node, and automatically stored. If your algorithm requires the evaluation in nodes that have unsufficient depth or inadequate bounds, so that a search is necessary, the logical place to store it is together with the other information about this node. How much can it be, 2 bytes? In a separate table you would duplicate all the overhead associated with the hashing, space-wise (a 4-byte lock) and time-wise (an extra non-local access to DRAM).

The size of the transposition table and evaluation cache are very different,
so adding an extra entry for the static evaluation of the nodes is very costy. The same thing also applies for the pawn hash table, which is usually a few Kbs, now if we add the pawn hash table entry (some people use up to 128bytes!) to the transposition table entry your total entries will be much much less. Also some dont evaluate internal nodes,so no need to allocate extra space in those cases.

H.G.Muller wrote:Why would you want a separate cache for the evaluation if you already have a transposition hash table? You either did not encounter the position before, or you did, in which case you should have stored everything you need to know about it in the hash table. It is the same set of nodes that you would want to preserve in both cases, namely those that gives you the most hits.

Your replacement scheme for the two tables is different (depth based vs. allways replace). (Infact snitch uses both depth and allways replace in main transposition table, but that's another story).
The sizes may differ greatly. (Eval cache is much smaller).
You don't wont to pollute your valuable depth-based hashtable with less important eval cache entries. A hashtable entry may save you serveral 1000 of nodes while a eval entry saves you one only !
The eval cache is used everywhere - internal nodes to leaves.
The normal hashtable is used in main search only (no gain for me if used in qsearch).

Thats why one might want to use two tables.
As said in my previous post it dosn't pay off for Snitch anyway.

Klaus

Well, if you don't evaluate in internal nodes, you don't need to store this information in an extra field of your main hash-table entry. Because for end leaves the evaluation is simply the value of that position, and goes into the hash table anyway.

For those that would need the evaluation in internal nodes: Despite the fact that hash-table hits can save you a tremendous amount of work, in practice that does not seem to occur frequently enough to have a dramatic impact on performance. With a good replacement scheme, the search time only very weakly depends on hash-table size. (For me the slowdown is a factor 1.5 when I reduce the table size by 256.) Increasing the entry size from 12 to 14 bytes just decreases the number of entries by 14%. (Most likely it will not decrease it at all, because you picked the number of entries not to completely fill the available memory, but to be a convenient number, like a power of 2, and the extra 14% can be fit in memory that would otherwise remain unused.)

The point is that hash-table hits that save you a lot of work per hit occur very infrequently. And they will still occur in a somewhat smaller hash table, because of the depth-preferred replacement: the decrease in hash-table size goes exclusively at the expense of the number of the shallow entries, that you could not all store anyway, and that continually force each other out of the table.

A hash-table that only uses depth-preferred replacement performs very poorly as soon as the loading factor approaches or exceeds 1. For people that have both a replace-always and a depth-preferred table, they can decide to include the field for the static evaluation only in the replace-always table. I don't see a reason why you would want a different size for the replace-always part of your main hash table and the evaluation cache. This part of the hash table will be almost exclusively filled with entries of the lowest draft, on which you never save an approximately fixed amount of search effort on a hit. Just as not having to redo the evaluation would. The raw hit rate can be very high here, but when I collected statistics only a very small fraction of the hits had a stored draft that was enough to satisfy the request, and the search would have to be done anyway. It could have a real impact if you would get the evaluation for free on such a hit, because the evaluation would be valid for any requested remaining depth.

It is easy enough to try...