Extracting PV from TT

[Gian-Carlo Pascutto]

The simplest way is to simply carry the pv as a list or array. There is not much overhead, even for a 100 ply search. I think that most people do it this way, since it is foolproof.

In my mind, explicitly storing the PV is a needless waste of time. The PV should be fully obtainable from the hashtable. If it's not, you've got a serious bug you need to fix. So I prefer to find those early by relying 100% on the hashtable to get the PV.

This is trivially _not_ a bug. On the last iteration, any move can involve a ton of searching, and can overwrite things, particularly the hash PV entries for shallow draft entries. I've never seen an implementation that did not have this problem...

See my answer above regarding evicting PV entries from the hashtable.

[Gian-Carlo Pascutto]

What about a case where the PV move at the root searches a tree of 500M nodes. And the _second_ move is almost good enough to become the best, but not quite? And it can easily search 500M nodes or _more_. And while deep draft entries are not usually lost, the ones near the tip can get overwritten in a heartbeat.

They can't. If they can in Crafty, then that's a bug you should fix. It's a bug you would have more easily found if you tried to get your PV from the hash, because you would have noticed moves are missing.

So basically, you've just perfectly illustrated my point: explicitly storing the PV is just hiding bugs and serves no useful purpose.

[bob]

What about a case where the PV move at the root searches a tree of 500M nodes. And the _second_ move is almost good enough to become the best, but not quite? And it can easily search 500M nodes or _more_. And while deep draft entries are not usually lost, the ones near the tip can get overwritten in a heartbeat.

They can't. If they can in Crafty, then that's a bug you should fix. It's a bug you would have more easily found if you tried to get your PV from the hash, because you would have noticed moves are missing.

So basically, you've just perfectly illustrated my point: explicitly storing the PV is just hiding bugs and serves no useful purpose.

This is nonsense and you are not thinking it thru. Here is a simple example that happened to me when I tried the PV from hash many years ago.

We search the PV and at a remaining depth of (say) 5, we store position P, which has the best move from this node, with a draft of 5. Now we search a different root move, that has a similar tree size (or even bigger if it is a check or whatever). We reach a position Q, which has a deeper draft because of the extra checks in this path, yet P and Q both map to the same hash entry. And P gets overwritten since Q has a greater draft. if you store two positions in a hash bucket, this has to happen 3 times in one search. Still can happen. I currently store 4 entries in a single bucket, so I need 5 entries to overwrite.

It can happen, and it isn't a bug. If you want to flag hash entries as PV, that is also a bad idea, because you reach a point where the PV changes somewhere, and all the old PV nodes need to be unflagged or you pollute the table with entries you can't replace.

Thanks to repetitions, you can even get a bogus move or two or N on the end of the PV as well...

[bob]

The simplest way is to simply carry the pv as a list or array. There is not much overhead, even for a 100 ply search. I think that most people do it this way, since it is foolproof.

In my mind, explicitly storing the PV is a needless waste of time. The PV should be fully obtainable from the hashtable. If it's not, you've got a serious bug you need to fix. So I prefer to find those early by relying 100% on the hashtable to get the PV.

This is trivially _not_ a bug. On the last iteration, any move can involve a ton of searching, and can overwrite things, particularly the hash PV entries for shallow draft entries. I've never seen an implementation that did not have this problem...

See my answer above regarding evicting PV entries from the hashtable.

How do you know an entry is a PV entry? And if you flag each one, how do you go back and remove the flag as the PV changes while searching the first move, or even as you search other root moves?

[Mincho Georgiev]

If it comes down to printing the PV, i dont see a problem to do whatever you want (retrieve it).
My personal opinion if we talk about move ordering is that the pv_move and tt_move should be delimited if they differ from each other.
I may misunderstood the general topic idea, but i didn't see if it's about collecting the pv for move ordering (or refute) or just collecting it for printing.

[Gian-Carlo Pascutto]

How do you know an entry is a PV entry? And if you flag each one, how do you go back and remove the flag as the PV changes while searching the first move, or even as you search other root moves?

Entries with exact scores are PV entries. The amount of them in a complete search is so minuscule that you shouldn't have to evict them from your hashtable. Obviously you don't replace them by bound entries with deeper drafts.

For a new search they are evicted due to aging.

[Gian-Carlo Pascutto]

If it comes down to printing the PV, i dont see a problem to do whatever you want (retrieve it).
My personal opinion if we talk about move ordering is that the pv_move and tt_move should be delimited if they differ from each other.
I may misunderstood the general topic idea, but i didn't see if it's about collecting the pv for move ordering (or refute) or just collecting it for printing.

Why would it matter? In what case can they differ anyway in PV nodes? A PV is by definition the sequence with the best moves.

[MattieShoes]

Depending on how you store moves, you can also potentially run into issues where the move is illegal -- say trading QR instead of KR results in the same position because the recapture is with the untraded rook.. Then your best move in hash could potentially be telling you to move a rook that's not on the chessboard, etc.

This makes very little sense to me. The hashkey would be different so it's impossible to get a hit.

It was possible with a version of my engine that stored the index of the piecelist instead of the from square for a move, but the hash key is based on piece/position. So it's possible to have two identical positions with different piecelists. So the best move referenced a piecelist index that was empty. It was a bad implementation on my part that I subsequently fixed, just mentioning it because it took me a while for the lightbulb to go on in my brain.

[Mincho Georgiev]

If it comes down to printing the PV, i dont see a problem to do whatever you want (retrieve it).
My personal opinion if we talk about move ordering is that the pv_move and tt_move should be delimited if they differ from each other.
I may misunderstood the general topic idea, but i didn't see if it's about collecting the pv for move ordering (or refute) or just collecting it for printing.

Why would it matter? In what case can they differ anyway in PV nodes? A PV is by definition the sequence with the best moves.

I didn't say anything about pv-nodes, all-nodes or cut-nodes.

[Jan Brouwer]

Entries with exact scores are PV entries. The amount of them in a complete search is so minuscule that you shouldn't have to evict them from your hashtable. Obviously you don't replace them by bound entries with deeper drafts.

What are typical values for the number of PV nodes in a search?
I checked my engine: about 0.01% to 0.1% (for searches of about 10M nodes).
This seems a little on the high side.