Collecting PV in a PVS search ?
Moderators: hgm, Dann Corbit, Harvey Williamson
Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
-
- Posts: 234
- Joined: Sat Jan 17, 2015 10:54 pm
Collecting PV in a PVS search ?
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 ?
2-Do you collect the PV of the Qsearch ?
- hgm
- Posts: 25887
- Joined: Fri Mar 10, 2006 9:06 am
- Location: Amsterdam
- Full name: H G Muller
- Contact:
Re: Collecting PV in a PVS search ?
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.
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 ?
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.
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 ?
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.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 ?
2 - No. The pv is already long enough that nobody looks at it till the end.
Daniel José -
http://www.andscacs.com

Re: Collecting PV in a PVS search ?
Really?!elcabesa wrote:today I use a std::list instead of a std::Vector because it's faster,

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).
- hgm
- Posts: 25887
- Joined: Fri Mar 10, 2006 9:06 am
- Location: Amsterdam
- Full name: H G Muller
- Contact:
Re: Collecting PV in a PVS search ?
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 ?
mar wrote:Really?!elcabesa wrote:today I use a std::list instead of a std::Vector because it's faster,
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);
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 ?
That's indeed a nice and simple idea, I think you could do with half the size, but the array is small anyway.hgm wrote:Well, a stack in a linear array seems better; it avoids 2-d addressing, and is more compact.
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 ?
Since the PV is updated only a few times anyway, even invoking some Python routine would probably be good enough...mar wrote:That's indeed a nice and simple idea, I think you could do with half the size, but the array is small anyway.hgm wrote:Well, a stack in a linear array seems better; it avoids 2-d addressing, and is more compact.
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.
- hgm
- Posts: 25887
- Joined: Fri Mar 10, 2006 9:06 am
- Location: Amsterdam
- Full name: H G Muller
- Contact:
Re: Collecting PV in a PVS search ?
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.mar wrote: I think you could do with half the size,