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
Is there a reasonable number of pawn hash entries?
Moderators: hgm, Rebel, chrisw
-
- Posts: 620
- Joined: Fri Feb 08, 2008 10:44 am
- Location: Madrid - Spain
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Is there a reasonable number of pawn hash entries?
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...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
-
- Posts: 1822
- Joined: Thu Mar 09, 2006 11:54 pm
- Location: The Netherlands
Re: Is there a reasonable number of pawn hash entries?
Yeah i did such estimates on the back of an envelope quite some years ago.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
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.
-
- Posts: 4185
- Joined: Tue Mar 14, 2006 11:34 am
- Location: Ethiopia
Re: Is there a reasonable number of pawn hash entries?
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
-
- Posts: 3232
- Joined: Mon May 31, 2010 1:29 pm
- Full name: lucasart
Re: Is there a reasonable number of pawn hash entries?
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).bob wrote: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...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
-
- Posts: 1822
- Joined: Thu Mar 09, 2006 11:54 pm
- Location: The Netherlands
Re: Is there a reasonable number of pawn hash entries?
simple solution, set it on 0x800000 entries then.lucasart wrote: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).bob wrote: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...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
-
- Posts: 348
- Joined: Sat Feb 27, 2010 12:21 am
Re: Is there a reasonable number of pawn hash entries?
I settled on 2**18 entries total with bucket size 2. Both pawn and king locations are in the hash. Details are here.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 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.
-
- Posts: 620
- Joined: Fri Feb 08, 2008 10:44 am
- Location: Madrid - Spain
Re: Is there a reasonable number of pawn hash entries?
After doing some tests I arrive to conclude that 65535 entries is the best for my engine fast games.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.
-
- Posts: 3232
- Joined: Mon May 31, 2010 1:29 pm
- Full name: lucasart
Re: Is there a reasonable number of pawn hash entries?
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 wrote:After doing some tests I arrive to conclude that 65535 entries is the best for my engine fast games.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.
-
- Posts: 620
- Joined: Fri Feb 08, 2008 10:44 am
- Location: Madrid - Spain
Re: Is there a reasonable number of pawn hash entries?
Yes, I wanted to mean that.lucasart wrote: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 wrote:After doing some tests I arrive to conclude that 65535 entries is the best for my engine fast games.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.