Collecting PVs of Qsearch ?

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.
Post Reply
MahmoudUthman
Posts: 234
Joined: Sat Jan 17, 2015 10:54 pm

Collecting PVs of Qsearch ?

Post by MahmoudUthman » Sat Oct 22, 2016 9:49 pm

what is the simplest way to collect the complete PV from the root to the evaluation ?

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

Re: Collecting PVs of Qsearch ?

Post by hgm » Sat Oct 22, 2016 10:34 pm

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&#58; new PV node
      MOVE *p = pvPtr; // PV left by daughter
      pvPtr = pvStart; // pop old PV
      *pvPtr++ = move; // new best move of this node
      while&#40;*pvPtr++ = *p++) &#123;&#125; // copy PV of daughter behind it
    &#125;
  ...
  pvPtr = pvStart; // cleanup
  return alpha;
&#125;

Sven
Posts: 3826
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Collecting PVs of Qsearch ?

Post by Sven » Sat Oct 22, 2016 10:57 pm

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 &#123;
    Move move&#91;63&#93;;
    int  size;

    PV&#40;) &#58; size&#40;0&#41; &#123;&#125;

    void concat&#40;Move const & m, PV const & pv&#41;
    &#123;
        move&#91;0&#93; = m;
        int pvSize = min&#40;pv.size, 63 - 1&#41;;
        for &#40;int i = 1; i <= pvSize; i++) &#123;
            move&#91;i&#93; = pv&#91;i - 1&#93;;
        &#125;
        size = pvSize + 1;
    &#125;
&#125;;

int search&#40;..., PV & pv&#41; // same for qSearch
&#123;
    ...
    for &#40;all moves&#41; &#123;
        PV localPV;
        ...
        int v = -search&#40;..., localPV&#41;;
        ...
        if &#40;v >= beta&#41; CUTOFF;
        if &#40;v > alpha&#41; &#123;
            pv.concat&#40;move, localPV&#41;;
        &#125;
    &#125;
    ...
&#125;
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.

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

Re: Collecting PVs of Qsearch ?

Post by elcabesa » Sun Oct 23, 2016 8:15 am

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

MahmoudUthman
Posts: 234
Joined: Sat Jan 17, 2015 10:54 pm

Re: Collecting PVs of Qsearch ?

Post by MahmoudUthman » Sun Oct 23, 2016 11:26 pm

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

Post Reply