Hashing the PV

[sluijten]

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?

[hgm]

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.)

[Edmund]

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.)

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.

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

[hgm]

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.

[bob]

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.

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...

[bob]

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?

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.

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.

[sluijten]

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?

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.

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.

How many table entries do you normally use without getting too many collisions?

[bob]

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?

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.

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.

How many table entries do you normally use without getting too many collisions?

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...

I don't have a good estimate for a reasonable size...

[sluijten]

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...