Pawn Hash

[Don]

I can't stand _any_ collisions and don't get 'em with 64 bit signatures. I tried 32 but that crashes Crafty instantly. All of the pawn structure stuff I store for use later has to be right, for efficiency. If a mask says there is a passed pawn on file X, there had better be one or else something is going to break. If you don't store critical information that can break you if it is wrong, it is likely no worse than the hash paper results I wrote about a couple of years back. But if bad / corrupt data can crash your evaluation, then 32 is extremely dangerous at today's speeds

I agree, 32 is not enough and of course if you program depends on zero hash collisions to function properly without crashing, then I wonder if 64 bit is even enough. I tried running tests a while back against crafty using xboard and Crafty will crash every few days. Is that why?

[Don]

I decided to test my pawn structure with king stuff in the hopes of trying to determine if I could get some speed by moving some calculations outside of the pawn structure routine.

What I did was simply turn off the probe part, so that the program cannot see that there might be a hit. So essentially the program must calculate the pawn structure score EVERY time it calls the evaluation function.

I would like to appeal to others to try this same thing. I was surprised by the result and had previously believed that this was a major thing, but it's relatively minor. I would like to see what others are getting.

In the opening position, doing a 17 ply search a version of Komodo takes 18.8 seconds.

With the hashing part turned off, the program takes 21.2 seconds and looks at the same exact number of nodes. This is factor of only 1.13 - so the hashing helps but not as much as I had imagined. It seems to me that in the old days pawn structure hashing was worth a lot more for me.

I also did this same test with fixed depth searches in the autotester. I did 10 and 11 ply searches and in both cases the ratio was also about 1.13. I average the total thinking time over a few hundred games.

If you do the algebra, and I removed the king hashing and was able to achieve a 100% hash table hit rate and assuming I now have a 0.90 hit rate, I could only expect to gain slightly more than a 1% improvement, and that is not considering the slowdown from doing the extra calculations outside the pawn structure - which probably would be at least a 1% slowdown. So even under these idealized assumptions it would probably be a mistake for me to go to pawn only hashing.

I don't know if this is an accurate assessment, but I think of Komodo as having one of the better evaluations - mostly due to a lot of help from Larry Kaufman and a lot of hard work in this area.

So I'm pretty interested in answering the question, is something around 15% typical for the speedup due to pawn structure hashing? Of course the answer for each individual program will vary depending on how much work is done in the pawn structure routine and how efficiently it's coded as well as the hit rate.

By the way, my pawn structure hash table is fixed at 128 K entries.

[Dann Corbit]

I decided to test my pawn structure with king stuff in the hopes of trying to determine if I could get some speed by moving some calculations outside of the pawn structure routine.

What I did was simply turn off the probe part, so that the program cannot see that there might be a hit. So essentially the program must calculate the pawn structure score EVERY time it calls the evaluation function.

I would like to appeal to others to try this same thing. I was surprised by the result and had previously believed that this was a major thing, but it's relatively minor. I would like to see what others are getting.

In the opening position, doing a 17 ply search a version of Komodo takes 18.8 seconds.

With the hashing part turned off, the program takes 21.2 seconds and looks at the same exact number of nodes. This is factor of only 1.13 - so the hashing helps but not as much as I had imagined. It seems to me that in the old days pawn structure hashing was worth a lot more for me.

I also did this same test with fixed depth searches in the autotester. I did 10 and 11 ply searches and in both cases the ratio was also about 1.13. I average the total thinking time over a few hundred games.

If you do the algebra, and I removed the king hashing and was able to achieve a 100% hash table hit rate and assuming I now have a 0.90 hit rate, I could only expect to gain slightly more than a 1% improvement, and that is not considering the slowdown from doing the extra calculations outside the pawn structure - which probably would be at least a 1% slowdown. So even under these idealized assumptions it would probably be a mistake for me to go to pawn only hashing.

I don't know if this is an accurate assessment, but I think of Komodo as having one of the better evaluations - mostly due to a lot of help from Larry Kaufman and a lot of hard work in this area.

So I'm pretty interested in answering the question, is something around 15% typical for the speedup due to pawn structure hashing? Of course the answer for each individual program will vary depending on how much work is done in the pawn structure routine and how efficiently it's coded as well as the hit rate.

By the way, my pawn structure hash table is fixed at 128 K entries.

I guess that pawn hashing gives a much higher return when the board is sparse. I suggest this experiment:

Both sides get a king, three pawns, and a knight. Make a few boards with different pawn formations (pawns isolated, pawns locked, pawns connected) and see what value you get from pawn hash.

Another thing worth a look is to run against this EPD file with tablebase turned off and see what happens with pawn hashing:
http://cap.connx.com/epd/pawntest.epd.bz2

[Don]

I decided to test my pawn structure with king stuff in the hopes of trying to determine if I could get some speed by moving some calculations outside of the pawn structure routine.

What I did was simply turn off the probe part, so that the program cannot see that there might be a hit. So essentially the program must calculate the pawn structure score EVERY time it calls the evaluation function.

I would like to appeal to others to try this same thing. I was surprised by the result and had previously believed that this was a major thing, but it's relatively minor. I would like to see what others are getting.

In the opening position, doing a 17 ply search a version of Komodo takes 18.8 seconds.

With the hashing part turned off, the program takes 21.2 seconds and looks at the same exact number of nodes. This is factor of only 1.13 - so the hashing helps but not as much as I had imagined. It seems to me that in the old days pawn structure hashing was worth a lot more for me.

I also did this same test with fixed depth searches in the autotester. I did 10 and 11 ply searches and in both cases the ratio was also about 1.13. I average the total thinking time over a few hundred games.

If you do the algebra, and I removed the king hashing and was able to achieve a 100% hash table hit rate and assuming I now have a 0.90 hit rate, I could only expect to gain slightly more than a 1% improvement, and that is not considering the slowdown from doing the extra calculations outside the pawn structure - which probably would be at least a 1% slowdown. So even under these idealized assumptions it would probably be a mistake for me to go to pawn only hashing.

I don't know if this is an accurate assessment, but I think of Komodo as having one of the better evaluations - mostly due to a lot of help from Larry Kaufman and a lot of hard work in this area.

So I'm pretty interested in answering the question, is something around 15% typical for the speedup due to pawn structure hashing? Of course the answer for each individual program will vary depending on how much work is done in the pawn structure routine and how efficiently it's coded as well as the hit rate.

By the way, my pawn structure hash table is fixed at 128 K entries.

I guess that pawn hashing gives a much higher return when the board is sparse. I suggest this experiment:

Both sides get a king, three pawns, and a knight. Make a few boards with different pawn formations (pawns isolated, pawns locked, pawns connected) and see what value you get from pawn hash.

Another thing worth a look is to run against this EPD file with tablebase turned off and see what happens with pawn hashing:
http://cap.connx.com/epd/pawntest.epd.bz2

Hi Dan.

I've done a lot of these kinds of experiments before. In general when pawns come off the board the hit rate goes up very quickly. Even a few pawns that are wild and free produce high hit rates because there is a pretty finite number of configurations possible once 3 or 4 come off for each side.

Of course things change a bit when kings are hashed in. As the position becomes more open you get more positions where the king wanders around a lot.

I'm pretty sure it would be difficult to produce a position where my hit rate goes below 85% - but I will try a couple of endings with just pawns and kings that are relatively open and have wandering knights to mix things up a bit.

[bob]

I can't stand _any_ collisions and don't get 'em with 64 bit signatures. I tried 32 but that crashes Crafty instantly. All of the pawn structure stuff I store for use later has to be right, for efficiency. If a mask says there is a passed pawn on file X, there had better be one or else something is going to break. If you don't store critical information that can break you if it is wrong, it is likely no worse than the hash paper results I wrote about a couple of years back. But if bad / corrupt data can crash your evaluation, then 32 is extremely dangerous at today's speeds

I agree, 32 is not enough and of course if you program depends on zero hash collisions to function properly without crashing, then I wonder if 64 bit is even enough. I tried running tests a while back against crafty using xboard and Crafty will crash every few days. Is that why?

Not that I know of. I currently have about 10,000,000 games it has played on my cluster without a single crash. Every loss on time on ICC is logged and I am not seeing any (which results in a flag).

If it crashes, there's something up for sure. But after as many games as I have played, I'd hope that if I don't see one in 10,000,000, nobody else would see one at all.

[Don]

I can't stand _any_ collisions and don't get 'em with 64 bit signatures. I tried 32 but that crashes Crafty instantly. All of the pawn structure stuff I store for use later has to be right, for efficiency. If a mask says there is a passed pawn on file X, there had better be one or else something is going to break. If you don't store critical information that can break you if it is wrong, it is likely no worse than the hash paper results I wrote about a couple of years back. But if bad / corrupt data can crash your evaluation, then 32 is extremely dangerous at today's speeds

I agree, 32 is not enough and of course if you program depends on zero hash collisions to function properly without crashing, then I wonder if 64 bit is even enough. I tried running tests a while back against crafty using xboard and Crafty will crash every few days. Is that why?

Not that I know of. I currently have about 10,000,000 games it has played on my cluster without a single crash. Every loss on time on ICC is logged and I am not seeing any (which results in a flag).

If it crashes, there's something up for sure. But after as many games as I have played, I'd hope that if I don't see one in 10,000,000, nobody else would see one at all.

So the question is whether 64 bits is enough to make the probably of a crash so low that it's just not a consideration. Do you 64 bits to verify the position and additional bits for the address calculation?

[mcostalba]

I decided to test my pawn structure with king stuff in the hopes of trying to determine if I could get some speed by moving some calculations outside of the pawn structure routine.

What I did was simply turn off the probe part, so that the program cannot see that there might be a hit. So essentially the program must calculate the pawn structure score EVERY time it calls the evaluation function.

I would like to appeal to others to try this same thing. I was surprised by the result and had previously believed that this was a major thing, but it's relatively minor. I would like to see what others are getting.

I would suggest to measure the time to lookup the hash table, this is not zero.

You need a good profiler, ones that accounts for memory access latency and not only CPU cycles, and you can exactly measure the impact of the lookup.

In SF there is a time penalty, not that big as it was in the TT table before we started to use prefetching, but measurable anyhow.

[bob]

I can't stand _any_ collisions and don't get 'em with 64 bit signatures. I tried 32 but that crashes Crafty instantly. All of the pawn structure stuff I store for use later has to be right, for efficiency. If a mask says there is a passed pawn on file X, there had better be one or else something is going to break. If you don't store critical information that can break you if it is wrong, it is likely no worse than the hash paper results I wrote about a couple of years back. But if bad / corrupt data can crash your evaluation, then 32 is extremely dangerous at today's speeds

I agree, 32 is not enough and of course if you program depends on zero hash collisions to function properly without crashing, then I wonder if 64 bit is even enough. I tried running tests a while back against crafty using xboard and Crafty will crash every few days. Is that why?

Not that I know of. I currently have about 10,000,000 games it has played on my cluster without a single crash. Every loss on time on ICC is logged and I am not seeing any (which results in a flag).

If it crashes, there's something up for sure. But after as many games as I have played, I'd hope that if I don't see one in 10,000,000, nobody else would see one at all.

So the question is whether 64 bits is enough to make the probably of a crash so low that it's just not a consideration. Do you 64 bits to verify the position and additional bits for the address calculation?

No. I use a normal 64 bit signature and store the entire 64 bits in the hash entry. And I use part of that 64 bits for the probe address as well. I tested this for crash-safeness by running millions of cluster games with code included to check the data that I depend on, and had no failures. I am sure I get an occasional collision, but if so, at least the data I get does not wreck the program. I ran like this for a year or so after I found the original crash, before I decided it was safe enough to remove the test (it is obviously executed for every static eval, making the cost measurable even if not horribly high.)

Obviously it _could_ crash. And I had significant problems before I added the "lockless hash" idea to the pawn hash (already used it in normal hash). Once I took care of that, Crafty has not crashed in at least 50M games except when I did something to cause one, which does happen from time to time during debugging.

I take every crash as significant, because it can hint at a deeper problem (an invalid memory reference can crash, or just corrupt something that will hurt later). Actually, in the current version, the program will not crash if the data is bad, it will hang in an infinite loop, because it says "OK, there is one or more pawns on this file, so lets get 'em one at a time. But if there are none to start with, the loop will not terminate. I found that particular issue by seeing time losses about once every 1000 games on ICC or in cluster testing.

I apparently misspoke when I said this would cause a crash, it causes a hang. And I have seen no crashes and just a few time losses over the past 50M games on the cluster. Each time loss is carefully checked and is always a problem of just taking too much time and moving right after losing, rather than hanging. I don't see that at all if I use an increment, however, and all of my testing is with increment unless we are testing sudden-death type time usage changes...

Sorry for the rambling reply, but when I looked at the code to answer your question above, I realized I had made a statement that was inaccurate and wanted to fix it so that it won't come up at another time and I'd try to figure out what I meant and would not be able to.

[bob]

I decided to test my pawn structure with king stuff in the hopes of trying to determine if I could get some speed by moving some calculations outside of the pawn structure routine.

What I did was simply turn off the probe part, so that the program cannot see that there might be a hit. So essentially the program must calculate the pawn structure score EVERY time it calls the evaluation function.

I would like to appeal to others to try this same thing. I was surprised by the result and had previously believed that this was a major thing, but it's relatively minor. I would like to see what others are getting.

In the opening position, doing a 17 ply search a version of Komodo takes 18.8 seconds.

With the hashing part turned off, the program takes 21.2 seconds and looks at the same exact number of nodes. This is factor of only 1.13 - so the hashing helps but not as much as I had imagined. It seems to me that in the old days pawn structure hashing was worth a lot more for me.

I also did this same test with fixed depth searches in the autotester. I did 10 and 11 ply searches and in both cases the ratio was also about 1.13. I average the total thinking time over a few hundred games.

If you do the algebra, and I removed the king hashing and was able to achieve a 100% hash table hit rate and assuming I now have a 0.90 hit rate, I could only expect to gain slightly more than a 1% improvement, and that is not considering the slowdown from doing the extra calculations outside the pawn structure - which probably would be at least a 1% slowdown. So even under these idealized assumptions it would probably be a mistake for me to go to pawn only hashing.

I don't know if this is an accurate assessment, but I think of Komodo as having one of the better evaluations - mostly due to a lot of help from Larry Kaufman and a lot of hard work in this area.

So I'm pretty interested in answering the question, is something around 15% typical for the speedup due to pawn structure hashing? Of course the answer for each individual program will vary depending on how much work is done in the pawn structure routine and how efficiently it's coded as well as the hit rate.

By the way, my pawn structure hash table is fixed at 128 K entries.

Here is my result run as yours. First program is crafty with pawn hash disabled, second is normal crafty, both to depth 17, starting position.:

log.001: time=22.91 mat=0 n=28847342 fh=91% nps=1.3M
log.002: time=10.76 mat=0 n=28847342 fh=91% nps=2.7M

WAC2 to depth 21:

log.001: time=8.42 mat=0 n=23574168 fh=92% nps=2.8M
log.002: time=5.72 mat=0 n=23574168 fh=92% nps=4.1M

Kopec22 depth 16:

log.001: time=18.17 mat=0 n=36149661 fh=95% nps=2.0M
log.002: time=9.95 mat=0 n=36149661 fh=95% nps=3.6M

Huge differences for me.

Both versions were compiled with same Makefile, both using PGO, both using same hash sizes and everything (same .craftyrc file in same directory).

As a note, my pawn hashing is a two-level process. Three possible cases:

(1) current pawn structure is same as pawn structure for last call to Evaluate(). I don't even need to probe the pawn hash table, the data is already available in local data.

(2) current pawn structure is different from last position evaluated, I probe pawn hash and use that if found, copying it to local data so that it will be used in (1) above next call (if possible).

(3) Do the computations.

My pawn eval is not that cheap. I compute squares pawns can move to safely (only considering pawns for both sides) to determine which pawns can be protected (if they are not) as opposed to which pawns can't be protected even though they appear to not be weak because of pawns on adjacent files, but those pawns can't safely advance far enough to defend the pawn...