Collecting PV in a PVS search ?

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

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

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

[cdani]

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]

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

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

[elcabesa]

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.

[mar]

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]

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

[hgm]

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.