Collecting Principal variation

[Sven]

The problem at the root is why you need two arrays, one for the current PV and one for a possible new PV. Below the root, when you have a fail-high followed by a fail-low, you re-search all the moves which will regenerate the PV.

No. PVS algorithm behaves the same at all full-width nodes including the root. So the same reason that explains why you need a candidate PV for the root node also explains why you need a candidate PV for other nodes, to avoid destroying candidate PVs of higher-level nodes.

[hgm]

Something like this:

Code: Select all

const int NONE = -1;

typedef struct { int start, last; } PV;
typedef struct { int next; Move info; } Cell;

Cell cell[1000];

int freeList;

void Init()
{
  for i=1; i<1000; i++) cell[i].next = i-1;
  freeList = i-1;
}

Search(int alpha, int beta, PV *pv)
{
  PV daughterPV;
  pv->start = NONE; // initialize empty PV
  while((move = NextMove())) {
    MakeMove(move);
    score = -Search(-beta, -alpha, &daughterPV);
    UnMake();
    if(score > alpha) {
      if(pv->start != NONE) cell[pv->last].next = freeList, freeList = pv->start, pv->start = 0; // trash previous candidate PV
      if(score >= beta) return beta;
      alpha = score; // we get here only in PV nodes
      pv->start = freeList; freeList = cell[freeList].next; // allocate cell for current move
      cell[pv->start].info = move;
      cell[pv->start].next = daughterPV.start; pv->last = daughterPV.last; // append daughter PV to it
      if(daughterPV.start == NONE) pv->last = pv->start; // if daughter did not supply PV, our move is last one
    }
  }
  return alpha;
}

Instead of just a single info field with the best move, you could locate all 'local variables' of Search() in the Cell structure, so they would be preserved for the next visit of this node, when 'following the PV' in the next (ID or IID) iteration. This could include the (sorted) move list.