Collecting PVs of Qsearch ?

[MahmoudUthman]

what is the simplest way to collect the complete PV from the root to the evaluation ?

[hgm]

The way I do it in Fairy-Max: do this both in Search and QSearch

Code: Select all

MOVE pvLines[10000];
MOVE *pvPtr = pvLines;

Search()
{
  MOVE *pvStart = pvPtr;
  *pvPtr++ = 0; // invalid move code to indicate end of(now empty) PV
  ...
    if(score > alpha) {
      alpha = score;
      if(score >= beta) break; // cutoff
      // alpha < score < beta&#58; new PV node
      MOVE *p = pvPtr; // PV left by daughter
      pvPtr = pvStart; // pop old PV
      *pvPtr++ = move; // new best move of this node
      while&#40;*pvPtr++ = *p++) &#123;&#125; // copy PV of daughter behind it
    &#125;
  ...
  pvPtr = pvStart; // cleanup
  return alpha;
&#125;

[Sven]

what is the simplest way to collect the complete PV from the root to the evaluation ?

Or this way (maybe a bit more readable but slightly slower than the HGM code):

Code: Select all

struct PV {
    Move move[63];
    int  size;

    PV() : size(0) {}

    void concat(Move const & m, PV const & pv)
    {
        move[0] = m;
        int pvSize = min(pv.size, 63 - 1);
        for &#40;int i = 1; i <= pvSize; i++) &#123;
            move&#91;i&#93; = pv&#91;i - 1&#93;;
        &#125;
        size = pvSize + 1;
    &#125;
&#125;;

int search&#40;..., PV & pv&#41; // same for qSearch
&#123;
    ...
    for &#40;all moves&#41; &#123;
        PV localPV;
        ...
        int v = -search&#40;..., localPV&#41;;
        ...
        if &#40;v >= beta&#41; CUTOFF;
        if &#40;v > alpha&#41; &#123;
            pv.concat&#40;move, localPV&#41;;
        &#125;
    &#125;
    ...
&#125;

and in the iterative deepening loop you have the root PV.

In fact it is almost the same as the well-known "triangular PV" approach, only with a PV as as separate structure instead of having a two-dimensional array.

[elcabesa]

I'm using c++ in my engine nad I started collecting PV using standard container of std::library

in my code PV is a std::list<Move>

all the time I have to append the PV of a subtree search to the PV i do the following

pvLine.clear(); // clear the PV
pvLine.push_back(bestMove); //set bestMove as the startingMove
pvLine.splice(pvLine.end(),childPV); // append the subtree

std::list is a linked list so splice doesn't do copies of elements but it simply change change apointer of a list

If you like it you could find the code in search.cpp of my project

[MahmoudUthman]

One last thing , is it worth the trouble to provide full PV lines for the user all the time ? I mean extracting PVs from the TT seems good enough -"for some reason it reduces search time by a small but measurable amount ! cache?"- most of the time ?!