Collecting PV in a PVS search ?

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, 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 PV in a PVS search ?

Post by MahmoudUthman » Sun Jun 11, 2017 7:17 am

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 ?

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

Re: Collecting PV in a PVS search ?

Post by hgm » Sun Jun 11, 2017 7:53 am

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.

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

Re: Collecting PV in a PVS search ?

Post by elcabesa » Sun Jun 11, 2017 10:23 am

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.

User avatar
cdani
Posts: 2104
Joined: Sat Jan 18, 2014 9:24 am
Location: Andorra
Contact:

Re: Collecting PV in a PVS search ?

Post by cdani » Sun Jun 11, 2017 11:15 am

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.

mar
Posts: 2001
Joined: Fri Nov 26, 2010 1:00 pm
Location: Czech Republic
Full name: Martin Sedlak

Re: Collecting PV in a PVS search ?

Post by mar » Sun Jun 11, 2017 11:58 am

elcabesa wrote:today I use a std::list instead of a std::Vector because it's faster,
Really?! :shock:
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).

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

Re: Collecting PV in a PVS search ?

Post by hgm » Sun Jun 11, 2017 12:40 pm

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)
}

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

Re: Collecting PV in a PVS search ?

Post by elcabesa » Sun Jun 11, 2017 12:53 pm

mar wrote:
elcabesa wrote:today I use a std::list instead of a std::Vector because it's faster,
Really?! :shock:
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.

mar
Posts: 2001
Joined: Fri Nov 26, 2010 1:00 pm
Location: Czech Republic
Full name: Martin Sedlak

Re: Collecting PV in a PVS search ?

Post by mar » Sun Jun 11, 2017 12:55 pm

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.

syzygy
Posts: 4455
Joined: Tue Feb 28, 2012 10:56 pm

Re: Collecting PV in a PVS search ?

Post by syzygy » Sun Jun 11, 2017 12:58 pm

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...

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

Re: Collecting PV in a PVS search ?

Post by hgm » Sun Jun 11, 2017 1:04 pm

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.

Post Reply