Principal Variation Search

Principal Variation Search (PVS) is an Alpha-Beta optimization.

MinMaxPVS(Player, Depth, Alpha, Beta)
{
   if ( Depth == 0 )
      return Evaluation(Position)

   Generate_Moves(Player)

   Sort_Moves()

   Best_Score = -INFINITE

   while ( Get_Next_Move(Move) )
   {
      Make_Move(Move)

      if ( First_Move(Move) )
         Score = -MinMaxPVS(-Player, Depth - 1, -Beta, -Alpha)
      else
      {
         Score = -MinMaxPVS(-Player, Depth - 1, -Alpha - 1, -Alpha)
         if ( Score > Alpha && Score < Beta )
            Score = -MinMaxPVS(-Player, Depth - 1, -Beta, -Alpha)
      }

      UnMake_Move(Move)

      if ( Score > Best_Score )
      {
         Best_Score = Score

         if ( Best_Score > Alpha )
         {
            Alpha = Best_Score
            if ( Best_Score >= Beta )
               return Best_Score
         }
      }
   }

   return Best_Score
}