Futility pruning idea

[maksimKorzh]

It just happens that this evening i decided to implement LMR for my Drofa project,
so i figured i could write in this topic as well.

I used more complex approach using some almalgamm of ideas i found on the CPW and from a Weiss engine.

First, in the initiation of the Search class i calculate base reduction array:

Code: Select all

void Search::init_LMR_array(){
  for (int i = 0; i < 34; i++){
    for (int j = 0; j< 34; j++){
      _lmr_R_array[i][j] = 0.1 + (pow(i, 0.15) * pow(j, 0.15))/1.75;
    }
  }
}

It looks fancy, but in fact for now its mostly should be either 0 or 1(mostly) and may be 2 sometimes.
I will try to tune this later.

Than in the _negamax function

Code: Select all

        
        //LATE MOVE REDUCTIONS
        //mix of ideas from Weiss code and what is written in the chessprogramming wiki
        //
        //For now we dont reduce in the PV, if depth too low, when extention is triggered
        //and when move give check.
        //This can be a subject for a later tuning
        //
        //Currently we try to reduce 4th move and beyond.

        doLMR = !pvNode && depth > 2 && LegalMoveCount > 3 && 
        Extension == 0 && !movedBoard.colorIsInCheck(movedBoard.getActivePlayer());
        if (doLMR){

          //Basic reduction is done according to the array
          //Initiated at the ini() of the Search Class
          //Now mostly 0 -> 1
          int reduction = _lmr_R_array[std::min(33, depth)][std::min(33, LegalMoveCount)];

          //if move is quiet, reduce a bit more
          if (!move.getFlags()){
            reduction++;
          }
          //Avoid to reduce so much that we go to QSearch right away
          int fDepth = std::max(1, depth - 1 - reduction);
          
          //Search with reduced depth around alpha in assumtion
          // that alpha would not be beaten here
          score = -_negaMax(movedBoard, fDepth, -alpha - 1 , -alpha, ply + 1, false);
        }
        
        // Code here is restructured based on Weiss
        // First part is clear here: if we did LMR and score beats alpha
        // We need to do a re-search.
        // 
        // If we did not do LMR: if we are in a non-PV our we already have alpha == beta - 1,
        // and if we are searching 2nd move and so on we already did full window search - 
        // So for both of this cases we do limited window search. 
        //
        // This system is implemented instead of fullDepth = true/false basic approach.
        if (doLMR){
          if (score > alpha){
            score = -_negaMax(movedBoard, depth - 1 + Extension, -alpha - 1, -alpha, ply + 1, false);
          }
        } else if (!pvNode || LegalMoveCount > 1){
          score = -_negaMax(movedBoard, depth - 1 + Extension, -alpha - 1, -alpha, ply + 1, false);
        }

        // If we are in the PV 
        // Search with a full window the first move to calculate bounds
        // or if score improved alpha during the current round of search.
        if  (pvNode) {
          if ((LegalMoveCount == 1) || (score > alpha && score < beta)){
            score = -_negaMax(movedBoard, depth - 1 + Extension, -beta, -alpha, ply + 1, false );  
          }
        }

I reduce here everything (captures, promotions, etc), starting from the 4th move in the overall list.
Moves that are PVnode, cause extension or give check are not reduced.
Quiet moves are reduced with R+1, and now move can be reduced to have depth = 0.

In startpos it gives Drofa +2 depth in the same amount of time spend in comparation to the current tested 1.0.3 version.
I started a testrun to confirm elogain, for now things looks really good. Like super good:

Code: Select all

Score of Drofa_dev vs Drofa_1.0.3: 27 - 9 - 24  [0.650] 60
Elo: 107 +/- 71

If this holds, I really should think on finding some opponents for my engine that are stronger than VICE

Cool! Thanks for sharing!
Maybe one day my engine https://www.youtube.com/watch?v=QUNP-Uj ... wfiWNI76Cs can try challenge yours)