Is there a reasonable number of pawn hash entries?

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
Kempelen
Posts: 620
Joined: Fri Feb 08, 2008 9:44 am
Location: Madrid - Spain
Contact:

Is there a reasonable number of pawn hash entries?

Post by Kempelen » Tue Jul 10, 2012 9:24 pm

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
Fermin Serrano
Author of 'Rodin' engine
http://sites.google.com/site/clonfsp/

bob
Posts: 20392
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Is there a reasonable number of pawn hash entries?

Post by bob » Tue Jul 10, 2012 11:20 pm

Kempelen wrote: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
Posts: 1780
Joined: Thu Mar 09, 2006 10:54 pm
Location: The Netherlands
Contact:

Re: Is there a reasonable number of pawn hash entries?

Post by diep » Tue Jul 10, 2012 11:49 pm

Kempelen wrote: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
Posts: 3705
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: Is there a reasonable number of pawn hash entries?

Post by Daniel Shawul » Thu Jul 12, 2012 2:41 am

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

User avatar
lucasart
Posts: 3035
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: Is there a reasonable number of pawn hash entries?

Post by lucasart » Fri Jul 13, 2012 4:08 am

bob wrote:
Kempelen wrote: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
Posts: 1780
Joined: Thu Mar 09, 2006 10:54 pm
Location: The Netherlands
Contact:

Re: Is there a reasonable number of pawn hash entries?

Post by diep » Sat Jul 14, 2012 9:54 am

lucasart wrote:
bob wrote:
Kempelen wrote: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.

User avatar
marcelk
Posts: 348
Joined: Fri Feb 26, 2010 11:21 pm
Contact:

Re: Is there a reasonable number of pawn hash entries?

Post by marcelk » Sat Jul 14, 2012 10:46 am

Kempelen wrote: 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.

User avatar
Kempelen
Posts: 620
Joined: Fri Feb 08, 2008 9:44 am
Location: Madrid - Spain
Contact:

Re: Is there a reasonable number of pawn hash entries?

Post by Kempelen » Mon Jul 16, 2012 12:03 pm

Daniel Shawul wrote: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.
Fermin Serrano
Author of 'Rodin' engine
http://sites.google.com/site/clonfsp/

User avatar
lucasart
Posts: 3035
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: Is there a reasonable number of pawn hash entries?

Post by lucasart » Mon Jul 16, 2012 1:06 pm

Kempelen wrote:
Daniel Shawul wrote: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.

User avatar
Kempelen
Posts: 620
Joined: Fri Feb 08, 2008 9:44 am
Location: Madrid - Spain
Contact:

Re: Is there a reasonable number of pawn hash entries?

Post by Kempelen » Mon Jul 16, 2012 1:47 pm

lucasart wrote:
Kempelen wrote:
Daniel Shawul wrote: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.
Fermin Serrano
Author of 'Rodin' engine
http://sites.google.com/site/clonfsp/

Post Reply