Winboard Forum

Does it make sense to store node evaluations into the transposition table?

Actually my opinion switches to not to store. What do you think about that?

Reinhard.

Reinhard Scharnagl wrote:Does it make sense to store node evaluations into the transposition table?

Actually my opinion switches to not to store. What do you think about that?

Hi Reinhard,

As far as I know, most people do not store the static evaluation in the transposition table. However, it is quite common to have a separate, smaller hash table for the static eval. I am not the right person to give advice about what makes sense -- I have never tried storing the static eval anywhere at all.

Tord

Tord,

it seems, that I have been not precise enough. I am talking of the dynamic evaluation values.

Reinhard.

Reinhard Scharnagl wrote:Tord,

it seems, that I have been not precise enough. I am talking of the dynamic evaluation values.

In that case, I'm afraid I don't understand at all. What does "dynamic evaluation values" mean? It sounds like it means the value returned from a search, which is of course exactly what we all store in our transposition tables ...

Tord

Tord,

such also were my thoughts in the beginning. But I noticed some miraculous effects with that evaluations. For long I haven't had any explanation, why Smirf was ever selecting a move, having a PV (created from the transposition table) leading to being mated, though the evaluation was far from that worst value. (You would not notice this effect, when creating the PV line during the search).

So the PV line constructed from the transposition table seems to be more actual than the reported evaluation. To solve that puzzle took me a lot of time. I always had thought, using the transposition table during search evaluation would support me with the most actual evaluation values. But that obviously was no longer true.

The first idea has been that there would be doubles with different values inside the TT. But that would not explain the existence of the dynamically created PV, using identical TT keys.

So lets see the explanation I actually have for this: suppose there is a set of PV lines leading to the same end position by differing using some transpositions. One of them will be recalculated using a higher depth (Smirf uses a sort of iterative deepening) and find a worse value, leading to that PV not being revisited the next time. But only the node values of that PV have been updated. So there are still some nodes along the sister PVs, which yet have old and misleading values stored for some of their nodes in the TT.

Thus the value of a node depends on the actual PV below of this node, which could have changed. That lead to my question here.

Reinhard.

Reinhard Scharnagl wrote:Tord,

such also were my thoughts in the beginning. But I noticed some miraculous effects with that evaluations. For long I haven't had any explanation, why Smirf was ever selecting a move, having a PV (created from the transposition table) leading to being mated, though the evaluation was far from that worst value. (You would not notice this effect, when creating the PV line during the search).

So the PV line constructed from the transposition table seems to be more actual than the reported evaluation. To solve that puzzle took me a lot of time. I always had thought, using the transposition table during search evaluation would support me with the most actual evaluation values. But that obviously was no longer true.

The first idea has been that there would be doubles with different values inside the TT. But that would not explain the existence of the dynamically created PV, using identical TT keys.

So lets see the explanation I actually have for this: suppose there is a set of PV lines leading to the same end position by differing using some transpositions. One of them will be recalculated using a higher depth (Smirf uses a sort of iterative deepening) and find a worse value, leading to that PV not being revisited the next time. But only the node values of that PV have been updated. So there are still some nodes along the sister PVs, which yet have old and misleading values stored for some of their nodes in the TT.

Thus the value of a node depends on the actual PV below of this node, which could have changed. That lead to my question here.

Reinhard.

I am afraid I do not exactly understand and an example with specific pvs can help.

If I understand correctly the problem is misleading information about the remaining depth of some nodes in the hash tables but I do not understand exactly what is the pronlem.

I do not use hash tables for pruning so I avoid this type of problems.

Uri

Reinhard,

A search's evaluation is always more reliable then a reconstructed PV from tt. (moves can get overwritten in tt all the time, from entirely different tree-parts.)

"Sister pv's" will also have other values, by the principle of alpha-beta.
If they don't, you have bugs, or a very unsound search.

From this:

"So lets see the explanation I actually have for this: suppose there is a set of PV lines leading to the same end position by differing using some transpositions. One of them will be recalculated using a higher depth (Smirf uses a sort of iterative deepening) and find a worse value, leading to that PV not being revisited the next time. But only the node values of that PV have been updated. So there are still some nodes along the sister PVs, which yet have old and misleading values stored for some of their nodes in the TT.
"

It seems you are getting your depths wrong.

I've never noticed the effect you are talking about, but you've to be carefull how you handle extentiondepths, reductions, and other things. (exentions and reductions that you already know of, at that node. Since you don't know what's going to happen below. As long as the same happens below in other parts of the tree, depth is safe. But if you have obscure path-dependant pruning or other such things, you've to do other tricks with your "depth". )

Stan

Tord Romstad wrote:

Reinhard Scharnagl wrote:Does it make sense to store node evaluations into the transposition table?

Actually my opinion switches to not to store. What do you think about that?

Hi Reinhard,

As far as I know, most people do not store the static evaluation in the transposition table. However, it is quite common to have a separate, smaller hash table for the static eval. I am not the right person to give advice about what makes sense -- I have never tried storing the static eval anywhere at all.

Tord

In Diep i do both.

Please keep into account that the eval hashtable in itself is having a hitrate of 10-20% which is pretty low, as a result of storing evaluation
also in transpositiontable.

Total hitrate (both combined) is about 50%.

In case of 10% hitrate there, that means that the EFFECTIVE cost of a lookup at a dual core opteron 2.2Ghz is about 2.2 cycles/ns * 2340 nanoseconds.

That's roughly 5000 cycles.

So in such a case such a seperated evaltable besides storing in normal hashtable makes less sense for majority of the chessprograms,
As it only makes sense if you have an evaluation that's far far slower than 5000 cycles.

For majority of efficient programmed programs that's simply not the case.

For diep, which slow search is getting around 85k nps at k7 2.1ghz,
or 107k nps at a 1.8Ghz opteron (single core measured) , obviously
on AVERAGE the number of cycles spent on 1 node is already 25000 cycles, just imagine a full eval if you also realize the 50% hitrate,
additional to the 4% cutoffs the transpositiontable roughly gives,
added to the facts that positions in check you don't eval and that
in the majority of innernodes no evaluation happens either.

What did amaze me a few months ago is that increasing the size of the evaluation table and pawntable considerable to in total 200MB speeded up my program about 2%. This at a single cpu k7 (from my dual k7 which has a 400 ns latency to ddr ram).

At a quad opteron dual core with in total 4 GB ram and 8 cores,
a transpositiontable of 2 GB, taking 200MB a processor extra is tad of a problem though.

Fact is you can for each new machine keep optimizing forever hashtables,
as with every type of latency and architecture a different strategy is best.

At a quad opteron dual core for example, diep's approach of using
local hashtables is not really the optimal idea.

A TLB trashing lookup to a remote processor is on average 234 ns,
a local lookup is like 147 ns. So the difference is just 70 ns.

This at 1.8Ghz is not much of a penalty.

So there is more possible there in theory, but it all is dependant upon the program in question and the hardware you intend to run it at.

Vincent

Hoi Vincent,

How is Diep-3D ?

Groeten,
Stan