Full Principal Variation Retrieval

[jwes]

It might be what you did, but it was not what you WROTE...

I agree with your conclusion. But I still think you could have 'the best of both Worlds' when storing the PV of PV nodes in the hash table in the way I described.

I probably didn't write it very clearly, I agree. I will go back to look and see.

Yes, storing the PV for those non-fail nodes sounds like an idea. I might try a quick trick later to test that. My quick idea is to take the 64 bit signature, squash it to something relatively small (say 16 bits) and use that as an index into a PV-holder. Doesn't change the length of the hash entry at all, only question is how significant will the collision rate be? with 65536 entries, and not very many true PV nodes, it might work. I am going to add a statistical measurement in Crafty to see how many times I would actually store one of these PV entries and compute a nodes per store average to get an idea of potential collisions...

More on this later. Fortunately it is simple, or I wouldn't bother since the effect will be nil on strength, but nice for debugging and seeing the real PV...

I ran a quick experiment. I put in counters to see how many EXACT nodes were in the hash table. I ran 30 positions for 2 min each with 512m hash which on my machine is about 200m nodes per position. The largest number of exact nodes in the hash table at any time was 1619 which suggests that 16 bits could be enough.

[Dann Corbit]

It might be what you did, but it was not what you WROTE...

I agree with your conclusion. But I still think you could have 'the best of both Worlds' when storing the PV of PV nodes in the hash table in the way I described.

I probably didn't write it very clearly, I agree. I will go back to look and see.

Yes, storing the PV for those non-fail nodes sounds like an idea. I might try a quick trick later to test that. My quick idea is to take the 64 bit signature, squash it to something relatively small (say 16 bits) and use that as an index into a PV-holder. Doesn't change the length of the hash entry at all, only question is how significant will the collision rate be? with 65536 entries, and not very many true PV nodes, it might work. I am going to add a statistical measurement in Crafty to see how many times I would actually store one of these PV entries and compute a nodes per store average to get an idea of potential collisions...

More on this later. Fortunately it is simple, or I wouldn't bother since the effect will be nil on strength, but nice for debugging and seeing the real PV...

I ran a quick experiment. I put in counters to see how many EXACT nodes were in the hash table. I ran 30 positions for 2 min each with 512m hash which on my machine is about 200m nodes per position. The largest number of exact nodes in the hash table at any time was 1619 which suggests that 16 bits could be enough.

Correspondence chess players will often analyze for more than 24 hours.
What about a correspondence chess player with an 8CPU machine at 4 GHz per thread with 32 GB hash?

Computer speed is exponential due to hardware growth, so in 5 years, compute power will be 32 times higher, so your two minute search is like a one hour search today.

I think that game history should support up to 6000 plies. Nobody does that, of course.

On the other hand, I consider it completely safe to store the generated moves for any position in an array of 256 elements simply because carefully contrived artificial positions have never achieved more than 218 distinct move choices.

[bob]

It might be what you did, but it was not what you WROTE...

I agree with your conclusion. But I still think you could have 'the best of both Worlds' when storing the PV of PV nodes in the hash table in the way I described.

I probably didn't write it very clearly, I agree. I will go back to look and see.

Yes, storing the PV for those non-fail nodes sounds like an idea. I might try a quick trick later to test that. My quick idea is to take the 64 bit signature, squash it to something relatively small (say 16 bits) and use that as an index into a PV-holder. Doesn't change the length of the hash entry at all, only question is how significant will the collision rate be? with 65536 entries, and not very many true PV nodes, it might work. I am going to add a statistical measurement in Crafty to see how many times I would actually store one of these PV entries and compute a nodes per store average to get an idea of potential collisions...

More on this later. Fortunately it is simple, or I wouldn't bother since the effect will be nil on strength, but nice for debugging and seeing the real PV...

I ran a quick experiment. I put in counters to see how many EXACT nodes were in the hash table. I ran 30 positions for 2 min each with 512m hash which on my machine is about 200m nodes per position. The largest number of exact nodes in the hash table at any time was 1619 which suggests that 16 bits could be enough.

Correspondence chess players will often analyze for more than 24 hours.
What about a correspondence chess player with an 8CPU machine at 4 GHz per thread with 32 GB hash?

Computer speed is exponential due to hardware growth, so in 5 years, compute power will be 32 times higher, so your two minute search is like a one hour search today.

I think that game history should support up to 6000 plies. Nobody does that, of course.

On the other hand, I consider it completely safe to store the generated moves for any position in an array of 256 elements simply because carefully contrived artificial positions have never achieved more than 218 distinct move choices.

Actually, Crafty will play a game of 60,000 plies if you want. It won't search that deep on any single search, but it will play a game that lasts that long.

[hgm]

UCI engines would probably forfeit on time in such a game, due to the time it takes to send them the game (on every move) alone!

[bob]

UCI engines would probably forfeit on time in such a game, due to the time it takes to send them the game (on every move) alone!

ChessBase used to do that and told no one until Thorsten sent me a game he had played between Crafty and Fritz (I think) and he asked, "does this log file look normal?" It looked like hell. No ponder matches, even though I pondered like crazy. When I got a move, I first got stopped, the engine was told to reset (new) and then the entire game was shoved down my throat followed by a "go".

I'd call that more than "a minor inconvenience".

[bob]

UCI engines would probably forfeit on time in such a game, due to the time it takes to send them the game (on every move) alone!

ChessBase used to do that and told no one until Thorsten sent me a game he had played between Crafty and Fritz (I think) and he asked, "does this log file look normal?" It looked like hell. No ponder matches, even though I pondered like crazy. When I got a move, I first got stopped, the engine was told to reset (new) and then the entire game was shoved down my throat followed by a "go".

I'd call that more than "a minor inconvenience".

BTW I am testing the idea I mentioned. Except that I am using an array of size 4096 right now, and I am saving the signature when I save a PV, so that before I graft that PV on an EXACT hit, I can make sure it "belongs". A mis-match shows a collision and will indicate that a larger array is needed. Right now I am just doing an xor-fold to reduce 64 bits to 12. Got a small bug or two to work out, but it looks promising. More to follow shortly. Fine #70 (for Crafty) produces a few "short PVs" ending in <HT> This version ought to eliminate that completely.

[hgm]

If you are clearing the PV entries for which the corresponding hash entry is replaced, you could rehash collissions, (rather than simply overwrite), and get a much better filling fraction of the table. You would have the inconvenience that you would have to test on every replacement if the replaced entry is exact, while usually it isn't.

OTOH you will have to remove PV entries at some point, or the table will fill up during the game. You can clear it after every move, provided that the signatures you store with them contain enough information to find back the original hash entry, so you can see if it is still there.

[bob]

If you are clearing the PV entries for which the corresponding hash entry is replaced, you could rehash collissions, (rather than simply overwrite), and get a much better filling fraction of the table. You would have the inconvenience that you would have to test on every replacement if the replaced entry is exact, while usually it isn't.

OTOH you will have to remove PV entries at some point, or the table will fill up during the game. You can clear it after every move, provided that the signatures you store with them contain enough information to find back the original hash entry, so you can see if it is still there.

I have not got to the long-term issues. But I do have a signature to verify that the PV goes with the hash entry. And it will be easy enough to search at least a few entries to find an overwritable one. Perhaps using the normal age mechanism. So far it is looking reasonable, but I still have a couple of issues in trying to retain the <EGTB> flag and such...

[jwes]

UCI engines would probably forfeit on time in such a game, due to the time it takes to send them the game (on every move) alone!

ChessBase used to do that and told no one until Thorsten sent me a game he had played between Crafty and Fritz (I think) and he asked, "does this log file look normal?" It looked like hell. No ponder matches, even though I pondered like crazy. When I got a move, I first got stopped, the engine was told to reset (new) and then the entire game was shoved down my throat followed by a "go".

I'd call that more than "a minor inconvenience".

BTW I am testing the idea I mentioned. Except that I am using an array of size 4096 right now, and I am saving the signature when I save a PV, so that before I graft that PV on an EXACT hit, I can make sure it "belongs". A mis-match shows a collision and will indicate that a larger array is needed. Right now I am just doing an xor-fold to reduce 64 bits to 12. Got a small bug or two to work out, but it looks promising. More to follow shortly. Fine #70 (for Crafty) produces a few "short PVs" ending in <HT> This version ought to eliminate that completely.

It should be good enough just to and some bits from the hash key. That would also make it easier to configure it so people doing overnight analysis with giant hash tables can allocate more memory.

[bob]

UCI engines would probably forfeit on time in such a game, due to the time it takes to send them the game (on every move) alone!

ChessBase used to do that and told no one until Thorsten sent me a game he had played between Crafty and Fritz (I think) and he asked, "does this log file look normal?" It looked like hell. No ponder matches, even though I pondered like crazy. When I got a move, I first got stopped, the engine was told to reset (new) and then the entire game was shoved down my throat followed by a "go".

I'd call that more than "a minor inconvenience".

BTW I am testing the idea I mentioned. Except that I am using an array of size 4096 right now, and I am saving the signature when I save a PV, so that before I graft that PV on an EXACT hit, I can make sure it "belongs". A mis-match shows a collision and will indicate that a larger array is needed. Right now I am just doing an xor-fold to reduce 64 bits to 12. Got a small bug or two to work out, but it looks promising. More to follow shortly. Fine #70 (for Crafty) produces a few "short PVs" ending in <HT> This version ought to eliminate that completely.

It should be good enough just to and some bits from the hash key. That would also make it easier to configure it so people doing overnight analysis with giant hash tables can allocate more memory.

Not sure what you mean. I am currently using 16384 + 7 entries (+7 to allow for the 8-entry bucket size). I AND off the rightmost 14 bits of the normal hash signature to use for an index, then try that + up to 7 more... I suppose I could malloc() this, and that might be what I eventually end up doing. So far, with 16384, I have not seen any mismatches yet (EXACT hash hit, but no match on the path hash table).