Hashing the PV

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
sluijten
Posts: 44
Joined: Wed Apr 13, 2011 10:43 am
Contact:

Hashing the PV

Post by sluijten » Mon Jun 06, 2011 10:47 am

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?

User avatar
hgm
Posts: 23772
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Hashing the PV

Post by hgm » Mon Jun 06, 2011 12:37 pm

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
Posts: 668
Joined: Mon Dec 03, 2007 2:01 pm
Location: Barcelona, Spain
Contact:

Re: Hashing the PV

Post by Edmund » Mon Jun 06, 2011 1:20 pm

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

User avatar
hgm
Posts: 23772
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Hashing the PV

Post by hgm » Mon Jun 06, 2011 1:37 pm

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
Posts: 20639
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Hashing the PV

Post by bob » Mon Jun 06, 2011 5:37 pm

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.
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
Posts: 20639
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Hashing the PV

Post by bob » Mon Jun 06, 2011 5:39 pm

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?
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
Posts: 44
Joined: Wed Apr 13, 2011 10:43 am
Contact:

Re: Hashing the PV

Post by sluijten » Mon Jun 13, 2011 12:30 pm

bob wrote:
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?
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
Posts: 20639
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Hashing the PV

Post by bob » Mon Jun 13, 2011 8:35 pm

sluijten wrote:
bob wrote:
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?
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
Posts: 44
Joined: Wed Apr 13, 2011 10:43 am
Contact:

Re: Hashing the PV

Post by sluijten » Mon Jun 27, 2011 7:25 am

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

Post Reply