average hit rate of pawn hash tables?

[cyberfish]

Hi,
I just tried implementing a pawn hash table in my chess engine. I am using a 8MB table and the hit rate is ~87%. Does that number look right? I've heard somewhere else I don't remember that it should be way higher than that (~99% if I remembered correctly). Can someone please clarify?

Thank you

[bob]

Hi,
I just tried implementing a pawn hash table in my chess engine. I am using a 8MB table and the hit rate is ~87%. Does that number look right? I've heard somewhere else I don't remember that it should be way higher than that (~99% if I remembered correctly). Can someone please clarify?

Thank you

Crafty is always at 99%. Very few calls to EvaluatePawns() are actually done, but there must be some so 100% is impossible.

[mjlef]

99% is typical for a pawns only hash. If you include king positions this drops (so your rate may indicated you include king positions).

[cyberfish]

Thanks for the replies. In my engine I am only hashing the pawns (of both sides). Is that how everyone's doing it?

Also, what replacement schemes should be used? I am doing always-replace with my pawn table right now.

[gladius]

I get about 94% for the starting position with an 8mb pawn hash. A few moves out of the opening though (once pieces have some mobility), and the hit rate is sitting above 99% consistently.

I only hash pawn positions, but that means that I still have to run my passed pawn evaluation code on every eval as the king position affects the scores. That is a very minor cost though, especially as passed pawns aren't around most of the time, and the pawn hash can store which pawns are passed.

[cyberfish]

hmm I see, I was only using the starting position =) turns out mine has a hit rate of ~99% in the midgame too.

Thanks for your help

[Zach Wegner]

Also, what replacement schemes should be used? I am doing always-replace with my pawn table right now.

Always replace is the only thing that makes any sense, really.

[hgm]

Why do you think that would be better than, say, Least-Recent Used of 2 or 4 (or as many entries that fit in your cache line)?

[Zach Wegner]

Well, I don't use any bucket system for the pawn hash. And anyways, not even one of my entries will fit in a cache line, and I don't expect many people's to fit either.

Perhaps if you did make a bucket system, and keep track of the "age", it would be marginally better. I don't think it would make much difference, especially considering the overhead in cache thrashing.

[hgm]

If you need multiple cache-line accesses anyway, it would be best to store the hash key and age information of several entries all in the first cache line you probe. Then You can conclude from that single access if you have a hit or not, and if not, which entry you will replace. And then the rest of the accesses can be for that entry only.