Principal Variation Search Question

[osborne]

Hi All,

I am trying to implement PVS (Principle Variation Search) into my engine. I read the PVS article on the Chess Programming Wiki and it showed two different implementations:

Code: Select all

int pvSearch( int alpha, int beta, int depth ) {
   if( depth == 0 ) return quiesce( alpha, beta );
   for ( all moves)  {
      make
      if ( first move ) {
         score = -pvSearch(-beta, -alpha, depth - 1);
      } else {
         score = -pvSearch(-alpha-1, -alpha, depth - 1);
         if ( score > alpha && beta - alpha > 1 )
         // beta - alpha > 1 prevents redundant re-search of Non-PV nodes.
         // Note that in rare cases this conditions is true for PV nodes.
         // Some engines prevent that by setting a boolean PvNode variable
         // to determine if position is in a PV node. But it's generally
         // considered as too rare to cause considereable stength loss.
            score = -pvSearch(-beta, -alpha, depth - 1); // re-search
      }
      unmake
      if( score >= beta )
         return beta;   // fail-hard beta-cutoff
      if( score > alpha ) {
         alpha = score; // alpha acts like max in MiniMax
      }
   }
   return alpha; // fail-hard
}

Code: Select all

int pvSearch( int alpha, int beta, int depth ) {
   if( depth == 0 ) return quiesce(alpha, beta);
   bool bSearchPv = true;
   for ( all moves)  {
      make
      if ( bSearchPv ) {
         score = -pvSearch(-beta, -alpha, depth - 1);
      } else {
         score = -zwSearch(-alpha, depth - 1);
         if ( score > alpha ) // in fail-soft ... && score < beta ) is common
            score = -pvSearch(-beta, -alpha, depth - 1); // re-search
      }
      unmake
      if( score >= beta )
         return beta;   // fail-hard beta-cutoff
      if( score > alpha ) {
         alpha = score; // alpha acts like max in MiniMax
         bSearchPv = false;   // *1)
      }
   }
   return alpha;
}

// fail-hard zero window search, returns either beta-1 or beta
int zwSearch(int beta, int depth ) {
   // alpha == beta - 1
   // this is either a cut- or all-node
   if( depth == 0 ) return quiesce(beta-1, beta);
   for ( all moves)  {
     make
     score = -zwSearch(1-beta, depth - 1);
     unmake
     if( score >= beta )
        return beta;   // fail-hard beta-cutoff
   }
   return beta-1; // fail-hard, return alpha
}

I understand that the split search function is just an aesthetic difference, but the bSearchPV flag seems to be a difference in logic. My question: Is one implementation better than the other? If so, then which one is?

Thank you for your time,
Jeff Osborne

[hgm]

Indeed, the second implementation closes the window only after a move is found that raises alpha. Which makes a difference if that is not the first move.

I have even seen implementations that never make a first-move exemption, and even do a closed-window pilot search before searching the PV with open window. Normally that pilot search would fail high, of course, so you would redo it with open window. This goes in the opposit direction as the second implementation from the wiki.

The number of open-window nodes in all cases would be very small, so this probably doesn't have much impact. It is probably much more important how carefully you select an alternative when the PV move fails low. (E.g. through IDD, and starting from which depth.) Just searching all moves at maximum depth with open window in the order dictated by the static move ordering seems a very expensive method.