Collecting Principal variation

[vittyvirus]

I saw that Stockfish used something like the Bruce Moreland's technique to collect PV. In Yaka, I'm currently using this technique I found:
You actually maintain an array inside a Searcher class like this:

Code: Select all

Move pv[MAX_PLY];

Note that it is decleared in the searcher class, not the search function.
Now, inside the search function, if you find a best move:

Code: Select all

if (score > alpha) {
      alpha = score;
      pv[ply] = move_list[i];
}

Now when you need to display the PV, you can check the MoveList for the position contains this move:

Code: Select all

GameLine gl;
  Position temp_pos(pos);
  temp_pos.make_move(SearchTreeInfo[0].best_move, gl);
  for &#40;ply_t ply = 1; ply < depth; ++ply&#41; &#123;
    MoveList<LEGAL> move_list&#40;temp_pos&#41;;
    if &#40;move_list.contains&#40;pv&#91;ply&#93;.get&#40;))) &#123;
      temp_pos.make_move&#40;pv&#91;ply&#93;, gl&#41;;
      out << pv&#91;ply&#93;.to_str&#40;) << ' ';
    &#125; else break;
  &#125;

Best,
Syed Fahad

[jordanbray]

This algorithm didn't work for me. In other nodes, the score would fail high deep within the tree, but not within the PV. This caused the pv list to become corrupted.

I may have done it wrong, though.

[Sven]

Hi Syed,

you need to remember one full PV per tree level: current PV at root node (ply=0), current PV at ply=1 after the first move of the current variation, current PV at ply=2 and so on. Implementing it requires either the "triangular PV" approach or an approach that returns a PV as an out parameter from each subtree (or something similar). Both has almost the same semantics and differs only by implementation details. You will not succeed with an approach that stores only one PV (one-dimensional) for the whole search tree, doing so is incorrect in general.

To understand why, you can think about how you analyze a chess position. Note what you need to remember when having analyzed one move, obtained its PV, and then analyze a second move. You remember the whole PV of the first move but also the PV of the second move, only then you back up to the root again to decide whether the second move is better than the first, and if it is then you replace the old PV by the new PV. The PV of a node is the best move concatenated with the PV of the best move's successor node. This works recursively, therefore you need one PV per tree level.

[Sven]

Your algorithm above will destroy, for instance, the PV of the first root move while you are at some node in the subtree of the second root move, find a new best move for that node and overwrite PV[ply] with that best move. At that point you do not know yet whether the second root move will turn out to be better than the first (for which a PV has been found), and if later on you find that the second is not better then the first PV needs to stay unchanged.

[vittyvirus]

Your algorithm above will destroy, for instance, the PV of the first root move while you are at some node in the subtree of the second root move, find a new best move for that node and overwrite PV[ply] with that best move. At that point you do not know yet whether the second root move will turn out to be better than the first (for which a PV has been found), and if later on you find that the second is not better then the first PV needs to stay unchanged.

Well, that is a real problem. But that is why we check whether the move list for the pv array contains the moves. This method, thus doesn't always return the full length pv, but it works for my purpose:

Code: Select all

1 -0.01 400 3 133k e2e3 
2 0.83 3864 32 120k d2d4 e7e6 
3 -0.04 33537 173 193k b1c3 b8a6 d2d4 
4 1.2 221382 1526 145k e2e3 b8a6 d1h5 a8b8 

Note that my baby engine can't search too deep.

[Sven]

Your algorithm above will destroy, for instance, the PV of the first root move while you are at some node in the subtree of the second root move, find a new best move for that node and overwrite PV[ply] with that best move. At that point you do not know yet whether the second root move will turn out to be better than the first (for which a PV has been found), and if later on you find that the second is not better then the first PV needs to stay unchanged.

Well, that is a real problem. But that is why we check whether the move list for the pv array contains the moves.

You check whether the move pv[ply] is a legal move at that ply. But that does not guarantee that pv[ply] is actually part of the root PV. In most cases it isn't.

This method, thus doesn't always return the full length pv, but it works for my purpose:

Code: Select all

1 -0.01 400 3 133k e2e3 
2 0.83 3864 32 120k d2d4 e7e6 
3 -0.04 33537 173 193k b1c3 b8a6 d2d4 
4 1.2 221382 1526 145k e2e3 b8a6 d1h5 a8b8

Note that my baby engine can't search too deep.

Your method won't work correctly even for a 2-ply search. Take this well-known position:
[D]kbK5/pp6/1P6/8/8/8/8/R7 w - - 0 1
Analyze it with pencil and paper. Ignore all non-checking quiet moves except 1.Ra6. Use move ordering: captures prior to other moves. Write down the PV at every node. Look what happens.

[Sven]

I modify my example as follows:
1) 3-ply search instead of 2-ply (and also plus quiescence search);
2) also do not ignore 1.Ra2 (for simplicity, 1.Ra3/.../Ra5 and 1.Rb1/.../Rh1 can be ignored), and try 1.Ra2 before 1.Ra6
If I have done everything right then you get a broken PV when analyzing the subtree of 1.Ra2, and later on the analysis of 1.Ra6 will not repair it. Correct me if I'm wrong (in this case I would need a better example, maybe I was too fast).

[jwes]

Isn't the solution to use two arrays, one to collect possible PVs, and the other to save the current PV?

[Sven]

Isn't the solution to use two arrays, one to collect possible PVs, and the other to save the current PV?

No. You need one "candidate PV" per ply. If you are at ply N, have collected a PV there, and back up to ply N-1 then the new PV at ply N-1 is either the old one that was saved before, or the new move concatenated with the PV of ply N. In any case you now have a new PV at ply N-1. As soon as you back up from there to ply N-2 the same repeats one level higher. Again the decision whether the N-1 PV will become part of the new N-2 PV will be made only when backing up. At level N-2 two different candidate PVs are competing with each other. Changing one's mind requires to replace a whole PV of a node by a different one, not just one move. But at the same time you may need to remember more PV candidates at each higher level as well (x < N-2), where backing up to these higher levels requires the same thing as levels N, N-1, N-2. So neither one array nor two arrays are sufficient for the whole tree.

[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.