Collecting Principal variation

[bob]

Using PVS, once a value between alpha and beta is returned the rest of the tree is searched with a zero window unless and until it is proved there is a better score. I believe this means the PV will always be the last move at each ply with a score between alpha and beta.

Problem is there are LOTS of times where something trips the PVS window and requires a re-search. But that entire path never becomes a new PV. There really isn't a short cut to having a PV per ply.

[Sven]

Using PVS, once a value between alpha and beta is returned the rest of the tree is searched with a zero window unless and until it is proved there is a better score. I believe this means the PV will always be the last move at each ply with a score between alpha and beta.

Problem is there are LOTS of times where something trips the PVS window and requires a re-search. But that entire path never becomes a new PV. There really isn't a short cut to having a PV per ply.

Yes. Furthermore, a PV is also not just one move but a sequence of moves. This already implies that two dimensions are required, regardless which search algorithm is used.

[Daniel Shawul]

Using PVS, once a value between alpha and beta is returned the rest of the tree is searched with a zero window unless and until it is proved there is a better score. I believe this means the PV will always be the last move at each ply with a score between alpha and beta.

Problem is there are LOTS of times where something trips the PVS window and requires a re-search. But that entire path never becomes a new PV. There really isn't a short cut to having a PV per ply.

Yes. Furthermore, a PV is also not just one move but a sequence of moves. This already implies that two dimensions are required, regardless which search algorithm is used.

I thought you guys understood that negascout requires just pv[MAX_PLY] as the OP stated, when we had this discussion some years ago http://talkchess.com/forum/viewtopic.ph ... triangular. The only thing problematic were search instabilties as HG pointed out. Try the tscp-negascout program i provided with both the pv[MAX_PLY] and pv[MAX_PLY][MAX_PLY] approach, and you will see both gives the same result.

[bob]

Using PVS, once a value between alpha and beta is returned the rest of the tree is searched with a zero window unless and until it is proved there is a better score. I believe this means the PV will always be the last move at each ply with a score between alpha and beta.

Problem is there are LOTS of times where something trips the PVS window and requires a re-search. But that entire path never becomes a new PV. There really isn't a short cut to having a PV per ply.

Yes. Furthermore, a PV is also not just one move but a sequence of moves. This already implies that two dimensions are required, regardless which search algorithm is used.

I thought you guys understood that negascout requires just pv[MAX_PLY] as the OP stated, when we had this discussion some years ago http://talkchess.com/forum/viewtopic.ph ... triangular. The only thing problematic were search instabilties as HG pointed out. Try the tscp-negascout program i provided with both the pv[MAX_PLY] and pv[MAX_PLY][MAX_PLY] approach, and you will see both gives the same result.

Is PV[max_ply] a LOCAL array? If not, how is it going to work?

You get a PV for the first move at ply=1. You CAN get a PVS fail high on another root move at ply=n, then a re-search produces a good score, but as you back up, you find a move that refutes that and the PV never changes at the root. If you change the PV down in the tree,, and you only have one copy, how is it going to not get clobbered?

Your comment "I DO get a different PV from what pv[m][m] gives" says it all. The PV goes from the root move to the move that leads to the score being backed up. If you DON'T get that, it is not the "PV".

[jwes]

Using PVS, once a value between alpha and beta is returned the rest of the tree is searched with a zero window unless and until it is proved there is a better score. I believe this means the PV will always be the last move at each ply with a score between alpha and beta.

Problem is there are LOTS of times where something trips the PVS window and requires a re-search. But that entire path never becomes a new PV. There really isn't a short cut to having a PV per ply.

Doesn't this mean that we haven't found the PV yet? This path may not become the PV, but the previous path is also not the PV.

[kbhearn]

Using PVS, once a value between alpha and beta is returned the rest of the tree is searched with a zero window unless and until it is proved there is a better score. I believe this means the PV will always be the last move at each ply with a score between alpha and beta.

Problem is there are LOTS of times where something trips the PVS window and requires a re-search. But that entire path never becomes a new PV. There really isn't a short cut to having a PV per ply.

Yes. Furthermore, a PV is also not just one move but a sequence of moves. This already implies that two dimensions are required, regardless which search algorithm is used.

I thought you guys understood that negascout requires just pv[MAX_PLY] as the OP stated, when we had this discussion some years ago http://talkchess.com/forum/viewtopic.ph ... triangular. The only thing problematic were search instabilties as HG pointed out. Try the tscp-negascout program i provided with both the pv[MAX_PLY] and pv[MAX_PLY][MAX_PLY] approach, and you will see both gives the same result.

Is PV[max_ply] a LOCAL array? If not, how is it going to work?

You get a PV for the first move at ply=1. You CAN get a PVS fail high on another root move at ply=n, then a re-search produces a good score, but as you back up, you find a move that refutes that and the PV never changes at the root. If you change the PV down in the tree,, and you only have one copy, how is it going to not get clobbered?

Your comment "I DO get a different PV from what pv[m][m] gives" says it all. The PV goes from the root move to the move that leads to the score being backed up. If you DON'T get that, it is not the "PV".

If the search is 100% stable, then when a scout search fails high, it will 100% be the source of a new pv and it doesn't matter that you're clobbering the old one.

Of course that would require either no transposition table or a crippled one that will only accept exact depth matches, as well as no reduction/pruning decisions based off move ordering.

[Sven]

Using PVS, once a value between alpha and beta is returned the rest of the tree is searched with a zero window unless and until it is proved there is a better score. I believe this means the PV will always be the last move at each ply with a score between alpha and beta.

Problem is there are LOTS of times where something trips the PVS window and requires a re-search. But that entire path never becomes a new PV. There really isn't a short cut to having a PV per ply.

Yes. Furthermore, a PV is also not just one move but a sequence of moves. This already implies that two dimensions are required, regardless which search algorithm is used.

I thought you guys understood that negascout requires just pv[MAX_PLY] as the OP stated, when we had this discussion some years ago http://talkchess.com/forum/viewtopic.ph ... triangular. The only thing problematic were search instabilties as HG pointed out. Try the tscp-negascout program i provided with both the pv[MAX_PLY] and pv[MAX_PLY][MAX_PLY] approach, and you will see both gives the same result.

That discussion you link to did not have the result you make us believe today. It had the result that in a program as simple as TSCP (no TT, no search instability) it worked for you to replace the triangular PV approach by a linear approach, shown by you by playing few games. But in that same thread you also wrote:

Howver scorpio does get different pvs so there must be exceptions.

There was no agreement to your statement that a linear approach should be sufficient with negascout apart from agreeing that it seems to work in a modified TSCP. Also from a theoretical viewpoint Bob and myself disagreed to you, same as today. Therefore I see no point in asking why "we guys" did not understand that negascout would require a linear PV implementation only. There was no proof, nothing that we agreed upon.

It is obvious, and has also been explained at least by Bob back then, that a re-search of a move after failing high in a zero window can lead to a new *local* PV of the current node that has to replace the previous *local* PV. In this case you can definitely overwrite information that should not be overwritten, or get inconsistent PV results, if you do not keep one PV per ply.

[bob]

Using PVS, once a value between alpha and beta is returned the rest of the tree is searched with a zero window unless and until it is proved there is a better score. I believe this means the PV will always be the last move at each ply with a score between alpha and beta.

Problem is there are LOTS of times where something trips the PVS window and requires a re-search. But that entire path never becomes a new PV. There really isn't a short cut to having a PV per ply.

Yes. Furthermore, a PV is also not just one move but a sequence of moves. This already implies that two dimensions are required, regardless which search algorithm is used.

I thought you guys understood that negascout requires just pv[MAX_PLY] as the OP stated, when we had this discussion some years ago http://talkchess.com/forum/viewtopic.ph ... triangular. The only thing problematic were search instabilties as HG pointed out. Try the tscp-negascout program i provided with both the pv[MAX_PLY] and pv[MAX_PLY][MAX_PLY] approach, and you will see both gives the same result.

Is PV[max_ply] a LOCAL array? If not, how is it going to work?

You get a PV for the first move at ply=1. You CAN get a PVS fail high on another root move at ply=n, then a re-search produces a good score, but as you back up, you find a move that refutes that and the PV never changes at the root. If you change the PV down in the tree,, and you only have one copy, how is it going to not get clobbered?

Your comment "I DO get a different PV from what pv[m][m] gives" says it all. The PV goes from the root move to the move that leads to the score being backed up. If you DON'T get that, it is not the "PV".

If the search is 100% stable, then when a scout search fails high, it will 100% be the source of a new pv and it doesn't matter that you're clobbering the old one.

Of course that would require either no transposition table or a crippled one that will only accept exact depth matches, as well as no reduction/pruning decisions based off move ordering.

There is the old "if a frog had pockets, it would carry a gun and not worry about snakes.."

In real searches, most want a real PV, not some broken thing that doesn't take you to the endpoint that produced the score... The 2d array has no measurable overhead, is exact regardless of search instabilities, seems like a no-brainer to use it to me. I've used it happily for at least 45 years now. It seemed like a natural idea in 1968, still does today to me. And with the hash path idea I have explained, the PV is correct even more of the time.

[bob]

Using PVS, once a value between alpha and beta is returned the rest of the tree is searched with a zero window unless and until it is proved there is a better score. I believe this means the PV will always be the last move at each ply with a score between alpha and beta.

Problem is there are LOTS of times where something trips the PVS window and requires a re-search. But that entire path never becomes a new PV. There really isn't a short cut to having a PV per ply.

Doesn't this mean that we haven't found the PV yet? This path may not become the PV, but the previous path is also not the PV.

You don't know, however. That is the problem. The only way you really know you have a new pv is if it is backed up to the root along with the score it produced.

[Daniel Shawul]

Using PVS, once a value between alpha and beta is returned the rest of the tree is searched with a zero window unless and until it is proved there is a better score. I believe this means the PV will always be the last move at each ply with a score between alpha and beta.

Problem is there are LOTS of times where something trips the PVS window and requires a re-search. But that entire path never becomes a new PV. There really isn't a short cut to having a PV per ply.

Yes. Furthermore, a PV is also not just one move but a sequence of moves. This already implies that two dimensions are required, regardless which search algorithm is used.

I thought you guys understood that negascout requires just pv[MAX_PLY] as the OP stated, when we had this discussion some years ago http://talkchess.com/forum/viewtopic.ph ... triangular. The only thing problematic were search instabilties as HG pointed out. Try the tscp-negascout program i provided with both the pv[MAX_PLY] and pv[MAX_PLY][MAX_PLY] approach, and you will see both gives the same result.

That discussion you link to did not have the result you make us believe today. It had the result that in a program as simple as TSCP (no TT, no search instability) it worked for you to replace the triangular PV approach by a linear approach, shown by you by playing few games. But in that same thread you also wrote:

Howver scorpio does get different pvs so there must be exceptions.

There was no agreement to your statement that a linear approach should be sufficient with negascout apart from agreeing that it seems to work in a modified TSCP. Also from a theoretical viewpoint Bob and myself disagreed to you, same as today. Therefore I see no point in asking why "we guys" did not understand that negascout would require a linear PV implementation only. There was no proof, nothing that we agreed upon.

It is obvious, and has also been explained at least by Bob back then, that a re-search of a move after failing high in a zero window can lead to a new *local* PV of the current node that has to replace the previous *local* PV. In this case you can definitely overwrite information that should not be overwritten, or get inconsistent PV results, if you do not keep one PV per ply.

It is 2015 now Sven and still counting ... Break the tscp-negascout code if you can so that pv[N] and pv[N][N] give different results.
Well I just felt compelled to reply when I see a newbie being fed wrong information...