Had anyone tried EvalHashTable?

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

Had anyone tried EvalHashTable?

Post by ILikeChess » Wed May 23, 2007 1:33 pm

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
Posts: 8586
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: Had anyone tried EvalHashTable?

Post by Uri Blass » Wed May 23, 2007 1:39 pm

ILikeChess wrote: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

Re: Had anyone tried EvalHashTable?

Post by jesper_nielsen » Wed May 23, 2007 2:18 pm

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

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

Re: Had anyone tried EvalHashTable?

Post by hgm » Wed May 23, 2007 2:59 pm

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

Re: Had anyone tried EvalHashTable?

Post by Peter Fendrich » Wed May 23, 2007 5:15 pm

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
Posts: 8586
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: Had anyone tried EvalHashTable?

Post by Uri Blass » Wed May 23, 2007 5:23 pm

hgm wrote: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
Posts: 10112
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: Had anyone tried EvalHashTable?

Post by Dann Corbit » Wed May 23, 2007 6:22 pm

ILikeChess wrote: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
Posts: 8586
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: Had anyone tried EvalHashTable?

Post by Uri Blass » Wed May 23, 2007 6:37 pm

JP wrote: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

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

Re: Had anyone tried EvalHashTable?

Post by hgm » Wed May 23, 2007 6:49 pm

Uri Blass wrote: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

Re: Had anyone tried EvalHashTable?

Post by ILikeChess » Wed May 23, 2007 6:51 pm

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

It looks very worthy to try.

Post Reply