Had anyone tried EvalHashTable?

[ILikeChess]

Almost every engine has large eval function.So why not store eval score into small HashTable which I called EvalHashTable?

I do not think probe and store EvalHashTable will cost a lot of time, but EvalHash could avoid computering many many many boring codes.

[Uri Blass]

Almost every engine has large eval function.So why not store eval score into small HashTable which I called EvalHashTable?

I do not think probe and store EvalHashTable will cost a lot of time, but EvalHash could avoid computering many many many boring codes.

I already use evalhash table and I believe that other authors do the same.

Uri

[jesper_nielsen]

I tried it, but the end result was a 10% slowdown.

But my evaluation function is still very simple, and i have some fairly agressive pruning based upon lazy evaluation.

But i will try it again, once my evaluation function matures.

- Jesper

[hgm]

The main concern with an Eval Hash is that the evaluation takes a limited amount of time, and that you must make sure that the cost of the EvalHash probes is less than that time. Access to a RAM-based table (so one that does not fit in cache) takes 286 clocks on my (slow) Pentium-M machine, and is likely to cost even more on a fast machine. So one can do nearly 1000 instructions for the cost of one probe. That is a lot of evaluation.

With the main hash the trade-off is completely different, as a hash hit might allow you to prune a sub-tree of unlimited size.

You might try it with an EvaHash table that is small enough to fit in your L2 cache, for which the probing does not take significant time. E.g. if you have a 1MB L2 cache, try it with a 256KB table (32K entries if their size is 8 byte). You will get fewer hits, but the hits that you get are nearly free.

[Peter Fendrich]

Alaric have no evalhaash but maybe I will look at that when the evaluation is more loaded with stuff. Currently there is almost nothing...
/Peter

[Uri Blass]

The main concern with an Eval Hash is that the evaluation takes a limited amount of time, and that you must make sure that the cost of the EvalHash probes is less than that time. Access to a RAM-based table (so one that does not fit in cache) takes 286 clocks on my (slow) Pentium-M machine, and is likely to cost even more on a fast machine. So one can do nearly 1000 instructions for the cost of one probe. That is a lot of evaluation.

With the main hash the trade-off is completely different, as a hash hit might allow you to prune a sub-tree of unlimited size.

You might try it with an EvaHash table that is small enough to fit in your L2 cache, for which the probing does not take significant time. E.g. if you have a 1MB L2 cache, try it with a 256KB table (32K entries if their size is 8 byte). You will get fewer hits, but the hits that you get are nearly free.

I found that for me bigger eval hash is better.
Note that I evaluate every node and with small eval hash tables I am afraid I will get almost no hits.

I also found that pawn hash table of some mbytes make movei slightly faster relative to no hash.

I did not try pawn hash of 256 KB table
Maybe for pawn hash it is better to have smaller hash because here I probably can earn more from 256 mbyte table and I have the same pawn structure many times.

Note that my pawn evaluation(score that is dependent only on pawn structure) is probably not efficient in terms of speed but I cannot believe that it is slower than the full evaluation function of most engines.

I do not understand what is the meaning of 286 clocks on your slow pentium M-machine and I would like to have some translation to times in terms of 1/10^6 seconds.

Do you think that the times are the same with a faster machine or do you think that the times are simply not faster enough with a faster machine and it may cost less time but more than 286 cycles?

Uri

[Dann Corbit]

Almost every engine has large eval function.So why not store eval score into small HashTable which I called EvalHashTable?

I do not think probe and store EvalHashTable will cost a lot of time, but EvalHash could avoid computering many many many boring codes.

Everyone who has a complicated eval function does this.
I have inserted eval hash into a couple of different programs.
Usually, the speedup is modest.

[Uri Blass]

Alaric have no evalhaash but maybe I will look at that when the evaluation is more loaded with stuff. Currently there is almost nothing...
/Peter

I do not believe it.
With almost nothing in the evaluation it could not be a strong program.

Maybe you are better than other people in doing the same thing faster and I did not care much about speed of my evaluation function but it cannot be almost nothing.

Uri

[hgm]

I found that for me bigger eval hash is better.
Note that I evaluate every node and with small eval hash tables I am afraid I will get almost no hits.

I also found that pawn hash table of some mbytes make movei slightly faster relative to no hash.

Well, if your evaluation takes longer to compute than a hash probe divided by the hit rate, the a bigger table is always better. What I suggest applies to the opposite case. There will be an upper limit to the hit rate, as even an asymptotically large table will havee misses when a position is encountered for the first time. If even in that case computing the eval is still faster than probing for it, the only thing that could help is make the probing faster. And for that you would have to make the table fit L2.

I do not understand what is the meaning of 286 clocks on your slow pentium M-machine and I would like to have some translation to times in terms of 1/10^6 seconds.

Do you think that the times are the same with a faster machine or do you think that the times are simply not faster enough with a faster machine and it may cost less time but more than 286 cycles?

My Pentium M runs at 1.3GHz, so that is 13 CPU clocks per 10 ns. The multiplier ratio was 13, so the Front-Side Bus was running at 100 MHz (this is advertized by Intel as 400MHz, because the bus is ' quad pumped' , meaning that 4 data words (of 64 bits) can be transferred per FSB clock cycle). So one memory access takes 22 FSB clocks, or 220 ns = 0.22/10^6 sec.

This is including the write-back time of the old cache contents, so it is actually the average time it takes to do 2 memory accesses, one read and one write. As these seem to occur partly in parallel, access with only clean cash (that has not been written, and so can be discarded rather than having to be written back) is slightly faster. (Something like 234 clocks, IIRC.)

In principle this time is constant: if I would have a Pentium M at 1.6GHz the multiplier would be 16, but such a Pentium M would still have the '400 MHz' FSB, and the same chip set (containing the memory controller), and would thus also take 22 FSB cycles for the memory operations. But in that case it would be 352 CPU clocks.

Now with Intel chips with faster FSB (e.g. 533 MHz, or 1066 MHz, meaning that the bus spead in reality is 133MHz or 266 MHz) you cannot count on that it also takes 22 FSB cycles: the access time is mainly determined by memory technology. Only the transfer time between the North bridge of the Chipset and the CPU will be faster, but from memory to North bridge will be the same (unless your machine also requires faster memory modules). I have not measured exactly yet how much this matters.

On an Athlon64 in principle the same holds, except that memory access is systematically faster because the North bridge is taken out of the loop, and the CPU is connected to the memory directly. But also there the access time is determined by the memory technology, and independent of the CPU speed. So the faster your CPU, the less competative it will be to hash things in main memory.

[ILikeChess]

What is the percentage of EvalHashTable hit rate do you prefer to got?

It looks very worthy to try.