Is there a reasonable number of pawn hash entries?

[Kempelen]

Hello,

I don't know if someone has made any kind of statistical study to see how many different pawn formation is on average, or the max number seen, based on depth. I ask this because this would be a nice data in order to correctly allocate the pawn hash table size.

Fermin

[bob]

Hello,

I don't know if someone has made any kind of statistical study to see how many different pawn formation is on average, or the max number seen, based on depth. I ask this because this would be a nice data in order to correctly allocate the pawn hash table size.

Fermin

Simplest is to test. I did this in Crafty, basically by running several positions for a fixed amount of time, with a constant (and way too big) pawn hash. Hit rate is typically 99%+. Run same test with 1/2 as much memory. Keep repeating until the hit rate drops enough to show you are beginning to lose useful entries. You now know the right size for that time control. Try a couple of other time limits, and you should be able to create a simple function such that f(time) -> optimal phash size...

[diep]

Hello,

I don't know if someone has made any kind of statistical study to see how many different pawn formation is on average, or the max number seen, based on depth. I ask this because this would be a nice data in order to correctly allocate the pawn hash table size.

Fermin

Yeah i did such estimates on the back of an envelope quite some years ago.

I noticed quite some bigger pawnhashtable was 1% faster at specific processors for Diep, usually the types we can't afford.

Now Diep might consider more stuff in pawncode than any other program so i doubt any other program has this behaviour.

[Daniel Shawul]

I did a test on 5 bratko kopec positions for 20 secs each. There is almost no improvement from additional pawn hash entries. The smallest number of entries I tried was 32k ~ 0.8MB and it is so far the best. Look at the nps figure for each of the positions below. Ofcourse the result will depend on time control used. I think smaller pawn hash table is good idea as most of it can reside in cache.

Code: Select all

pht 32768 X 24 = 0.8 MB

                Nodes     Time      NPS      splits     bad
                =====     ====      ===      ======     ===
             21620882    15.70    1377213        0        0
             18107168    15.31    1182315        0        0
             20899027    16.97    1231890        0        0
             18887991    16.00    1180794        0        0
             23305020    20.04    1162925        0        0
pht 65536 X 24 = 1.5 MB

                Nodes     Time      NPS      splits     bad
                =====     ====      ===      ======     ===
             21620882    15.59    1386754        0        0
             18107168    16.09    1125437        0        0
             20899027    17.50    1193889        0        0
             18887991    16.13    1170912        0        0
             23105001    20.03    1153692        0        0
pht 131072 X 24 = 3.0 MB

                Nodes     Time      NPS      splits     bad
                =====     ====      ===      ======     ===
             21620882    16.04    1347935        0        0
             18107168    15.49    1169185        0        0
             20899027    17.16    1217892        0        0
             18887991    16.15    1169752        0        0
             23005001    20.00    1150077        0        0
pht 262144 X 24 = 6.0 MB

                Nodes     Time      NPS      splits     bad
                =====     ====      ===      ======     ===
             21620882    15.79    1369190        0        0
             18107168    15.30    1183475        0        0
             20899027    16.96    1231963        0        0
             18887991    15.99    1181090        0        0
             23005001    20.01    1149732        0        0
pht 524288 X 24 = 12.0 MB

                Nodes     Time      NPS      splits     bad
                =====     ====      ===      ======     ===
             21620882    15.70    1377213        0        0
             18107168    15.33    1181005        0        0
             20899027    17.00    1229643        0        0
             18887991    16.00    1180499        0        0
             23105001    20.08    1150819        0        0
pht 1048576 X 24 = 24.0 MB

                Nodes     Time      NPS      splits     bad
                =====     ====      ===      ======     ===
             21620882    15.70    1376950        0        0
             18107168    15.32    1181544        0        0
             20899027    16.99    1230150        0        0
             18887991    16.17    1167944        0        0
             23105001    20.08    1150647        0        0
pht 2097152 X 24 = 48.0 MB

                Nodes     Time      NPS      splits     bad
                =====     ====      ===      ======     ===
             21620882    15.96    1354776        0        0
             18107168    15.49    1169260        0        0
             20899027    17.19    1215483        0        0
             18887991    16.16    1168522        0        0
             22305008    20.09    1110364        0        0
pht 4194304 X 24 = 96.0 MB

                Nodes     Time      NPS      splits     bad
                =====     ====      ===      ======     ===
             21620882    15.87    1362717        0        0
             18107168    15.47    1170318        0        0
             20899027    17.22    1214001        0        0
             18887991    16.17    1168088        0        0
             23105001    20.08    1150418        0        0
pht 8388608 X 24 = 192.0 MB

                Nodes     Time      NPS      splits     bad
                =====     ====      ===      ======     ===
             21620882    16.16    1338339        0        0
             18107168    15.48    1169713        0        0
             20899027    17.20    1215201        0        0
             18887991    16.17    1167871        0        0
             23005001    20.01    1149502        0        0

[lucasart]

Hello,

I don't know if someone has made any kind of statistical study to see how many different pawn formation is on average, or the max number seen, based on depth. I ask this because this would be a nice data in order to correctly allocate the pawn hash table size.

Fermin

Simplest is to test. I did this in Crafty, basically by running several positions for a fixed amount of time, with a constant (and way too big) pawn hash. Hit rate is typically 99%+. Run same test with 1/2 as much memory. Keep repeating until the hit rate drops enough to show you are beginning to lose useful entries. You now know the right size for that time control. Try a couple of other time limits, and you should be able to create a simple function such that f(time) -> optimal phash size...

I also did a similar experiment, in order to estimate the pawn hash size. And I eventually used 0x10000 hash entries. My hit rate however, was more around 90%, but I use the kings positions into the pawn hash key (as I do some basic pawn shelter stuff and passed pawn eval depends on relative king position).

[diep]

Hello,

I don't know if someone has made any kind of statistical study to see how many different pawn formation is on average, or the max number seen, based on depth. I ask this because this would be a nice data in order to correctly allocate the pawn hash table size.

Fermin

Simplest is to test. I did this in Crafty, basically by running several positions for a fixed amount of time, with a constant (and way too big) pawn hash. Hit rate is typically 99%+. Run same test with 1/2 as much memory. Keep repeating until the hit rate drops enough to show you are beginning to lose useful entries. You now know the right size for that time control. Try a couple of other time limits, and you should be able to create a simple function such that f(time) -> optimal phash size...

I also did a similar experiment, in order to estimate the pawn hash size. And I eventually used 0x10000 hash entries. My hit rate however, was more around 90%, but I use the kings positions into the pawn hash key (as I do some basic pawn shelter stuff and passed pawn eval depends on relative king position).

simple solution, set it on 0x800000 entries then.

[marcelk]

I don't know if someone has made any kind of statistical study to see how many different pawn formation is on average, or the max number seen, based on depth. I ask this because this would be a nice data in order to correctly allocate the pawn hash table size.

I settled on 2**18 entries total with bucket size 2. Both pawn and king locations are in the hash. Details are here.
I haven't observed a notable relation between hit rate and search time and I'm also interested to see measurement results of those who do see an effect that is more than marginal.

[Kempelen]

I did a test on 5 bratko kopec positions for 20 secs each. There is almost no improvement from additional pawn hash entries. The smallest number of entries I tried was 32k ~ 0.8MB and it is so far the best. Look at the nps figure for each of the positions below. Ofcourse the result will depend on time control used. I think smaller pawn hash table is good idea as most of it can reside in cache.

After doing some tests I arrive to conclude that 65535 entries is the best for my engine fast games.

[lucasart]

I did a test on 5 bratko kopec positions for 20 secs each. There is almost no improvement from additional pawn hash entries. The smallest number of entries I tried was 32k ~ 0.8MB and it is so far the best. Look at the nps figure for each of the positions below. Ofcourse the result will depend on time control used. I think smaller pawn hash table is good idea as most of it can reside in cache.

After doing some tests I arrive to conclude that 65535 entries is the best for my engine fast games.

Surely you mean 65536 ? If it's not a power of two you'll have to do a dichotomic search which is a waste of time. I also use 0x10000 = 65536 pawn hash entries.

[Kempelen]

I did a test on 5 bratko kopec positions for 20 secs each. There is almost no improvement from additional pawn hash entries. The smallest number of entries I tried was 32k ~ 0.8MB and it is so far the best. Look at the nps figure for each of the positions below. Ofcourse the result will depend on time control used. I think smaller pawn hash table is good idea as most of it can reside in cache.

After doing some tests I arrive to conclude that 65535 entries is the best for my engine fast games.

Surely you mean 65536 ? If it's not a power of two you'll have to do a dichotomic search which is a waste of time. I also use 0x10000 = 65536 pawn hash entries.

Yes, I wanted to mean that.