Page 1 of 1
Collecting PVs of Qsearch ?
Posted: Sat Oct 22, 2016 11:49 pm
by MahmoudUthman
what is the simplest way to collect the complete PV from the root to the evaluation ?
Re: Collecting PVs of Qsearch ?
Posted: Sun Oct 23, 2016 12:34 am
by 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;
}
Re: Collecting PVs of Qsearch ?
Posted: Sun Oct 23, 2016 12:57 am
by Sven
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 {
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.
Re: Collecting PVs of Qsearch ?
Posted: Sun Oct 23, 2016 10:15 am
by 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
Re: Collecting PVs of Qsearch ?
Posted: Mon Oct 24, 2016 1:26 am
by 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 ?!