PV can be shorter than max depth searched

[AndrewShort]

In examining the PV returned by an iteration of a search, I notice that sometmes the PV is not as long as the depth of the search. For example, suppose the search iteration is searching to depth 25. When done, the PV might only show 17 moves, instead of 25.

My interpretation of this is that if you reach a node that has a usable exact score in the hash table, and that score happens to survive all the way back to the root without getting replaced by something else, then your PV will necessarily be shorter than the depth searched.

So, in the above example, some branches may have reached 25 deep during the search, but at some point, on ply 17, it found a usable exact score that survived back to the root without getting replaced.

Assuming my interpretation is correct, this means in some cases, the engine might announce mate in 10, for example, but it would only be able to show you the first 5 moves of that mating line, since the last 5 moves are lost in hash la-la land...

Correct?

[sje]

Yes, an exact score transposition table hit along the PV, just like a tablebase hit along the PV, will truncate the PV.

[Harald]

The extreme case is one move in the PV and the rest in the hash table.
If everything else is ok than this should be no problem and not effect
the quality of the best move.

If you want to show the rest of the moves and the whole variant in some
output window or log file then you can try to get the missing moves from
the hash table.
for ( pv ) { show_move(); make_move(); }
while ( hash_found ) { show_move(); make_move(); }
undo_all_moves();

Some people do not use the PV array at all and totally rely on the hash table,
perhaps with some extra code to make sure the most important moves
are always in the table.

Harald

[bob]

In examining the PV returned by an iteration of a search, I notice that sometmes the PV is not as long as the depth of the search. For example, suppose the search iteration is searching to depth 25. When done, the PV might only show 17 moves, instead of 25.

My interpretation of this is that if you reach a node that has a usable exact score in the hash table, and that score happens to survive all the way back to the root without getting replaced by something else, then your PV will necessarily be shorter than the depth searched.

So, in the above example, some branches may have reached 25 deep during the search, but at some point, on ply 17, it found a usable exact score that survived back to the root without getting replaced.

Assuming my interpretation is correct, this means in some cases, the engine might announce mate in 10, for example, but it would only be able to show you the first 5 moves of that mating line, since the last 5 moves are lost in hash la-la land...

Correct?

yep.

[hgm]

This problem would disappear if you do not allow hash cutoffs in PV nodes, as some engines do.

[CThinker]

Aside from the reasons that have already been mentioned, here is one more...

In some engines (Amy, for example), there are no PV arrays.

When its time to display the PV, it simply iterates through the hash table. If an entry gets overwritten due to hash collision, you simply get a shorter PV display.

These types of collisions that trash the hash table are common. So much so, that in some engines, the hash table is re-populated from the PV array at the end of the search. This guarantees that the hash table is current.

[Dann Corbit]

Fruit keeps an array to prevent this from happening.

Most engines will get truncated pvs if they are the sort that reconstruct the pv from the hash table.

[bob]

Fruit keeps an array to prevent this from happening.

Most engines will get truncated pvs if they are the sort that reconstruct the pv from the hash table.

There is no way to prevent it from happening. I have _always_ used an array to back up the PV, but what do you back up when the PV ends on an EXACT hash hit? All you have is the PV up to that point, we don't store the PV in a hash entry so we can see the rest of it on a hit, it would greatly reduce the number of hash entries we could store.

There is no solution here except to not allow EXACT hash hits. The penalty is not enormous, but it is also not zero, so I'm not willing to give up the extra performance just to get a full PV in every case.

[AndrewShort]

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.

[Guetti]

Why just not do Hash tables cut in PV nodes? You can still use the hash table move (if present) for moves sorting in PV nodes. i.e. Glaurung and Fruit do it this way, and I don't think they would gain much playing strength if they would not cut in PV nodes. I also do it this way, but my engine is so dumb it doesn't matter any way if I would lose 5 Elo because of this.