Page 1 of 3
Collecting PV in a PVS search ?
Posted: Sun Jun 11, 2017 9:17 am
by MahmoudUthman
1-out of curiosity what are the most efficient way to collect PV in a principal variation search (main & Qsearch) & the most elegant way that you know of ?
2-Do you collect the PV of the Qsearch ?
Re: Collecting PV in a PVS search ?
Posted: Sun Jun 11, 2017 9:53 am
by hgm
It is not different from plain alpha-beta. Whenever you get a move with an in-window score, (after having been verified by all required re-searches), it becomes the first move of the new PV of that node, and you append the PV of the corresponding daughter. I usually put PVs on a global stack (as I also do for move lists), because I don't like to have data of possibly unlimited size in the local variables. (So that you have to make a worst-case size allocation that in practice will only be used for a small fraction.) A node pops its PV from this stack by restoring the stack pointer to the value it had on entry of the node, but the actual PV stays stored there, so that the parent can pick it up to construct its own.
I usually do not have a separate routine for QS, as what has to be done in QS and full-width search is practically identical. Collecting PV is one of those things.
Re: Collecting PV in a PVS search ?
Posted: Sun Jun 11, 2017 12:23 pm
by elcabesa
i did it this way
http://vajoletchess.blogspot.it/2013/11 ... cipal.html
today I use a std::list instead of a std::Vector because it's faster, You can find the new code in vajolet, but it's very similar to the one explained in the blog.
Re: Collecting PV in a PVS search ?
Posted: Sun Jun 11, 2017 1:15 pm
by cdani
MahmoudUthman wrote:1-out of curiosity what are the most efficient way to collect PV in a principal variation search (main & Qsearch) & the most elegant way that you know of ?
2-Do you collect the PV of the Qsearch ?
1 - I use triangular pv tables from the beginnings, so is one of the things pending to optimize that I have. Anyway I think is not terrible slow.
2 - No. The pv is already long enough that nobody looks at it till the end.
Re: Collecting PV in a PVS search ?
Posted: Sun Jun 11, 2017 1:58 pm
by mar
elcabesa wrote:today I use a std::list instead of a std::Vector because it's faster,
Really?!
std::list is typically implemented as doubly-linked list and unless you provide your own allocator it does 1 memory allocation per item added.
How can it possibly be faster than a dynamic array (vector)?
std::list is #1 most useless container
I agree with Daniel: triangular is the way to go, compact, fast, no allocations whatsoever (you already ply-limit the search anyway).
Re: Collecting PV in a PVS search ?
Posted: Sun Jun 11, 2017 2:40 pm
by hgm
Well, a stack in a linear array seems better; it avoids 2-d addressing, and is more compact.
Code: Select all
typedef int Move;
Move pv[MAXPLY*MAXPLY];
int pvPtr;
int
Search ()
{
int myPV = pvPtr;
pv[pvPtr++] = INVALID; // initialize empty PV
for(ALL_MOVES)
{
...
if(score > alpha) {
if(score >= beta) break; // cutoff
int p = pvPtr; // PV of daughter was left here
pvPtr = myPV; // pop previous PV
pv[pvPtr++] = move; // new PV move
while((pv[pvPtr++] = pv[p++]) != INVALID) ; // append PV of daughter to it
}
}
pvPtr = myPV; // pop PV (but leave it above stack top)
}
Re: Collecting PV in a PVS search ?
Posted: Sun Jun 11, 2017 2:53 pm
by elcabesa
mar wrote:elcabesa wrote:today I use a std::list instead of a std::Vector because it's faster,
Really?!
std::list is typically implemented as doubly-linked list and unless you provide your own allocator it does 1 memory allocation per item added.
How can it possibly be faster than a dynamic array (vector)?
std::list is #1 most useless container
Code: Select all
if(bestScore > alpha)
{
bestMove = m;
alpha = bestScore;
pvLine.clear();
pvLine.push_back(bestMove);
pvLine.splice(pvLine.end(),childPV);
pvLine is a std::list, I set the bestmove as first element and attach childPV by "splice" ( change of a pointer ).
It avoid data copying. Each pvline change is just:set a new bestmove and "link" the already calculated child.
Re: Collecting PV in a PVS search ?
Posted: Sun Jun 11, 2017 2:55 pm
by mar
hgm wrote:Well, a stack in a linear array seems better; it avoids 2-d addressing, and is more compact.
That's indeed a nice and simple idea, I think you could do with half the size, but the array is small anyway.
Anything that doesn't do dynamic allocations and avoids wasting stack space is more than enough for collecting PV, since it's not about performance.
Re: Collecting PV in a PVS search ?
Posted: Sun Jun 11, 2017 2:58 pm
by syzygy
mar wrote:hgm wrote:Well, a stack in a linear array seems better; it avoids 2-d addressing, and is more compact.
That's indeed a nice and simple idea, I think you could do with half the size, but the array is small anyway.
Anything that doesn't do dynamic allocations and avoids wasting stack space is more than enough for collecting PV, since it's not about performance.
Since the PV is updated only a few times anyway, even invoking some Python routine would probably be good enough...
Re: Collecting PV in a PVS search ?
Posted: Sun Jun 11, 2017 3:04 pm
by hgm
mar wrote: I think you could do with half the size,
Yeah, but then I have to think about whether to use MAXPLY*(MAXPLY+1)/2, or (MAXPLY+1)*(MAXPLY+2)/2, and I was lazy. Unused memory doesn't eat cache, and unused memory pages do not eat TLB.