Page 1 of 2
Is there a reasonable number of pawn hash entries?
Posted: Tue Jul 10, 2012 11:24 pm
by 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
Re: Is there a reasonable number of pawn hash entries?
Posted: Wed Jul 11, 2012 1:20 am
by bob
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...
Re: Is there a reasonable number of pawn hash entries?
Posted: Wed Jul 11, 2012 1:49 am
by diep
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.
Re: Is there a reasonable number of pawn hash entries?
Posted: Thu Jul 12, 2012 4:41 am
by 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
Re: Is there a reasonable number of pawn hash entries?
Posted: Fri Jul 13, 2012 6:08 am
by lucasart
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).
Re: Is there a reasonable number of pawn hash entries?
Posted: Sat Jul 14, 2012 11:54 am
by diep
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.
Re: Is there a reasonable number of pawn hash entries?
Posted: Sat Jul 14, 2012 12:46 pm
by marcelk
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.
Re: Is there a reasonable number of pawn hash entries?
Posted: Mon Jul 16, 2012 2:03 pm
by Kempelen
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.
Re: Is there a reasonable number of pawn hash entries?
Posted: Mon Jul 16, 2012 3:06 pm
by lucasart
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.
Re: Is there a reasonable number of pawn hash entries?
Posted: Mon Jul 16, 2012 3:47 pm
by Kempelen
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.