Principal Variation Search vs. Transposition Table

[mvanthoor]

Hi

Because of the fact that the Principal Variation can be extracted from the Transposition Table if one wanted to, I was wondering about something. If you search the PV, ply by ply ("walking the PV"), you're actually searching hash table moves. So, if I collect a PV, and ALSO have a hash table, is it still necessary to do a principal variation search if I search the hash move first?

I may be misunderstanding this, but as I understand it now, it seems "walking the PV" (and thus, principal variation search?) seems pointless if you have a hash table. I've also seen references to "walking the PV is like having a poor man's TT", but I don't know where I read that quote. If true, it would seem to confirm my suspicion.

I could use a bit of assistance in determining if PVS is still helpful even if you have a TT.

[syzygy]

I may be misunderstanding this, but as I understand it now, it seems "walking the PV" (and thus, principal variation search?)

For me, PVS means zero-window searches of all non-first moves. This is very useful.

It is fine to use the search the TT move first. You will anyway not have the PV until after you have finished the PVS, so I am not really sure what else to do.

[mvanthoor]

I may be misunderstanding this, but as I understand it now, it seems "walking the PV" (and thus, principal variation search?)

For me, PVS means zero-window searches of all non-first moves. This is very useful.

It is fine to use the search the TT move first. You will anyway not have the PV until after you have finished the PVS, so I am not really sure what else to do.

I'm thinking to collect the PV by a somewhat modernized version of the triangular array method (vectors instead of arrays, because an array would need to be 256x256 elements in my case. My MAX_PLY is 255.) So I can have a PV without finding it in a hash table.

If I then search the hash move first, should I then STILL "walk the PV" ? (i.e.: can it be that the hash move is different than the PV move for that position and depth, and that the PV move turns out to be better than the hash move?)

[syzygy]

I'm thinking to collect the PV by a somewhat modernized version of the triangular array method (vectors instead of arrays, because an array would need to be 256x256 elements in my case. My MAX_PLY is 255.) So I can have a PV without finding it in a hash table.

I don't think you have the PV until you have finished the PVS

You have the PV from the previous iteration, but that PV can quickly become invalid, so "walking" the (previous) PV is of limited applicability. What you can do is insert the previous PV in the TT table before you start the next iteration to make sure that the TT table hasn't forgotten it (or you could give PV entries priority in your TT replacement strategy).

If I then search the hash move first, should I then STILL "walk the PV" ? (i.e.: can it be that the hash move is different than the PV move for that position and depth, and that the PV move turns out to be better than the hash move?)

You should only search the first move you pick with an open window and all the other moves with a zero window. Once a zero-window search fails high, you search that move with an open window.

I think your real question is: is the PV move (from the previous ply, as long as the PV hasn't been refuted in the next iteration) expected to be better than the TT move? This is difficult to answer. I expect that it will be very rare to have a TT move and a still-valid PV move from the previous iteration that differ.

[hgm]

Ideally the PV from the previous iteration should still be in your hash table. And if that is the case, walking the PV (which is not caled PVS, btw) is indeed useless. Depending on the size of your hash table and the quality of your replacement algorithm, the PV might have been overwritten, though. After all, the old PV is the first thing you follow during each iteration, and more often than not it stays the same. And after that you search the entire remaining tree. So the PV nodes can only survive if they are protected by depth, and even then the tail of the PV, which has low depth, will likely be lost.

One simple way to solve this, which doesn't complicate your search routine, is to stuff the previous PV back into the TT before each iteration.

In Fairy-Max I collect the PV in a 1-d array of moves, organized as a stack. Each depth has its own tentative PV on there, (terminated by some invalid move code, say 0), and when you go to the next depth you initialize its own (initially empty) PV on the top of that stack. On return the PV of the level from which you return is left on the stack. If the move scored in window, you then make that the first move of the new PV at that level, and copy the PV of the daughter behind it. And put the PV stack pointer just beyond the end of that.

[mvanthoor]

Syzygy and HGM: Thanks for the explanation. This stuff is somewhat difficult to visualize, but when I get to actually implementing it, I think it will become clear. That was the case with all the other concepts I encountered while writing my engine, so i assume it will be so now.

[elcabesa]

Principal Variation Search (PVS) is about searching the first move, and then prove that all the other possible move are worst than the first.

That said the PV from the previous iteration is mainly extracted to be shown on the GUI.

For PVS you can use the PV from the previous iteration or the move from transposition table and it will give you more or less the same strenght.

a small remark, even with an infinite size transiposition table, PV saved from previous iteration and extracted from the trasposition table are not always the same.

let's suppose that the PV contains a repetition
1) e4 Nf6 2) Nf3 Ng8 3) Ng1 Nf6 4) d4 e5 ....
the Pv extracted from transposition table can be eiter
1) e4 Nf6 2) Nf3 Ng8 3) Ng1 Nf6 4) Nf3 Ng8 5) Ng1 Nf6 6) Nf3 Ng8... or
1) e4 Nf6 2) d4 e5 ....
because for repeated position, only one move can be stored in Transposition table

[syzygy]

let's suppose that the PV contains a repetition
1) e4 Nf6 2) Nf3 Ng8 3) Ng1 Nf6 4) d4 e5 ....
the Pv extracted from transposition table can be eiter
1) e4 Nf6 2) Nf3 Ng8 3) Ng1 Nf6 4) Nf3 Ng8 5) Ng1 Nf6 6) Nf3 Ng8... or
1) e4 Nf6 2) d4 e5 ....
because for repeated position, only one move can be stored in Transposition table

But the first repetition within the PV can be evaluated as a draw. If the second time you get at the repeated position some other move is really better, then that move should have been on top the first time you got there and the position should not have repeated in the first place.

[OliverBr]

Because of the fact that the Principal Variation can be extracted from the Transposition Table if one wanted to,

Only if you store the PV into the TT.
Is it common sense that it's a good idea? Doesn't it look like the PV is consuming a lot of memory which is better used in having more hash slots?

[maksimKorzh]

Hi

Because of the fact that the Principal Variation can be extracted from the Transposition Table if one wanted to, I was wondering about something. If you search the PV, ply by ply ("walking the PV"), you're actually searching hash table moves. So, if I collect a PV, and ALSO have a hash table, is it still necessary to do a principal variation search if I search the hash move first?

I may be misunderstanding this, but as I understand it now, it seems "walking the PV" (and thus, principal variation search?) seems pointless if you have a hash table. I've also seen references to "walking the PV is like having a poor man's TT", but I don't know where I read that quote. If true, it would seem to confirm my suspicion.

I could use a bit of assistance in determining if PVS is still helpful even if you have a TT.

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)