PV can be shorter than max depth searched

[bob]

I did some testing, and the results are not surprising:

Generating the PV normally (via search) often yields the full pv, but occasionally you get a truncated PV due to exact hash hits surviving to the root.

Generating the PV after the fact, by walking the hash table, is very tempting, because it's so easy to write and it's fast - it doesn't bog down search. However, it usually yields a shorter PV than the normal way (via search) because of hash overwrites. I am not willing to not overwrite exact hash entries.

Sometimes, the after-the-fact hash walkthough generates a PV *longer* than the normal way (if normal yielded a truncated pv), but this is rare. In that case, you are just getting lucky that the hash table still contains the nodes in question.

So walking the hash table seems inferior to me, particularly since the PV is fed into the next iteration of the search, to be sorted first. I suppose if before you try a new iteration you see the pv is truncated, you may as well walk the hash to see if you can get a fuller pv, as it's almost free, and only done in a specific case between iterations. A fuller pv would usually mean a better sorting of the next iteration.

There is another issue... the hash reconstruction approach can produce a bogus PV.

The thing I want for debugging is to be able to have the sequence of moves leading exactly to the terminal node that produced the score that was backed up to the root. If the PV comes from the hash, it will be wrong often enough to make this kind of debugging very difficult...

[AndrewShort]

I had suspected that, but I hadn't thought through it, as you obviously have. In my informal tests of hundreds of positions, I never encountered such a mismatch, but I can see how it's certainly possible, since a node can get replaced with a node with deeper depth searched, but the old node is the one in the pv, and it might have a different best move.

[bob]

I had suspected that, but I hadn't thought through it, as you obviously have. In my informal tests of hundreds of positions, I never encountered such a mismatch, but I can see how it's certainly possible, since a node can get replaced with a node with deeper depth searched, but the old node is the one in the pv, and it might have a different best move.

That's correct. I tried this idea several (and I do mean several) years ago. And I was aware that an occasional bogus move might happen due to a real hash collision. But it happened way too often that the PV displayed did not lead to a position that matched the score given. Further analysis showed several depth > N matches for various plies where depth should have been just "N". So I got "better" moves, but that didn't help in debugging at all.

[CThinker]

I had suspected that, but I hadn't thought through it, as you obviously have. In my informal tests of hundreds of positions, I never encountered such a mismatch, but I can see how it's certainly possible, since a node can get replaced with a node with deeper depth searched, but the old node is the one in the pv, and it might have a different best move.

My experience is something like this:

You have just finished searching with depth D. At this point, the hash entries represent a valid sequence of moves for the PV. Now, you search with depth D+1. At some ply, you start saving a move to the hash table, and this overwrites an entry in your current PV sequence. And now, you are out of time, and you have to quit searching.

After this, the PV that you can derive from the hash table is only up to the earliest entry that was overwritten. If that happens to be the first move, you don't even have a PV at all. Even worse, if you use UCI, the UI will have nothing to give to you to ponder on.

Keeping PV arrays, instead of just relying on the hash table, helps in preventing the situation I just described.