Buckets for pawn hash?

[Aleks Peshkov]

The purpose for buckets is to provide better replacement decisions.

I do not know any better then LRU replacement scheme for pawn hash buckets. And LRU works badly with recursive nature of search tree.

[bob]

Not sure where your 0.25 comes from. The correct calculation would be

0.99 + C*0.01 = 1.99 (C = 100)
0.995 + C*0.005 = 1.495

1.495/1.99 = 75% = 100% - 25%.

OK, I will try again.

C = cost for basic pawn evaluation. HC = cost to manage basic pawn approach.

We hit 99% already, so the current cost is

cost = .99 * HC + .01 * C.

Using a bucket approach:

cost = .9925 * HC' + .0075 * C

First gets 99% hits, second gets 99.25% hits. Subtract and you get .0075C, assuming HC and HC' are the same, which they are not. Logically HC' is at least 4x HC since there would be four bucket entries to manage, in reality it would be more, but this works. So HC' = 4HC

with the first simple version, we get .99HC + 0.01C
with the bucket version, we get 3.97HC + .0075C

Now assuming C = 100 X HC (cost 100x as much to compute as to look up, we get

.99HC + .01*100HC = 1.99HC

with the second,

3.97HC + .0075*100HC = 4.72HC

The 4 bucket approach costs about 2x more than the 1bucket approach, unless I missed something...

[bob]

The purpose for buckets is to provide better replacement decisions.

I do not know any better then LRU replacement scheme for pawn hash buckets. And LRU works badly with recursive nature of search tree.

First, the majority of the pawn evaluations don't have to be looked up. The majority of the positions searched only move pieces doing captures, leaving the pawns along much of the time. You can recognize this with some care and not even access the pawn hash table.

Beyond that, I only use one hash entry for pawns... And the only reason my pawn hashing doesn't hit 100% is that there must be a few misses early on, which makes integer truncation show 99%. In reality it is 99.5% at worst.

As far as LRU goes, it is certainly better than random.

[hgm]

Logically HC' is at least 4x HC since there would be four bucket entries to manage, in reality it would be more, but this works. So HC' = 4HC

Normally the probe cost would be strongly dominated by the cost of the memory access to fetch the bucket. So HC ~ HC'.

[tpetzke]

1) How much is pawn evaluation from scratch cost comparing to total evaluation cost? How often it is actually needed when lazy evaluation shortcut active?

It is not only the evaluation, the pawn hash stores information that is required to evaluate other terms, like outposts on weak squares, rook on open file etc.... So it is not just a midgame and a endgame score, but much more.

I don't have lazy eval.

2) It is always O(1) savings, while regular transposition table can save magnitude of whole search time.

Yes, but for something executed at the leaves (O1) is nice. I never said you should substitute the TT with a pawn hash. And if you redirect a few MB from the TT for a pawn hash it should be an overall gain.

3) Pawn cache "table" with just 1 record would have decent hit rate.

Yes, and with some more slots it is even better.

[bob]

Logically HC' is at least 4x HC since there would be four bucket entries to manage, in reality it would be more, but this works. So HC' = 4HC

Normally the probe cost would be strongly dominated by the cost of the memory access to fetch the bucket. So HC ~ HC'.

In testing, I added one member to a bucket in Crafty, using 12 byte rather than 16 byte entries (4 bytes of padding on end of each bucket). It was enough slower that I removed it. The replacement loop isn't quite free, and historically this table doesn't need to be that big, causing huge cache traffic on SMP boxes where 20+ cores are modifying the data at a HIGH rate of speed.

And, there is critical-word-first which means accessing 16 bytes in a cache block is faster than accessing all 64, as with 64 you have to wait for the entire line to be filled in, while with one entry you don't...

I checked a few middle game positions and my hash hit rate is in the 99.6-99.8% range. For fine #70, about the best case scenario for pawn hashing, I saw 99.97% So we are really talking about a fraction of 1% to start with, and then saving some fraction of that fraction...

[bob]

1) How much is pawn evaluation from scratch cost comparing to total evaluation cost? How often it is actually needed when lazy evaluation shortcut active?

It is not only the evaluation, the pawn hash stores information that is required to evaluate other terms, like outposts on weak squares, rook on open file etc.... So it is not just a midgame and a endgame score, but much more.

I don't have lazy eval.

2) It is always O(1) savings, while regular transposition table can save magnitude of whole search time.

Yes, but for something executed at the leaves (O1) is nice. I never said you should substitute the TT with a pawn hash. And if you redirect a few MB from the TT for a pawn hash it should be an overall gain.

3) Pawn cache "table" with just 1 record would have decent hit rate.

Yes, and with some more slots it is even better.

Not much better. I ran a few MG and EG positions and hits averaged over 99.5%, so there is very little room for improvement over just a single entry probe.

[hgm]

But that could of course mean that your table is unnecessary large.

[tpetzke]

I don't get a 99,5% hit rate even with more slots. Last time I measured I had something like 97% which went down to 93% when I included the kings into the hash.

http://macechess.blogspot.de/2013/07/po ... -pawn.html

[bob]

I don't get a 99,5% hit rate even with more slots. Last time I measured I had something like 97% which went down to 93% when I included the kings into the hash.

http://macechess.blogspot.de/2013/07/po ... -pawn.html

Why would you include kings in a "pawn hash"???