I was running my program on a couple test positions earlier, and I came across a problem where the PV would be shorter than the max search depth. I am now pretty sure this is due to null move reductions (instead of pruning immediately I instead decrease the search depth by one ply and re-search to avoid problems with zugzwang). Is this actually a problem for the search or should I just leave it? If it is a problem, what should I do?
2 Answers
Short principal variations are common if you retrieve the PV from the transposition table. They occur because a position that makes up part of the PV was overwritten in a collision.
If you want access to the full PV, you need to maintain it separately from the transposition table. However, this can get tricky when you cut a search short due to a table hit because you would only have the PV up until that point. To handle this, you can save the searched line of each PV-node (i.e. a node with an exact score) in a separate table alongside your transposition table. Saving that information will obviously cost you memory, but as PV-nodes are relatively uncommon, it isn't actually that expensive.
In my chess engine (being written in C#), I maintain the PV in a triangular PV-table. When I save a PV-node, I save the list of moves that were searched after that PV-node into a Dictionary, using the position's Zobrist hash as the key. Later, when retrieving the node from the transposition table, if the node is a PV-node, I retrieve the PV for that position from the Dictionary and overwrite the relevant portion of the triangular-PV-table.
This is a technique that I implemented after reading a paper that Robert Hyatt had published about ten years ago: A solution to short PVs caused by exact hash matches (2014).
One thing to note is that this is not a common technique, and that is likely for good reason. This work takes resources that could be dedicated to the search. If your goal is to build the best possible chess-playing engine, you should be fine with truncated PV's as long as you have access to the singular best move from the current position. However, if your goal is to learn and understand your engine better, having access to the full PV is nice as it allows you to see the final position that the score was calculated from.
I would say this is most problematic if you are on a low depth or have no qsearch (because of the odd-even effect). My guess is that you should probably do a complete re-search if the second reduced search is greater than alpha since getting a new PV is pretty rare in general.