Principal Variation Search vs. Transposition Table

[mvanthoor]

Hi Marcel, even though you've got perfect answers already, still I want to share my experience - just like you I was thinking that principal variation search (PVS) is something to collect principal variation (PV) but... it's not... For some reason what is known as PVS (Principal Variation Search) is a technique intended to optimize the search performance via narrowing alpha-beta window, see this link for details: https://web.archive.org/web/20071030220 ... ng/pvs.htm

What you ask is: "why to collect PV if we already have it in transposition table" - it's completely different question. If you have transposition table you can extract PV from there, but principal variation search is not intended to collect principal variation despite it's name, it's just a name for a search performance optimization technique.

Btw for clarity and didactic purposes despite having TT still I'm using a separate (modular) PV collection technique known as triangular PV - I've grabbed the implementation from TSCP)

Thanks for your insights. I know PV collection is not the same as PVS. I was just wondering if doing a PVS is still necessary if you have a transposition table. As in: you search the hash move first, then the PV move... but what if the hash move IS the PV move? Then you search a move twice.

I'm thinking on how to implement PV collection in my engine. I don't like the triangular array method because MAX_DEPTH is 255 in my engine (and I may set it to the max size of a 4 bit int some day). I don't want to create a 256 x 256 * 8 bytes = 512 KB array on the stack just for PV collection. But vectors in the move loop are way too slow, as I need to create a new one at each iteration... Maybe I'll just create a stack of vectors outside the A/B-function and refer to it, just as I did with my move list when I did my first implementation.

[maksimKorzh]

Hi Marcel, even though you've got perfect answers already, still I want to share my experience - just like you I was thinking that principal variation search (PVS) is something to collect principal variation (PV) but... it's not... For some reason what is known as PVS (Principal Variation Search) is a technique intended to optimize the search performance via narrowing alpha-beta window, see this link for details: https://web.archive.org/web/20071030220 ... ng/pvs.htm

What you ask is: "why to collect PV if we already have it in transposition table" - it's completely different question. If you have transposition table you can extract PV from there, but principal variation search is not intended to collect principal variation despite it's name, it's just a name for a search performance optimization technique.

Btw for clarity and didactic purposes despite having TT still I'm using a separate (modular) PV collection technique known as triangular PV - I've grabbed the implementation from TSCP)

Thanks for your insights. I know PV collection is not the same as PVS. I was just wondering if doing a PVS is still necessary if you have a transposition table. As in: you search the hash move first, then the PV move... but what if the hash move IS the PV move? Then you search a move twice.

I'm thinking on how to implement PV collection in my engine. I don't like the triangular array method because MAX_DEPTH is 255 in my engine (and I may set it to the max size of a 4 bit int some day). I don't want to create a 256 x 256 * 8 bytes = 512 KB array on the stack just for PV collection. But vectors in the move loop are way too slow, as I need to create a new one at each iteration... Maybe I'll just create a stack of vectors outside the A/B-function and refer to it, just as I did with my move list when I did my first implementation.

PV moves and HASH moves are not the same moves. When I have added hash move sorting it gave an incredible performance boost (thanks for Pedro Castro for telling me to do that!). PV move comes from the previous iteration of iterative deepening, say at depth 3 we found move d2ď4 then at depth 4 we sort move d2d4 to search it first. But when we start search at say depth for and made move ď2d4 then how about the response? There is no move yet but the hash table could already save it and then we order the hash move.

I don't know if one should do PVS when have a TT but I can say that PVS slightly improves the performance in BBC

[hgm]

It is NOT called PVS. If you want non-confused replies, don't sow confusion by usinng wrong terminology.

[syzygy]

Thanks for your insights. I know PV collection is not the same as PVS. I was just wondering if doing a PVS is still necessary if you have a transposition table. As in: you search the hash move first, then the PV move... but what if the hash move IS the PV move? Then you search a move twice.

Again: you CANNOT search the PV move first because you don't know it yet! PVS is about CONSTRUCTING the PV. If you knew the PV move, you wouldn't need to search anymore.

If you want to construct the PV, it makes sense to search the TT move first. Or you can search a move from the PV returned by the previous iteration, but that is only possible if nothing in the PV has changed. Most likely, your PV will change (that's the point of searching deeper).

Obviously you should not search the same move twice.

Just go in this order:
1. Implement a TT.
2. Adjust your move ordering such that the TT move is always searched first, when a TT move is available.
3. Implement PVS.

Because of (2), your PVS will search the TT move first in PV nodes.

The biggest Elo boost will come from (2). And without (1) and (2), (3) will probably just lose Elo.

[mvanthoor]

So do I understand it correctly that if you have a triangular array (or in my case, a recursive vector) for constructing the PV, you don't actually need a principal variation search because you have the PV already?

As in: PVS is the way to construct the PV from the hash table? If so, that wasn't my intention. I don't really like that method. BlueFever uses a hash table to store the PV in VICE, but he has to do legality checking and other antics to get the correct PV from the hash table. In my case, I just use the best move and append the PV from the best child node... basically exactly the same as a triangular array.

[syzygy]

So do I understand it correctly that if you have a triangular array (or in my case, a recursive vector) for constructing the PV, you don't actually need a principal variation search because you have the PV already?

No. The triangular array is hardly important as it is just a way of remembering the moves that you want to display to the user. This is just cosmetics.

PVS search builds up the PV by searching what it hopes to be the best move first and then checking that all other moves are worse. It does this in the root node and in every "PV node".

PVS is a search algorithm (a particular variation of alpha-beta). It decides how the search tree is searched. Namely by searching the first move with an open window and all other moves with a zero window. The zero window searches are the cheapest way of verifying that the other moves are not better than the first move. (If it fails, researches are needed.)

The triangular array has zero influence on how the search tree is searched. It is just a way to keep track of the PV that was constructed by PVS so that the PV constructed by PVS can be displayed to the user. It doesn't give any Elo. It cannot replace a TT or PVS.

[Karlo Bala]

Again: you CANNOT search the PV move first because you don't know it yet! PVS is about CONSTRUCTING the PV. If you knew the PV move, you wouldn't need to search anymore.

If you want to construct the PV, it makes sense to search the TT move first. Or you can search a move from the PV returned by the previous iteration, but that is only possible if nothing in the PV has changed. Most likely, your PV will change (that's the point of searching deeper).

Obviously you should not search the same move twice.

Just go in this order:
1. Implement a TT.
2. Adjust your move ordering such that the TT move is always searched first, when a TT move is available.
3. Implement PVS.

Because of (2), your PVS will search the TT move first in PV nodes.

The biggest Elo boost will come from (2). And without (1) and (2), (3) will probably just lose Elo.

I'm not sure that I agree with you completely.

PV move from the previous iteration is the best guess at the PV node, and most of the time it is the same as TT move except when TT move (PV node) is overwritten (in the ideal implementation of TT, every PV move is in the TT). So, PV move from the previous iteration should be searched first. Once PV move fails at some depth, PV moves are not useful down the tree (we are not following PV anymore) and the next best guess should be a TT move.

Basically, the first best line at the N-depth search should be the PV line from (N-1)-depth search plus the best move from the last ply.

[hgm]

There is a huge confusion here, because people refer to first 'following the PV' as 'PVS', which actually means something entirely different. And it was also not made clear that when they want to follow 'the PV', they mean the PV of the previous iteration.

And indeed, ideally the PV of the previous search would still be in the TT, so that searching hash move first is automatically following the previous PV as the first branch in the new iteration. In practice the TT might not be large enough to hold the entire tree, and since the PV was the branch you followed first (if it has not changed), it has the highest chance of being overwritten. In that case the only way to survive is when the replacement algorithm offers some special protection to the PV nodes. E.g. because these had high depth (which for the nodes close to the root will of course be the case), or because they have exact score. (It might be a good idea to treat nodes with exact score as if they had double the actual depth.)

Still, the low-depth nodes near the end of the PV will have little protection, and can easily be lost from the TT. Then you won't have hash moves there, and searching that part might be not as efficient as when you would have had those. But we are talking about a miniscule part of the tree then, so most people don't care. Or at least not enough to complicate their search routine with extra code to also follow the old PV in case there is no hash move.

What some engines would do is stuff the old PV from the tri-angular array back into the TT after the search, so that you know for sure it will be there to the very end.

[mvanthoor]

PVS is a search algorithm (a particular variation of alpha-beta). It decides how the search tree is searched....

Ah; that makes the difference. It's a way of searching the tree; I was thinking it was a way of searching for the PV only, with no effect on search.

The triangular array has zero influence on how the search tree is searched. It is just a way to keep track of the PV that was constructed by PVS so that the PV constructed by PVS can be displayed to the user. It doesn't give any Elo. It cannot replace a TT or PVS.

True. I've implemented a PV-collection, and it doesn't do anything in the search but collect the PV. That can't actually make the search faster. (But if I save the PV of each ply, I could try each of the previous ply's PV moves earlier in the next depth if they are available... that'd be the "poor man's TT" to which HGM once referred, and that is thus what 'following the PV' means: the one from the previous iteration, as HGM says above.)

I understand now. Thanks It'll probably become completely clear when I reach the point of implementing this. (Like it was with all the other things.)

When I'm going to write that tutorial, I'll have to rebuild the engine piece by piece (per chapter) anyway, so I'll encounter all of these things at least twice

[syzygy]

Basically, the first best line at the N-depth search should be the PV line from (N-1)-depth search plus the best move from the last ply.

I agree, but once one of the verification search fails, the open-window research of that move will not be able to search a PV line from the previous iteration because it doesn't exist. So your PV search routine must anyway look in the TT table. And the same holds true for the zero-window searches because move selection is always important (unless you know so much that you didn't need to search in the first place).

Since the PV moves from the previous iteration form the very first line explored by the next iteration, reinserting the PV from the previous iteration into the TT before starting the next iteration is the perfect solution. Otherwise your search needs to have special code for "PV move selection" that will just be a massive source of bugs (in particular if PVS is still poorly understood in the first place).

So I would still very much recommend to implement a TT first.