## Collecting PVs of Qsearch ?

Discussion of chess software programming and technical issues.

Moderators: hgm, Dann Corbit, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
MahmoudUthman
Posts: 234
Joined: Sat Jan 17, 2015 10:54 pm

### Collecting PVs of Qsearch ?

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

hgm
Posts: 26576
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

### Re: Collecting PVs of Qsearch ?

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;

Sven
Posts: 4023
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

### Re: Collecting PVs of Qsearch ?

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.

elcabesa
Posts: 855
Joined: Sun May 23, 2010 11:32 am
Contact:

### Re: Collecting PVs of Qsearch ?

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
Posts: 234
Joined: Sat Jan 17, 2015 10:54 pm

### Re: Collecting PVs of Qsearch ?

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