Pawn Hash

[Don]

Zoning do not work for me because i calculate more than pawn shield which depend on specific king locations. My open files around king eval, and pawn storm depend on the exact location of the king.

Many programs include the king position in the pawn hash.

I hope not, it absolutely kills hash hit rate. In Cray Blitz we actually did a king safety hash, which included pawns + K in a separate table. The hit rate was never even 50%, whereas the normal pawn hash hit rate (for me) is always > 99%. most pawn scoring has nothing to do with king position. Giving up 50% hits could make a program many times slower than it needs to be.

Komodo considers kings in the pawn structure hash and the hit rate is high, though not as high as pure pawn. It's still something like 95% or more. I do pawn shelter and pawn storms based on stage of game. You should get WAY OVER 50% so I don't understand this.

[bob]

Zoning do not work for me because i calculate more than pawn shield which depend on specific king locations. My open files around king eval, and pawn storm depend on the exact location of the king.

Many programs include the king position in the pawn hash.

I hope not, it absolutely kills hash hit rate. In Cray Blitz we actually did a king safety hash, which included pawns + K in a separate table. The hit rate was never even 50%, whereas the normal pawn hash hit rate (for me) is always > 99%. most pawn scoring has nothing to do with king position. Giving up 50% hits could make a program many times slower than it needs to be.

Komodo considers kings in the pawn structure hash and the hit rate is high, though not as high as pure pawn. It's still something like 95% or more. I do pawn shelter and pawn storms based on stage of game. You should get WAY OVER 50% so I don't understand this.

I think it was depth-related. If you remember, we did king-safety as a separate hash in Cray Blitz. Back when 10 plies was a pretty deep middlegame search. I decided to do the "all in one" approach I use today to avoid that completely. I don't really see how it makes a difference whether the king is at g1 or h1 when evaluating the pawn shelter. It makes a difference overall, but certainly doesn't change the pawn structure situation at all...

[Daniel Shawul]

Are you guys sure it is indeed anything close to 90% ? Because with what I have now (king squares stored and checked later but not xored), I get hit rate of <60% but not greater than that. The higher values are rare which occur only in the opening position, both in middle game and endgame the numbers are significantly lower. I would really like to see hit rate stat of one game at 40/3 or 40/5 tc. Here is a quick game I did at 40/5 and corresponding stat. As you can see hit rate went very low, infact I didn't expect it would go as low as 10%! (May be i have some bug).

Legend
[%d %d %d] -> hist, misses, percentage
This counts are recorded when there is a pawn tt hit, i.e for the same pawn formation, how does the king location affect it.
The question that you guys are asking may be slightly different, because in your case you can store multiple king locations for the same pawn formation. I guess if see those 90% numbers i would believe it and move on with implementation:)

Code: Select all

[1108970 776435 58]
[1315651 659532 66]
[1181802 820181 59]
[1006917 669125 60]
[910024 618023 59]
[300810 163206 64]
[1361601 700191 66]
[1215886 849353 58]
[1284711 892976 58]
[1222456 907141 57]
[923351 758808 54]
[842715 667602 55]
[147418 131628 52]
[196144 350161 35]
[1889 1782 51]
[301 1205 19]
[40 224 15]
[74 1188 5]
[139 5170 2]
[177 3829 4]
[1077 8943 10]
[1037 8069 11]
[2574 14601 14]
[3426 37120 8]
[8281 59490 12]
[3249 23587 12]
[2093 10524 16]
[3532 23708 12]
[7354 74127 9]
[3593 36572 8]
[7279 69204 9]
[6492 59466 9]
[10136 116970 7]
[34023 186648 15]
[10055 38164 20]
[16699 74029 18]
[285124 2037373 12]
[46995 358318 11]
[8522 118072 6]
[63385 529812 10]
[62628 800119 7]
[16825 152349 9]
[42325 328875 11]

The game

Code: Select all

[FEN "1rbq1rk1/1pp2pbp/p1np1np1/4p3/2PPP3/2N1BP2/PP1Q2PP/R1N1KB1R w KQ e6 0 1 "]

1.d4d5 c6d4 2.c1e2 c7c5 3.d5c6 d4c6 4.e2g3 c8e6 5.f1d3 c6d4 6.g3e2 d8b6 7.e1g1 g7h6 8.e2d4 h6e3 
9.d2e3 e5d4 10.e3f2 f6d7 11.c3d5 e6d5 12.c4d5 b8c8 13.a1d1 d7e5 14.f1e1 b6a5 15.a2a3 e5d3 16.d1d3 c8c2 
17.b2b4 c2f2 18.b4a5 f2a2 19.e1c1 f7f5 20.d3d4 a2a3 21.d4b4 f5e4 22.f3e4 f8f7 23.b4b6 a3a5 24.b6d6 a5a2 
25.c1f1 f7c7 26.d6f6 c7c2 27.f6f8 g8g7 28.f1f7 g7h6 29.f7f2 a2a1 30.f2f1 a1a4 31.f8f4 a4d4 32.f1f2 c2c4 
33.f2b2 b7b5 34.b2a2 b5b4 35.a2a1 c4c3 36.f4h4 h6g7 37.h4f4 b4b3 38.a1f1 a6a5 39.h2h3 b3b2 40.f4f7 g7h6 
41.f1b1 c3c1 42.f7f1 c1b1 43.f1b1 d4d2 44.h3h4 a5a4 45.g2g4 a4a3 46.g4g5 h6h5 47.b1f1 

[bob]

Are you guys sure it is indeed anything close to 90% ? Because with what I have now (king squares stored and checked later but not xored), I get hit rate of <60% but not greater than that. The higher values are rare which occur only in the opening position, both in middle game and endgame the numbers are significantly lower. I would really like to see hit rate stat of one game at 40/3 or 40/5 tc. Here is a quick game I did at 40/5 and corresponding stat. As you can see hit rate went very low, infact I didn't expect it would go as low as 10%! (May be i have some bug).

Legend
[%d %d %d] -> hist, misses, percentage
This counts are recorded when there is a pawn tt hit, i.e for the same pawn formation, how does the king location affect it.
The question that you guys are asking may be slightly different, because in your case you can store multiple king locations for the same pawn formation. I guess if see those 90% numbers i would believe it and move on with implementation:)

Code: Select all

[1108970 776435 58]
[1315651 659532 66]
[1181802 820181 59]
[1006917 669125 60]
[910024 618023 59]
[300810 163206 64]
[1361601 700191 66]
[1215886 849353 58]
[1284711 892976 58]
[1222456 907141 57]
[923351 758808 54]
[842715 667602 55]
[147418 131628 52]
[196144 350161 35]
[1889 1782 51]
[301 1205 19]
[40 224 15]
[74 1188 5]
[139 5170 2]
[177 3829 4]
[1077 8943 10]
[1037 8069 11]
[2574 14601 14]
[3426 37120 8]
[8281 59490 12]
[3249 23587 12]
[2093 10524 16]
[3532 23708 12]
[7354 74127 9]
[3593 36572 8]
[7279 69204 9]
[6492 59466 9]
[10136 116970 7]
[34023 186648 15]
[10055 38164 20]
[16699 74029 18]
[285124 2037373 12]
[46995 358318 11]
[8522 118072 6]
[63385 529812 10]
[62628 800119 7]
[16825 152349 9]
[42325 328875 11]

The game

Code: Select all

[FEN "1rbq1rk1/1pp2pbp/p1np1np1/4p3/2PPP3/2N1BP2/PP1Q2PP/R1N1KB1R w KQ e6 0 1 "]

1.d4d5 c6d4 2.c1e2 c7c5 3.d5c6 d4c6 4.e2g3 c8e6 5.f1d3 c6d4 6.g3e2 d8b6 7.e1g1 g7h6 8.e2d4 h6e3 
9.d2e3 e5d4 10.e3f2 f6d7 11.c3d5 e6d5 12.c4d5 b8c8 13.a1d1 d7e5 14.f1e1 b6a5 15.a2a3 e5d3 16.d1d3 c8c2 
17.b2b4 c2f2 18.b4a5 f2a2 19.e1c1 f7f5 20.d3d4 a2a3 21.d4b4 f5e4 22.f3e4 f8f7 23.b4b6 a3a5 24.b6d6 a5a2 
25.c1f1 f7c7 26.d6f6 c7c2 27.f6f8 g8g7 28.f1f7 g7h6 29.f7f2 a2a1 30.f2f1 a1a4 31.f8f4 a4d4 32.f1f2 c2c4 
33.f2b2 b7b5 34.b2a2 b5b4 35.a2a1 c4c3 36.f4h4 h6g7 37.h4f4 b4b3 38.a1f1 a6a5 39.h2h3 b3b2 40.f4f7 g7h6 
41.f1b1 c3c1 42.f7f1 c1b1 43.f1b1 d4d2 44.h3h4 a5a4 45.g2g4 a4a3 46.g4g5 h6h5 47.b1f1 

What I am assuming we are talking about is to compute a zobrist hash signature by xoring in the Zobrist random numbers for each white and black pawn's location as well as those of both kings. That makes it safe to hash anything that depends only on pawn or king locations. I don't believe this is necessary, since for pawn shelter, whether the king is on g1 or h1 is irrelevant, it is the fact that the king is in that corner area that is important. I eventually identified left, center and right as "king zones" and compute the pawn shelter scores for each and store 'em in the same pawn hash (without the king locations hashed in). Then I just pick the appropriate pawn shelter term out of the 3 depending on where the king is. And I get way more hits that way.

[Don]

Are you guys sure it is indeed anything close to 90% ? Because with what I have now (king squares stored and checked later but not xored), I get hit rate of <60% but not greater than that. The higher values are rare which occur only in the opening position, both in middle game and endgame the numbers are significantly lower. I would really like to see hit rate stat of one game at 40/3 or 40/5 tc. Here is a quick game I did at 40/5 and corresponding stat. As you can see hit rate went very low, infact I didn't expect it would go as low as 10%! (May be i have some bug).

Legend
[%d %d %d] -> hist, misses, percentage
This counts are recorded when there is a pawn tt hit, i.e for the same pawn formation, how does the king location affect it.
The question that you guys are asking may be slightly different, because in your case you can store multiple king locations for the same pawn formation. I guess if see those 90% numbers i would believe it and move on with implementation:)

Code: Select all

[1108970 776435 58]
[1315651 659532 66]
[1181802 820181 59]
[1006917 669125 60]
[910024 618023 59]
[300810 163206 64]
[1361601 700191 66]
[1215886 849353 58]
[1284711 892976 58]
[1222456 907141 57]
[923351 758808 54]
[842715 667602 55]
[147418 131628 52]
[196144 350161 35]
[1889 1782 51]
[301 1205 19]
[40 224 15]
[74 1188 5]
[139 5170 2]
[177 3829 4]
[1077 8943 10]
[1037 8069 11]
[2574 14601 14]
[3426 37120 8]
[8281 59490 12]
[3249 23587 12]
[2093 10524 16]
[3532 23708 12]
[7354 74127 9]
[3593 36572 8]
[7279 69204 9]
[6492 59466 9]
[10136 116970 7]
[34023 186648 15]
[10055 38164 20]
[16699 74029 18]
[285124 2037373 12]
[46995 358318 11]
[8522 118072 6]
[63385 529812 10]
[62628 800119 7]
[16825 152349 9]
[42325 328875 11]

The game

Code: Select all

[FEN "1rbq1rk1/1pp2pbp/p1np1np1/4p3/2PPP3/2N1BP2/PP1Q2PP/R1N1KB1R w KQ e6 0 1 "]

1.d4d5 c6d4 2.c1e2 c7c5 3.d5c6 d4c6 4.e2g3 c8e6 5.f1d3 c6d4 6.g3e2 d8b6 7.e1g1 g7h6 8.e2d4 h6e3 
9.d2e3 e5d4 10.e3f2 f6d7 11.c3d5 e6d5 12.c4d5 b8c8 13.a1d1 d7e5 14.f1e1 b6a5 15.a2a3 e5d3 16.d1d3 c8c2 
17.b2b4 c2f2 18.b4a5 f2a2 19.e1c1 f7f5 20.d3d4 a2a3 21.d4b4 f5e4 22.f3e4 f8f7 23.b4b6 a3a5 24.b6d6 a5a2 
25.c1f1 f7c7 26.d6f6 c7c2 27.f6f8 g8g7 28.f1f7 g7h6 29.f7f2 a2a1 30.f2f1 a1a4 31.f8f4 a4d4 32.f1f2 c2c4 
33.f2b2 b7b5 34.b2a2 b5b4 35.a2a1 c4c3 36.f4h4 h6g7 37.h4f4 b4b3 38.a1f1 a6a5 39.h2h3 b3b2 40.f4f7 g7h6 
41.f1b1 c3c1 42.f7f1 c1b1 43.f1b1 d4d2 44.h3h4 a5a4 45.g2g4 a4a3 46.g4g5 h6h5 47.b1f1 

What I am assuming we are talking about is to compute a zobrist hash signature by xoring in the Zobrist random numbers for each white and black pawn's location as well as those of both kings. That makes it safe to hash anything that depends only on pawn or king locations. I don't believe this is necessary, since for pawn shelter, whether the king is on g1 or h1 is irrelevant, it is the fact that the king is in that corner area that is important. I eventually identified left, center and right as "king zones" and compute the pawn shelter scores for each and store 'em in the same pawn hash (without the king locations hashed in). Then I just pick the appropriate pawn shelter term out of the 3 depending on where the king is. And I get way more hits that way.

I compute the 3 files nearest the king - which is f,g,h if the king is on the g or h file. However I don't just do king safety. The kings distance to the square in front of passed pawns is considered for the endgame and factored into the pawn structure score, so all 64 squares matter for me.

Perhaps I should measure the hit rate again. I have found in the past that it's pretty low in the opening position but very rapidly increases as soon as pawns start moving and get committed.

[Don]

Perhaps I should measure the hit rate again. I have found in the past that it's pretty low in the opening position but very rapidly increases as soon as pawns start moving and get committed.

Ok, I took a quick and dirty measurement. This "hit" rate in the opening position is about 89% and it gradually increases as moves are played.

After 10 moves by both sides it is 93% and at move 16 in my test it was over 95%.

Of course it will probably vary significantly by position - by I used an open position to do this test. In a closed pawn structure the hit rate will be higher and in open positions lower.

90+ is a reasonably good hit rate but not enough to assume that everything is free. You still cannot be too sloppy.

[Daniel Shawul]

That is just not enough. Can you do one full game until the end ?
I had also the highest hit rates roughly until move 16 but significanlty went down once the position opended
up for the king. Also we have to look into the amount of calculation that goes into regular pawn evaluation, and
that involves king safetly. Since the former is usually more time consuming than the later, a small decrease in hit rate
does affect the over all speed significanlty. Note that in my case , I always have the highest pawn tt hit rate (99%) since
the key is not smeared with king locations. Whatever i get from storing king locations and their associated score is a bonus.
So <60% hit rate for that is acceptable. But for your case a slight decrease in pawn-king tt hit rate could be significant loss
in speed overall.

[Don]

That is just not enough. Can you do one full game until the end ?
I had also the highest hit rates roughly until move 16 but significanlty went down once the position opended
up for the king. Also we have to look into the amount of calculation that goes into regular pawn evaluation, and
that involves king safetly. Since the former is usually more time consuming than the later, a small decrease in hit rate
does affect the over all speed significanlty. Note that in my case , I always have the highest pawn tt hit rate (99%) since
the key is not smeared with king locations. Whatever i get from storing king locations and their associated score is a bonus.
So <60% hit rate for that is acceptable. But for your case a slight decrease in pawn-king tt hit rate could be significant loss
in speed overall.

My pawn structure attempts to be efficient, I am not sloppy with it and do not assume it's free. It's not super sophisticated but it attempt to be relatively complete. The pawn storm part is relatively cheap. There is much more to king safety that I do not do in the pawn structure.

Everything is relative, the only question of any relevance for me is how much useful stuff can I do with a given amount of resource. Sure I could speed up pawn structure by not hashing the kings - but then how expensive would it be to do the other stuff? What would be the total cost be of moving this out into the main evaluation?

When I get some time I'll try to do some complete games to get the hash table hit rate. Of course this number must be compared with the total execution time of computing the pawn/king structure evaluation.

[bob]

Are you guys sure it is indeed anything close to 90% ? Because with what I have now (king squares stored and checked later but not xored), I get hit rate of <60% but not greater than that. The higher values are rare which occur only in the opening position, both in middle game and endgame the numbers are significantly lower. I would really like to see hit rate stat of one game at 40/3 or 40/5 tc. Here is a quick game I did at 40/5 and corresponding stat. As you can see hit rate went very low, infact I didn't expect it would go as low as 10%! (May be i have some bug).

Legend
[%d %d %d] -> hist, misses, percentage
This counts are recorded when there is a pawn tt hit, i.e for the same pawn formation, how does the king location affect it.
The question that you guys are asking may be slightly different, because in your case you can store multiple king locations for the same pawn formation. I guess if see those 90% numbers i would believe it and move on with implementation:)

Code: Select all

[1108970 776435 58]
[1315651 659532 66]
[1181802 820181 59]
[1006917 669125 60]
[910024 618023 59]
[300810 163206 64]
[1361601 700191 66]
[1215886 849353 58]
[1284711 892976 58]
[1222456 907141 57]
[923351 758808 54]
[842715 667602 55]
[147418 131628 52]
[196144 350161 35]
[1889 1782 51]
[301 1205 19]
[40 224 15]
[74 1188 5]
[139 5170 2]
[177 3829 4]
[1077 8943 10]
[1037 8069 11]
[2574 14601 14]
[3426 37120 8]
[8281 59490 12]
[3249 23587 12]
[2093 10524 16]
[3532 23708 12]
[7354 74127 9]
[3593 36572 8]
[7279 69204 9]
[6492 59466 9]
[10136 116970 7]
[34023 186648 15]
[10055 38164 20]
[16699 74029 18]
[285124 2037373 12]
[46995 358318 11]
[8522 118072 6]
[63385 529812 10]
[62628 800119 7]
[16825 152349 9]
[42325 328875 11]

The game

Code: Select all

[FEN "1rbq1rk1/1pp2pbp/p1np1np1/4p3/2PPP3/2N1BP2/PP1Q2PP/R1N1KB1R w KQ e6 0 1 "]

1.d4d5 c6d4 2.c1e2 c7c5 3.d5c6 d4c6 4.e2g3 c8e6 5.f1d3 c6d4 6.g3e2 d8b6 7.e1g1 g7h6 8.e2d4 h6e3 
9.d2e3 e5d4 10.e3f2 f6d7 11.c3d5 e6d5 12.c4d5 b8c8 13.a1d1 d7e5 14.f1e1 b6a5 15.a2a3 e5d3 16.d1d3 c8c2 
17.b2b4 c2f2 18.b4a5 f2a2 19.e1c1 f7f5 20.d3d4 a2a3 21.d4b4 f5e4 22.f3e4 f8f7 23.b4b6 a3a5 24.b6d6 a5a2 
25.c1f1 f7c7 26.d6f6 c7c2 27.f6f8 g8g7 28.f1f7 g7h6 29.f7f2 a2a1 30.f2f1 a1a4 31.f8f4 a4d4 32.f1f2 c2c4 
33.f2b2 b7b5 34.b2a2 b5b4 35.a2a1 c4c3 36.f4h4 h6g7 37.h4f4 b4b3 38.a1f1 a6a5 39.h2h3 b3b2 40.f4f7 g7h6 
41.f1b1 c3c1 42.f7f1 c1b1 43.f1b1 d4d2 44.h3h4 a5a4 45.g2g4 a4a3 46.g4g5 h6h5 47.b1f1 

What I am assuming we are talking about is to compute a zobrist hash signature by xoring in the Zobrist random numbers for each white and black pawn's location as well as those of both kings. That makes it safe to hash anything that depends only on pawn or king locations. I don't believe this is necessary, since for pawn shelter, whether the king is on g1 or h1 is irrelevant, it is the fact that the king is in that corner area that is important. I eventually identified left, center and right as "king zones" and compute the pawn shelter scores for each and store 'em in the same pawn hash (without the king locations hashed in). Then I just pick the appropriate pawn shelter term out of the 3 depending on where the king is. And I get way more hits that way.

I compute the 3 files nearest the king - which is f,g,h if the king is on the g or h file. However I don't just do king safety. The kings distance to the square in front of passed pawns is considered for the endgame and factored into the pawn structure score, so all 64 squares matter for me.

I chose to simply compute whatever is needed for kings and other pieces, and stuff that in the pawn hash, and then use that stuff when I compute the score for the piece in question. Certainly improves the hit rate to factor king moves out of the equation. For endgames, I want to consider far more than just king position to passed pawns anyway...

Perhaps I should measure the hit rate again. I have found in the past that it's pretty low in the opening position but very rapidly increases as soon as pawns start moving and get committed.

[bob]

I decided to put a Pawn hash in my new engine, so that I can quickly hack in some passer recognition through a dumb algorithm, without having to worry about efficiency. I never used Pawn hash before. Does the following seem a reasonable implemetation:

I keep an extra 32-bit hash key, which uses the same randoms as the main hash key for Pawns, but zero keys for all other pieces. (In fact I derive them by ANDing the randoms fetched for the main hash with -IS_PAWN(piece), which seemed faster than setting up seprate tables.)

The Pawn hash itself is an array of integers, indexed by the low-order 18 bits of the key. It stores the hashed evaluation score in the 10 low-order bits, and the 22 high-order key bits in the rest, as signature.

In this scheme bits 10-17 are redundant, and do not contribute to avoiding collisions, as they were already implied by the address. I guess I could XOR these with 8 corresponding bits from my main hash key, if I make those bits only depend on Pawns there too (i.e. zero them for all other pieces). Would this degrade the opertion of the main hash table? I guess it would if I take bits for it that are used drectly in the index, but I could use bits from the signature. As I store only a 32-bits signature in the main hash, I guess there are some unused bits, which I could shift to the proper location for this purpose.

Would this be worth it, or would an 18-bit address and (effectively) a 14-bit signature be good enough?

I did a study a few years ago with 32 bit keys vs 64 keys and found no measurable difference in playing strength. I used a similar scheme where part of the 32 bit was also the address key and played something like 30,000 games.

However, that was a few years and that makes a world of difference. You will get lots of collisions, but the issue for playing strength is how often do those collisions actually affect the move choice? That is worth a few bits of "extra key" but with highly selective programs I suspect that it's not worth what it used to be worth a few years ago.

On the other hand, undetected collisions with the pawn structure hash is less likely to have a seriously negative affect that having these collisions with the full position signature.

My "intuition", for what (little) it's worth is that you can probably get away with this - a few undetected collision in the pawn structure hash is not going to cost you hardly anything in terms of raw ELO and mis-evaluations. However, I am quite sure you will get a fair number of collisions - and I'm sure you know how to make that calculation. But that calculation does not tell you how much ELO you will sacrifice.

If you are using this information to find passed pawns and/or to do something dynamic with them or some other aspect of pawn structure, your program better not make any assumptions because as we know you will get a lot of mis-evaluation. Komodo for instance stores the locations of the passed pawns computed from the pawn structure hash and does stuff with it during the slower evaluation.

Of course it's better if you can find a way to economically compute a separate address hash - but I know you are a minimalists. My feeling is that what you have described will be indistiguishable from a more anal approach. In fact if you do more and it costs you 1% slowdown it may actually be a slight weakening.

I can't stand _any_ collisions and don't get 'em with 64 bit signatures. I tried 32 but that crashes Crafty instantly. All of the pawn structure stuff I store for use later has to be right, for efficiency. If a mask says there is a passed pawn on file X, there had better be one or else something is going to break. If you don't store critical information that can break you if it is wrong, it is likely no worse than the hash paper results I wrote about a couple of years back. But if bad / corrupt data can crash your evaluation, then 32 is extremely dangerous at today's speeds