Page 1 of 1

### Collecting PVs of Qsearch ?

Posted: Sat Oct 22, 2016 9:49 pm
what is the simplest way to collect the complete PV from the root to the evaluation ?

### Re: Collecting PVs of Qsearch ?

Posted: Sat Oct 22, 2016 10:34 pm
The way I do it in Fairy-Max: do this both in Search and QSearch

Code: Select all

``````MOVE pvLines&#91;10000&#93;;
MOVE *pvPtr = pvLines;

Search&#40;)
&#123;
MOVE *pvStart = pvPtr;
*pvPtr++ = 0; // invalid move code to indicate end of&#40;now empty&#41; PV
...
if&#40;score > alpha&#41; &#123;
alpha = score;
if&#40;score >= beta&#41; 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;
``````

### Re: Collecting PVs of Qsearch ?

Posted: Sat Oct 22, 2016 10:57 pm
MahmoudUthman wrote: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 &#123;
Move move&#91;63&#93;;
int  size;

PV&#40;) &#58; size&#40;0&#41; &#123;&#125;

void concat&#40;Move const & m, PV const & pv&#41;
&#123;
move&#91;0&#93; = m;
int pvSize = min&#40;pv.size, 63 - 1&#41;;
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.

### Re: Collecting PVs of Qsearch ?

Posted: Sun Oct 23, 2016 8:15 am
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

### Re: Collecting PVs of Qsearch ?

Posted: Sun Oct 23, 2016 11:26 pm
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 ?!