I tried to search the forum on the topic, but get many hits on lost PV's after implementing hashtables. I have read somewhere (Bob Hyatt?) that there is a way (or idea) to hash a complete PV and store it in the hash table? (thinking about it - one way could be to use the move indices, as generated by the move generator and then hash this PV-info somehow.)
How does this work? Has somebody tried it?
Hashing the PV
Moderators: hgm, Rebel, chrisw
-
- Posts: 27793
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Hashing the PV
Bob has implemented this idea through having a separate hash table (indexed by the same key as the main hash) for PV nodes to store their entire PV. I think he reserves something like 32 moves per entry. Because such a small fraction of all nodes are PV nodes, the table can be comparatively small despite the large entry size.
It would indeed be possible to compress the move to a single byte by using the move-gen index. You would have to keep that index around, though, even when sorting the move list, which might cause too much overhead. (Because you would have to do it always; each node can later turn out to become a PV node!)
My original idea was to use a 1-byte move encoding (and then reserve two entries in the main hash table for every PV node, in stead of one, so the second can contain 16 PV moves). The encoding I had in mind would encode piece number plus step vector into a single byte, so that it could be decoded easily through a small table. (E.g. each Pawn would consume 4 neighboring code points, each King and Knight 8 code points, Bishops and Rooks 16 code points, and a Queen 32 code points.)
It would indeed be possible to compress the move to a single byte by using the move-gen index. You would have to keep that index around, though, even when sorting the move list, which might cause too much overhead. (Because you would have to do it always; each node can later turn out to become a PV node!)
My original idea was to use a 1-byte move encoding (and then reserve two entries in the main hash table for every PV node, in stead of one, so the second can contain 16 PV moves). The encoding I had in mind would encode piece number plus step vector into a single byte, so that it could be decoded easily through a small table. (E.g. each Pawn would consume 4 neighboring code points, each King and Knight 8 code points, Bishops and Rooks 16 code points, and a Queen 32 code points.)
-
- Posts: 670
- Joined: Mon Dec 03, 2007 3:01 pm
- Location: Barcelona, Spain
Re: Hashing the PV
The Chessbase Databaseformat uses this type of encoding. However you have to make sure, the engine doesn't break, should you suddenly have 2 queens on the board. As a sidenote, 14 code points for bishops and rooks or 28 for queens is enough.hgm wrote:The encoding I had in mind would encode piece number plus step vector into a single byte, so that it could be decoded easily through a small table. (E.g. each Pawn would consume 4 neighboring code points, each King and Knight 8 code points, Bishops and Rooks 16 code points, and a Queen 32 code points.)
Why not just recompute the order at which a certain move was generated. The overhead of one additional movegen at PV-nodes is minimal.
regards
Edmund
-
- Posts: 27793
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Hashing the PV
I kept it at powers of 2 to make it easy to also decode the moves by bit manipulation, in applications where even a 256-byte table would be unacceptably large. Besides, in Capablanca Chess a Rook really can have 16 different moves.
The largest problem with the scheme is that the piece numbers in the piece list are not guaranteed to be the same, when the position is reached through a different path. So you would really have to identify the piece by its location relative to other pieces of the same type.
The largest problem with the scheme is that the piece numbers in the piece list are not guaranteed to be the same, when the position is reached through a different path. So you would really have to identify the piece by its location relative to other pieces of the same type.
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Hashing the PV
I don't use piece lists, so I could give this a try, for fun. No one has, to date, created a position with over 256 moves (I think the record is 208 or some such number). A special move generator that produces all moves and then returns the index to the move desired would work. Might try this just for fun, however...hgm wrote:I kept it at powers of 2 to make it easy to also decode the moves by bit manipulation, in applications where even a 256-byte table would be unacceptably large. Besides, in Capablanca Chess a Rook really can have 16 different moves.
The largest problem with the scheme is that the piece numbers in the piece list are not guaranteed to be the same, when the position is reached through a different path. So you would really have to identify the piece by its location relative to other pieces of the same type.
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Hashing the PV
I created a separate hash table, that contains 64 moves per entry. When I store an EXACT entry, I store the PV from below that entry (all mvoes out to the terminal position) in the PV hash table. When I do a probe and get an EXACT entry, I take that PV and graft it on to the current PV, so that I now have the terminal score, and the path to take me to that position.sluijten wrote:I tried to search the forum on the topic, but get many hits on lost PV's after implementing hashtables. I have read somewhere (Bob Hyatt?) that there is a way (or idea) to hash a complete PV and store it in the hash table? (thinking about it - one way could be to use the move indices, as generated by the move generator and then hash this PV-info somehow.)
How does this work? Has somebody tried it?
It happens so infrequently it adds no overhead I could measure, and stops almost all of those truncated PV problems. It can't stop them all, because collisions will occur in that table as well, but they are rare.
-
- Posts: 44
- Joined: Wed Apr 13, 2011 12:43 pm
Re: Hashing the PV
How many table entries do you normally use without getting too many collisions?bob wrote:I created a separate hash table, that contains 64 moves per entry. When I store an EXACT entry, I store the PV from below that entry (all mvoes out to the terminal position) in the PV hash table. When I do a probe and get an EXACT entry, I take that PV and graft it on to the current PV, so that I now have the terminal score, and the path to take me to that position.sluijten wrote:I tried to search the forum on the topic, but get many hits on lost PV's after implementing hashtables. I have read somewhere (Bob Hyatt?) that there is a way (or idea) to hash a complete PV and store it in the hash table? (thinking about it - one way could be to use the move indices, as generated by the move generator and then hash this PV-info somehow.)
How does this work? Has somebody tried it?
It happens so infrequently it adds no overhead I could measure, and stops almost all of those truncated PV problems. It can't stop them all, because collisions will occur in that table as well, but they are rare.
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Hashing the PV
I have not tested that very well at all. I typically run on a machine with 12gigs of RAM, and since Crafty requires a power of 2 for hash, the most I can use is 8 gigs. That leaves almost 4 gigs and I typically run with 1 gig for that table to really almost eliminate the short PV problem...sluijten wrote:How many table entries do you normally use without getting too many collisions?bob wrote:I created a separate hash table, that contains 64 moves per entry. When I store an EXACT entry, I store the PV from below that entry (all mvoes out to the terminal position) in the PV hash table. When I do a probe and get an EXACT entry, I take that PV and graft it on to the current PV, so that I now have the terminal score, and the path to take me to that position.sluijten wrote:I tried to search the forum on the topic, but get many hits on lost PV's after implementing hashtables. I have read somewhere (Bob Hyatt?) that there is a way (or idea) to hash a complete PV and store it in the hash table? (thinking about it - one way could be to use the move indices, as generated by the move generator and then hash this PV-info somehow.)
How does this work? Has somebody tried it?
It happens so infrequently it adds no overhead I could measure, and stops almost all of those truncated PV problems. It can't stop them all, because collisions will occur in that table as well, but they are rare.
I don't have a good estimate for a reasonable size...
-
- Posts: 44
- Joined: Wed Apr 13, 2011 12:43 pm
Re: Hashing the PV
Using 7 bits to store a PV move (using the index as returned by the 'PV move generator'), and 128 bits for a single hash table entry, there's room for a 18-ply PV, seems worth trying sometime...