A pre-calculated pawn hash table ?

[Rebel]

Well, maybe...

A pawn hash table is used to speed-up the evaluation function. Since the pawn structures of white and black don't change that much during the search it's long recognized that hashing pawns is beneficial and will result in an average (citations needed!) hit-rate of 90% and a 10% overall speed-up.

The idea of a pre-calculated hash table (loaded at program start) in theory could speed-up an engine even more provided we are able to increase the number of 90% to for example 95%. Hardly maintenance then also.

....

http://rebel13.nl/rebel13/ideas.html#13

[chrisw]

Well, maybe...

A pawn hash table is used to speed-up the evaluation function. Since the pawn structures of white and black don't change that much during the search it's long recognized that hashing pawns is beneficial and will result in an average (citations needed!) hit-rate of 90% and a 10% overall speed-up.

The idea of a pre-calculated hash table (loaded at program start) in theory could speed-up an engine even more provided we are able to increase the number of 90% to for example 95%. Hardly maintenance then also.

....

http://rebel13.nl/rebel13/ideas.html#13

is there a figure for the count of actual discrete pawn conformations arising in normal games? Also arising within search, which is more to the point, I guess.

[Joost Buijs]

Well, maybe...

A pawn hash table is used to speed-up the evaluation function. Since the pawn structures of white and black don't change that much during the search it's long recognized that hashing pawns is beneficial and will result in an average (citations needed!) hit-rate of 90% and a 10% overall speed-up.

The idea of a pre-calculated hash table (loaded at program start) in theory could speed-up an engine even more provided we are able to increase the number of 90% to for example 95%. Hardly maintenance then also.

....

http://rebel13.nl/rebel13/ideas.html#13

In theory yes, but such a table has to be so very large that it is not feasible, not in a hundred years.

A small pawn hash-table works because the pawn structure changes very slowly during the course of the game, but when you want to store all permutations possible you need 3^48 entries. Some permutations can never occur during normal game play, but the table still has to be very large.

[Joost Buijs]

Well, maybe...

A pawn hash table is used to speed-up the evaluation function. Since the pawn structures of white and black don't change that much during the search it's long recognized that hashing pawns is beneficial and will result in an average (citations needed!) hit-rate of 90% and a 10% overall speed-up.

The idea of a pre-calculated hash table (loaded at program start) in theory could speed-up an engine even more provided we are able to increase the number of 90% to for example 95%. Hardly maintenance then also.

....

http://rebel13.nl/rebel13/ideas.html#13

In theory yes, but such a table has to be so large that it is not feasible, not in a hundred years.

A small pawn hash-table works because the pawn structure changes very slowly during the course of the game, but when you want to store all permutations possible you need 3^48 entries. Some permutations can never occur during normal game play, but still the table has to be very large.

[chrisw]

Well, maybe...

A pawn hash table is used to speed-up the evaluation function. Since the pawn structures of white and black don't change that much during the search it's long recognized that hashing pawns is beneficial and will result in an average (citations needed!) hit-rate of 90% and a 10% overall speed-up.

The idea of a pre-calculated hash table (loaded at program start) in theory could speed-up an engine even more provided we are able to increase the number of 90% to for example 95%. Hardly maintenance then also.

....

http://rebel13.nl/rebel13/ideas.html#13

In theory yes, but such a table has to be so very large that it is not feasible, not in a hundred years.

A small pawn hash-table works because the pawn structure changes very slowly during the course of the game, but when you want to store all permutations possible you need 3^48 entries. Some permutations can never occur during normal game play, but the table still has to be very large.

The question is, how large? Or, if only 99.9% of actually attained pawn conformations are accounted for, the outliers can be calculated cheaply on the fly.

So, how large is large?

[Rebel]

Well, maybe...

A pawn hash table is used to speed-up the evaluation function. Since the pawn structures of white and black don't change that much during the search it's long recognized that hashing pawns is beneficial and will result in an average (citations needed!) hit-rate of 90% and a 10% overall speed-up.

The idea of a pre-calculated hash table (loaded at program start) in theory could speed-up an engine even more provided we are able to increase the number of 90% to for example 95%. Hardly maintenance then also.

....

http://rebel13.nl/rebel13/ideas.html#13

is there a figure for the count of actual discrete pawn conformations arising in normal games? Also arising within search, which is more to the point, I guess.

I tried a Lichess download of 16 million games, unique pawn structures 132 million. Can't measure the hit-rate because I currently can't create a bigger pawn hash table than 32 million.

[Rebel]

Well, maybe...

A pawn hash table is used to speed-up the evaluation function. Since the pawn structures of white and black don't change that much during the search it's long recognized that hashing pawns is beneficial and will result in an average (citations needed!) hit-rate of 90% and a 10% overall speed-up.

The idea of a pre-calculated hash table (loaded at program start) in theory could speed-up an engine even more provided we are able to increase the number of 90% to for example 95%. Hardly maintenance then also.

....

http://rebel13.nl/rebel13/ideas.html#13

In theory yes, but such a table has to be so very large that it is not feasible, not in a hundred years.

A small pawn hash-table works because the pawn structure changes very slowly during the course of the game, but when you want to store all permutations possible you need 3^48 entries. Some permutations can never occur during normal game play, but the table still has to be very large.

You probably already have a working pawn hash table in Nightmare so a possible gain has to be seen, see the remark on the page.

2. Engine authors who already have a good working pawn hash table (with all the usual and unusual extras) likely won't profit much. On the other hand engine authors without a pawn hash table with this system easily could implement one from the EPD's.

Nevertheless don't you think it's already a small miracle that from the in theory almost 5 billion possible pawn structures a selection of 1.3 million can produce a hit-rate of 97% ?

[Joost Buijs]

Well, maybe...

A pawn hash table is used to speed-up the evaluation function. Since the pawn structures of white and black don't change that much during the search it's long recognized that hashing pawns is beneficial and will result in an average (citations needed!) hit-rate of 90% and a 10% overall speed-up.

The idea of a pre-calculated hash table (loaded at program start) in theory could speed-up an engine even more provided we are able to increase the number of 90% to for example 95%. Hardly maintenance then also.

....

http://rebel13.nl/rebel13/ideas.html#13

In theory yes, but such a table has to be so very large that it is not feasible, not in a hundred years.

A small pawn hash-table works because the pawn structure changes very slowly during the course of the game, but when you want to store all permutations possible you need 3^48 entries. Some permutations can never occur during normal game play, but the table still has to be very large.

The question is, how large? Or, if only 99.9% of actually attained pawn conformations are accounted for, the outliers can be calculated cheaply on the fly.

So, how large is large?

That is a question that I don't know the answer to. Of course, you can scan a very large database of games and it might turn out that the number of different pawn-structures that occur in practice is not so high at all. On the other hand if such a hash-table has to be several GB in size the 10% speed gain will be diminished to zero.

Using PEXT to calculate an index into a table with structural data for each pawn is already faster than the standard way of doing things, at least on Intel processors this is the case (hopefully AMD fixed this in Zen2), so the gain with a large pawn hash-table may be non existent.

[Joost Buijs]

Well, maybe...

A pawn hash table is used to speed-up the evaluation function. Since the pawn structures of white and black don't change that much during the search it's long recognized that hashing pawns is beneficial and will result in an average (citations needed!) hit-rate of 90% and a 10% overall speed-up.

The idea of a pre-calculated hash table (loaded at program start) in theory could speed-up an engine even more provided we are able to increase the number of 90% to for example 95%. Hardly maintenance then also.

....

http://rebel13.nl/rebel13/ideas.html#13

In theory yes, but such a table has to be so very large that it is not feasible, not in a hundred years.

A small pawn hash-table works because the pawn structure changes very slowly during the course of the game, but when you want to store all permutations possible you need 3^48 entries. Some permutations can never occur during normal game play, but the table still has to be very large.

You probably already have a working pawn hash table in Nightmare so a possible gain has to be seen, see the remark on the page.

2. Engine authors who already have a good working pawn hash table (with all the usual and unusual extras) likely won't profit much. On the other hand engine authors without a pawn hash table with this system easily could implement one from the EPD's.

Nevertheless don't you think it's already a small miracle that from the in theory almost 5 billion possible pawn structures a selection of 1.3 million can produce a hit-rate of 97% ?

I just measured it, Nightmare has 8MB pawn-hash per thread, it stores only passed pawns and the pawn-structure score. On the initial position (depth 20) the speed gain due to the pawn-table is exactly 12%.

[hgm]

The Pawn hash table has a high hit rate because a typical search tree only contains a very small fraction of all possible Pawn structures. And this is a consequence of most moves in the tree not being Pawn moves or captures of a Pawn, and sequences of Pawn moves having a high chance of being transpositions (because there are lots of Pawns, which mostly move independently).

If you want a higher hit rate, you can simply use a larger table. It doesn't really help to get a higher hit rate when the time spent on misses is already negligible. With 95% hit rate the time spent on doing Pawn-structure evaluation is already reduced by a factor 20. Whether this is already negligible depends a bit how complex and efficient that evaluation is. Of course expanding the table involves some cost by itself, because a larger table will drive up the number of (level-3) cache misses. So that the extra hits this gives you might actually be slow hits.

That you can get such a high hit rate with a table that can only contain such a tiny fraction of all possible Pawns constellations tells us that Pawn structure is a very 'local' property, the 'neighborhood' of the current root position wandering through the vastly larger 'pawn-structure space' during the game. That also tells there is very little benefit in precalculating one particular neighborhood, (like that of the opening position), as you would drift away from it pretty quickly, in many possible directions. Precalculating a significant fraction of all these neighborhoods might make the table so large that it would be slower to probe it (in DRAM) than to evaluate on the fly. It is also not clear how representative positions that occur in actual games are for what you would encounter in a typical search tree.

BTW, a sharper bound on the number of Pawn constellations than 3^48 (which also counts cases like having 48 black Pawns) is 2^64. (3^48 = (1.5*2)^48 = 1.5^48 * 2^48 = 2.25^24 * 2^48 > 2^24 * 2^48 = 2^72.) Uri Brass once pointed out that you need 48 bits to indicate Pawn occupation of the 48 Pawn-accessible squares, and that an additional 16 bits are then enough to flag which of the 16 Pawns that can maximally be in there are black. An even more accurate estimate, which takes account of the fact that you can have at most 8 white and 8 black Pawns, is 2^55. For exactly 16 Pawns it is 2^54.68 (= 48!/(16!*32!) * 16!/(8!*8!)), but the number decreases very fast when there are fewer Pawns.) This still does not take account of the fact that most of the Pawn constellations would be unreachable from the initial position.