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: new PV node
      MOVE *p = pvPtr; // PV left by daughter
      pvPtr = pvStart; // pop old PV
      *pvPtr++ = move; // new best move of this node
      while(*pvPtr++ = *p++) {} // copy PV of daughter behind it
    }
  ...
  pvPtr = pvStart; // cleanup
  return alpha;
}

[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 (int i = 1; i <= pvSize; i++) {
            move[i] = pv[i - 1];
        }
        size = pvSize + 1;
    }
};

int search(..., PV & pv) // same for qSearch
{
    ...
    for (all moves) {
        PV localPV;
        ...
        int v = -search(..., localPV);
        ...
        if (v >= beta) CUTOFF;
        if (v > alpha) {
            pv.concat(move, localPV);
        }
    }
    ...
}

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 ?!