Futility pruning idea

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.
maksimKorzh
Posts: 214
Joined: Sat Sep 08, 2018 3:37 pm
Location: Ukraine
Full name: Maksim Korzh
Contact:

Futility pruning idea

Post by maksimKorzh » Wed Sep 09, 2020 1:44 pm

Hi Guys

I've been researching CPW for the last few days to make sure the idea I'd like to ask your opinion about is not present there (please correct me if I'm wrong!)

So the idea is to DROP moves scored as 0 (so I know for sure they are not PV/Captures/killers/history) when depth is greater than 3 (assuming IID implemented so PV/killer/history has been initialized).
Here's how I'm trying it now:

Code: Select all

    // loop over move list
    for (int count = 0; count < move_list->count; count++)
    {                                                                     
        // "Futility?" pruning
        if (depth > 3  && score_move(move_list->moves[0]) == 20000 && !score_move(move_list->moves[count]))
            continue;
    }
Now here're the results of this for "tricky position":


My move list after getting sorted:

Code: Select all

    // my idea is to drop moves starting from a2a4 and NOT MAKE/NOT EVALUATE them AT ALL
     move: e2a6   score: 20000
     move: f3f6   score: 10201
     move: d5e6   score: 10105
     move: g2h3   score: 10105
     move: e5g6   score: 10104
     move: e5d7   score: 10104
     move: e5f7   score: 10104
     move: f3h3   score: 10101
     move: f3h5   score: 6
     move: a2a4   score: 0
     move: e5c6   score: 0
     move: b2b3   score: 0
     move: e5c4   score: 0
     move: e5g4   score: 0
     move: e5d3   score: 0
     move: c3b5   score: 0
     move: c3a4   score: 0
     move: c3b1   score: 0
     move: c3d1   score: 0
     move: d2h6   score: 0
     move: d2g5   score: 0
     move: d2f4   score: 0
     move: d2e3   score: 0
     move: d2c1   score: 0
     move: g2g3   score: 0
     move: e2b5   score: 0
     move: e2c4   score: 0
     move: e2d3   score: 0
     move: e2d1   score: 0
     move: e2f1   score: 0
     move: a1b1   score: 0
     move: a1c1   score: 0
     move: a1d1   score: 0
     move: h1f1   score: 0
     move: h1g1   score: 0
     move: g2g4   score: 0
     move: f3f5   score: 0
     move: d5d6   score: 0
     move: f3f4   score: 0
     move: f3g4   score: 0
     move: f3d3   score: 0
     move: f3e3   score: 0
     move: f3g3   score: 0
     move: a2a3   score: 0
     move: e1g1   score: 0
     move: e1c1   score: 0
     move: e1d1   score: 0
     move: e1f1   score: 0

Code: Select all

// PRUNING
info score cp 30 depth 1 nodes 774 pv e2a6 b4c3 
info score cp 30 depth 2 nodes 2919 pv e2a6 b4c3 
info score cp 15 depth 3 nodes 13444 pv e2a6 b4c3 b2c3 e6d5 
info score cp 15 depth 4 nodes 37675 pv e2a6 b4c3 b2c3 e6d5 
info score cp 0 depth 5 nodes 143033 pv e2a6 e6d5 c3d5 b6d5 e4d5 e7e5 
bestmove e2a6

// NO PRUNING
info score cp 30 depth 1 nodes 774 pv e2a6 b4c3 
info score cp 30 depth 2 nodes 2919 pv e2a6 b4c3 
info score cp 15 depth 3 nodes 13444 pv e2a6 b4c3 b2c3 e6d5 
info score cp 15 depth 4 nodes 88274 pv e2a6 b4c3 b2c3 e6d5 
info score cp 0 depth 5 nodes 372537 pv e2a6 e6d5 c3d5 b6d5 e4d5 e7e5 
bestmove e2a6
VIsually when my engine plays vs itself at say depth 6 it makes almost the same moves.
But feel that something might be wrong with this approach because it's too easy.

Please tell me what do you think?
Did anybody apply this technique (maybe with some modifications) ?

THANKS IN ADVANCE!
BBC - didactic UCI chess engine written by Code Monkey King
https://github.com/maksimKorzh/bbc

82 video YouTube series
https://www.youtube.com/watch?v=QUNP-Uj ... wfiWNI76Cs

Kieren Pearson
Posts: 31
Joined: Tue Dec 31, 2019 1:52 am
Full name: Kieren Pearson

Re: Futility pruning idea

Post by Kieren Pearson » Wed Sep 09, 2020 2:46 pm

I'm assuming that PV gets assigned a score of 20000, captures a score of 10000 + captured piece value and then killers / history a small positive score.

After some thought, this seems like a psudo-implementation of LMR. Instead of searching with a reduced depth, you are completely cutting off if they are far enough down the move order, but we still search PV, captures, killers and history to full depth.

I would look into and implement LMR, which will be even better than this in actual games. If I understand the implementation, any of those quiet moves will NEVER be searched no matter the depth, which is a very big issue if one of those moves for example gave check and delivered checkmate and your engine missed that

maksimKorzh
Posts: 214
Joined: Sat Sep 08, 2018 3:37 pm
Location: Ukraine
Full name: Maksim Korzh
Contact:

Re: Futility pruning idea

Post by maksimKorzh » Wed Sep 09, 2020 3:31 pm

Kieren Pearson wrote:
Wed Sep 09, 2020 2:46 pm
I'm assuming that PV gets assigned a score of 20000, captures a score of 10000 + captured piece value and then killers / history a small positive score.

After some thought, this seems like a psudo-implementation of LMR. Instead of searching with a reduced depth, you are completely cutting off if they are far enough down the move order, but we still search PV, captures, killers and history to full depth.

I would look into and implement LMR, which will be even better than this in actual games. If I understand the implementation, any of those quiet moves will NEVER be searched no matter the depth, which is a very big issue if one of those moves for example gave check and delivered checkmate and your engine missed that
Hi Kieren

Yes, all of your assumptions are correct.
Could you please point out to LMR implementation (didactic one would be perfect)
BBC - didactic UCI chess engine written by Code Monkey King
https://github.com/maksimKorzh/bbc

82 video YouTube series
https://www.youtube.com/watch?v=QUNP-Uj ... wfiWNI76Cs

Kieren Pearson
Posts: 31
Joined: Tue Dec 31, 2019 1:52 am
Full name: Kieren Pearson

Re: Futility pruning idea

Post by Kieren Pearson » Wed Sep 09, 2020 3:46 pm

https://web.archive.org/web/20150212051 ... m/lmr.html

Not sure what didactic means but here you go

maksimKorzh
Posts: 214
Joined: Sat Sep 08, 2018 3:37 pm
Location: Ukraine
Full name: Maksim Korzh
Contact:

Re: Futility pruning idea

Post by maksimKorzh » Wed Sep 09, 2020 3:56 pm

Kieren Pearson wrote:
Wed Sep 09, 2020 3:46 pm
https://web.archive.org/web/20150212051 ... m/lmr.html

Not sure what didactic means but here you go
Just perfect! Exactly what I was looking for!
Thanks you so much, Kieren!
BBC - didactic UCI chess engine written by Code Monkey King
https://github.com/maksimKorzh/bbc

82 video YouTube series
https://www.youtube.com/watch?v=QUNP-Uj ... wfiWNI76Cs

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

Re: Futility pruning idea

Post by hgm » Wed Sep 09, 2020 4:36 pm

Does this work? :shock: It seems to me it should completely cripple the engine. It would be blind to any tactics deeper than 3 ply.

maksimKorzh
Posts: 214
Joined: Sat Sep 08, 2018 3:37 pm
Location: Ukraine
Full name: Maksim Korzh
Contact:

Re: Futility pruning idea

Post by maksimKorzh » Wed Sep 09, 2020 5:20 pm

hgm wrote:
Wed Sep 09, 2020 4:36 pm
Does this work? :shock: It seems to me it should completely cripple the engine. It would be blind to any tactics deeper than 3 ply.
I've tested my engine vs TSCP with this weird idea and without.
The games are pretty similar (well my engine still getting mated due to the poor evaluation)
With this weird idea or without my engine is getting mated almost exactly the same
The only difference is that with this idea it plays 2 2.5 faster than TSCP at the same fixed depth
while without it takes about the same time for both engines to make a move.

I've already realized that this is a BAD idea. I'm now researching LMR.
While I love the idea (hemce this weird idea) still I'm encountering some issues with understanding the implementation.
Any additional help regarding how to implement LMR is appreciated.
BBC - didactic UCI chess engine written by Code Monkey King
https://github.com/maksimKorzh/bbc

82 video YouTube series
https://www.youtube.com/watch?v=QUNP-Uj ... wfiWNI76Cs

maksimKorzh
Posts: 214
Joined: Sat Sep 08, 2018 3:37 pm
Location: Ukraine
Full name: Maksim Korzh
Contact:

Re: Futility pruning idea

Post by maksimKorzh » Wed Sep 09, 2020 6:54 pm

OMG!

I've just implemented LMR:

Code: Select all

            // First move, use full-window search
            if(moves_searched == 0) 
            {                        
                // recursive negamax call
                score = -negamax(-beta, -alpha, depth - 1);
            }   
            // LMR
            else {   
                if (moves_searched >= full_depth_moves &&
                    depth >= reduction_limit &&
                    in_check == 0 &&
                    get_move_capture(move_list->moves[count]) == 0 &&
                    get_move_promoted(move_list->moves[count]) == 0
                   )
                {
                    // Search this move with reduced depth:
                    score = -negamax(- alpha - 1, -alpha, depth-2);
                }
                
                else score = alpha + 1;  // Hack to ensure that full-depth search is done
        

                if(score > alpha)
                {
                    score = -negamax(-alpha - 1, -alpha, depth-1);
                    
                    // research on fail    
                    if((score > alpha) && (score < beta))
                        score = -negamax(-beta, -alpha, depth-1);
                }      
            }
And now while my engine hits depth 7 in 2+0 blitz TSCP only goes depth 6
My engine has mated TSCP and the clock at the end of game is:
TSCP: 15 sec left
BBC(my engine): 56 sec left

AMAZING!
Thanks for providing an amazing resource so I could make use of it!!!


BBC - didactic UCI chess engine written by Code Monkey King
https://github.com/maksimKorzh/bbc

82 video YouTube series
https://www.youtube.com/watch?v=QUNP-Uj ... wfiWNI76Cs

No4b
Posts: 23
Joined: Thu Jun 18, 2020 1:21 pm
Location: Moscow
Full name: Alexander Litov

Re: Futility pruning idea

Post by No4b » Thu Sep 10, 2020 12:19 am

maksimKorzh wrote:
Wed Sep 09, 2020 6:54 pm
OMG!

I've just implemented LMR:

Code: Select all

            // First move, use full-window search
            if(moves_searched == 0) 
            {                        
                // recursive negamax call
                score = -negamax(-beta, -alpha, depth - 1);
            }   
            // LMR
            else {   
                if (moves_searched >= full_depth_moves &&
                    depth >= reduction_limit &&
                    in_check == 0 &&
                    get_move_capture(move_list->moves[count]) == 0 &&
                    get_move_promoted(move_list->moves[count]) == 0
                   )
                {
                    // Search this move with reduced depth:
                    score = -negamax(- alpha - 1, -alpha, depth-2);
                }
                
                else score = alpha + 1;  // Hack to ensure that full-depth search is done
        

                if(score > alpha)
                {
                    score = -negamax(-alpha - 1, -alpha, depth-1);
                    
                    // research on fail    
                    if((score > alpha) && (score < beta))
                        score = -negamax(-beta, -alpha, depth-1);
                }      
            }
And now while my engine hits depth 7 in 2+0 blitz TSCP only goes depth 6
My engine has mated TSCP and the clock at the end of game is:
TSCP: 15 sec left
BBC(my engine): 56 sec left

AMAZING!
Thanks for providing an amazing resource so I could make use of it!!!


Great work! Code is really simple, understandable and effective.

No4b
Posts: 23
Joined: Thu Jun 18, 2020 1:21 pm
Location: Moscow
Full name: Alexander Litov

Re: Futility pruning idea

Post by No4b » Thu Sep 10, 2020 12:47 am

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 :)

Post Reply