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.bob wrote:I probably didn't write it very clearly, I agree. I will go back to look and see.hgm wrote: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.
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...
Full Principal Variation Retrieval
Moderators: hgm, Rebel, chrisw
-
- Posts: 778
- Joined: Sat Jul 01, 2006 7:11 am
Re: Full Principal Variation Retrieval
-
- Posts: 12540
- Joined: Wed Mar 08, 2006 8:57 pm
- Location: Redmond, WA USA
Re: Full Principal Variation Retrieval
Correspondence chess players will often analyze for more than 24 hours.jwes wrote: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.bob wrote:I probably didn't write it very clearly, I agree. I will go back to look and see.hgm wrote: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.
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...
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.
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Full Principal Variation Retrieval
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.Dann Corbit wrote:Correspondence chess players will often analyze for more than 24 hours.jwes wrote: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.bob wrote:I probably didn't write it very clearly, I agree. I will go back to look and see.hgm wrote: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.
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...
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.
-
- Posts: 27795
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Full Principal Variation Retrieval
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!
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Full Principal Variation Retrieval
hgm wrote: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".
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Full Principal Variation Retrieval
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.bob wrote:hgm wrote: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".
-
- Posts: 27795
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Full Principal Variation Retrieval
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.
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.
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Full Principal Variation Retrieval
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...hgm wrote: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.
-
- Posts: 778
- Joined: Sat Jul 01, 2006 7:11 am
Re: Full Principal Variation Retrieval
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 wrote: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.bob wrote:hgm wrote: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".
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Full Principal Variation Retrieval
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).jwes wrote: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 wrote: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.bob wrote:hgm wrote: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".