Futility pruning ?

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
MahmoudUthman
Posts: 229
Joined: Sat Jan 17, 2015 10:54 pm

Futility pruning ?

Post by MahmoudUthman » Sat Mar 04, 2017 11:05 pm

could someone provide a pseudo code for the different forms of futility pruning and what are the advantages/disadvantages for one over the other ?

cetormenter
Posts: 169
Joined: Sun Oct 28, 2012 8:46 pm

Re: Futility pruning ?

Post by cetormenter » Sun Mar 05, 2017 12:51 am

Code: Select all

for (move : moveList)
{
   if &#40;Depth < FUTILITY_DEPTH && !inCheck && searchedMoves > 1 && !IsInteresting&#40;move&#41; && eval + FUTILITY_MARGIN < Alpha&#41;
      continue;

   //Rest of moveloop goes here

&#125;;
More detailed information can be found on the programming wiki https://chessprogramming.wikispaces.com ... ty+Pruning.

The main considerations for futility pruning is what goes into the IsInteresting function.

MahmoudUthman
Posts: 229
Joined: Sat Jan 17, 2015 10:54 pm

Re: Futility pruning ?

Post by MahmoudUthman » Sun Mar 05, 2017 1:05 am

cetormenter wrote:

Code: Select all

for &#40;move &#58; moveList&#41;
&#123;
   if &#40;Depth < FUTILITY_DEPTH && !inCheck && searchedMoves > 1 && !IsInteresting&#40;move&#41; && eval + FUTILITY_MARGIN < Alpha&#41;
      continue;

   //Rest of moveloop goes here

&#125;;
More detailed information can be found on the programming wiki https://chessprogramming.wikispaces.com ... ty+Pruning.

The main considerations for futility pruning is what goes into the IsInteresting function.
thank you , but what about this code in sf despite having an equivalent to the above in it's move loop ?

Code: Select all

// Step 7. Futility pruning&#58; child node &#40;skipped when in check&#41;
    if (   !rootNode
        &&  depth < 7 * ONE_PLY
        &&  eval - futility_margin&#40;depth&#41; >= beta
        &&  eval < VALUE_KNOWN_WIN  // Do not return unproven wins
        &&  pos.non_pawn_material&#40;pos.side_to_move&#40;)))
        return eval;

mjlef
Posts: 1367
Joined: Thu Mar 30, 2006 12:08 pm
Contact:

Re: Futility pruning ?

Post by mjlef » Sun Mar 05, 2017 2:57 am

MahmoudUthman wrote:
cetormenter wrote:

Code: Select all

for &#40;move &#58; moveList&#41;
&#123;
   if &#40;Depth < FUTILITY_DEPTH && !inCheck && searchedMoves > 1 && !IsInteresting&#40;move&#41; && eval + FUTILITY_MARGIN < Alpha&#41;
      continue;

   //Rest of moveloop goes here

&#125;;
More detailed information can be found on the programming wiki https://chessprogramming.wikispaces.com ... ty+Pruning.

The main considerations for futility pruning is what goes into the IsInteresting function.
thank you , but what about this code in sf despite having an equivalent to the above in it's move loop ?

Code: Select all

// Step 7. Futility pruning&#58; child node &#40;skipped when in check&#41;
    if (   !rootNode
        &&  depth < 7 * ONE_PLY
        &&  eval - futility_margin&#40;depth&#41; >= beta
        &&  eval < VALUE_KNOWN_WIN  // Do not return unproven wins
        &&  pos.non_pawn_material&#40;pos.side_to_move&#40;)))
        return eval;
In this case, SF is doing this after the evaluation which they do above the move loop. They compare against bet, with the assumption that if the current side's is far ahead of beta, then they likely have at least one move that would, if searched, fail high (return a score >=beta). This fails in zugzwang positions, of course. Many programs call this "static null move pruning", since it is a bit like null move in that is needs a score above beta, and assume the right to move generally has some value.

There is another section of code in Stockfish inside the move loop that is more like traditional futility pruning. Since this is done before making the move and doing a full evaluation, the margins used are normally bigger, since the eval before making a move is not so good at predicting if after. I believe they do not do futility pruning if the move is a capture and some other conditions. They compare against alpha, and prune score too low instead of too high.

A third futility pruning is used in many programs in the qsearch which is used even in captures. If your eval was say -500 centipawns, and program is considering searching a pawn capture (lets say pawn is not passed and worth 100 centipawn), and lets say alpha is 0, then you can prune this move (as long as it say is not a check if you are in the check including parts of your qsearch).

Mark

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

Re: Futility pruning ?

Post by hgm » Sun Mar 05, 2017 8:18 am

This "static null-move pruning" is basically futility pruning that could have been done in the parent node, but based on the exact evaluation (for which you have to make the move first) rather than an estimate. Usually futility pruning uses the current evaluation plus the estimated gain by the move to be pruned, like

Code: Select all

if&#40;currentEval + MaterialCaptured&#40;move&#41; < alpha - MARGIN&#41; continue; // prune move
In the daughter (after making 'move') that condition would look like

Code: Select all

if&#40;-&#40;parentEval + MaterialCaptured&#40;lastMove&#41;) > beta + MARGIN&#41; return;   // prune node
So the difference is that it uses currentEval instead of -(parentEval + materialCaptured(lastMove)). As the margin is rather large, the importance of very precisely knowing the current eval is questionable. While it is beyond question that it takes a lot of extra work (MakeMove + Evaluate + UnMake). The uncertainty in the estimate could probably be taken care of by an insignificant increase of the MARGIN. In that case "static null-move pruning" would simply be a very inefficient implementation of futility pruning.

MahmoudUthman
Posts: 229
Joined: Sat Jan 17, 2015 10:54 pm

Re: Futility pruning ?

Post by MahmoudUthman » Mon Mar 06, 2017 12:17 am

mjlef wrote:
MahmoudUthman wrote:
cetormenter wrote:

Code: Select all

for &#40;move &#58; moveList&#41;
&#123;
   if &#40;Depth < FUTILITY_DEPTH && !inCheck && searchedMoves > 1 && !IsInteresting&#40;move&#41; && eval + FUTILITY_MARGIN < Alpha&#41;
      continue;

   //Rest of moveloop goes here

&#125;;
More detailed information can be found on the programming wiki https://chessprogramming.wikispaces.com ... ty+Pruning.

The main considerations for futility pruning is what goes into the IsInteresting function.
thank you , but what about this code in sf despite having an equivalent to the above in it's move loop ?

Code: Select all

// Step 7. Futility pruning&#58; child node &#40;skipped when in check&#41;
    if (   !rootNode
        &&  depth < 7 * ONE_PLY
        &&  eval - futility_margin&#40;depth&#41; >= beta
        &&  eval < VALUE_KNOWN_WIN  // Do not return unproven wins
        &&  pos.non_pawn_material&#40;pos.side_to_move&#40;)))
        return eval;
In this case, SF is doing this after the evaluation which they do above the move loop. They compare against bet, with the assumption that if the current side's is far ahead of beta, then they likely have at least one move that would, if searched, fail high (return a score >=beta). This fails in zugzwang positions, of course. Many programs call this "static null move pruning", since it is a bit like null move in that is needs a score above beta, and assume the right to move generally has some value.

There is another section of code in Stockfish inside the move loop that is more like traditional futility pruning. Since this is done before making the move and doing a full evaluation, the margins used are normally bigger, since the eval before making a move is not so good at predicting if after. I believe they do not do futility pruning if the move is a capture and some other conditions. They compare against alpha, and prune score too low instead of too high.

A third futility pruning is used in many programs in the qsearch which is used even in captures. If your eval was say -500 centipawns, and program is considering searching a pawn capture (lets say pawn is not passed and worth 100 centipawn), and lets say alpha is 0, then you can prune this move (as long as it say is not a check if you are in the check including parts of your qsearch).

Mark
Thank you , I tried it today but lost ~80 points , Is it not supposed to be used in PV nodes ? "by the way I don't do null moves in PV nodes"
hgm wrote:This "static null-move pruning" is basically futility pruning that could have been done in the parent node, but based on the exact evaluation (for which you have to make the move first) rather than an estimate. Usually futility pruning uses the current evaluation plus the estimated gain by the move to be pruned, like

Code: Select all

if&#40;currentEval + MaterialCaptured&#40;move&#41; < alpha - MARGIN&#41; continue; // prune move
In the daughter (after making 'move') that condition would look like

Code: Select all

if&#40;-&#40;parentEval + MaterialCaptured&#40;lastMove&#41;) > beta + MARGIN&#41; return;   // prune node
So the difference is that it uses currentEval instead of -(parentEval + materialCaptured(lastMove)). As the margin is rather large, the importance of very precisely knowing the current eval is questionable. While it is beyond question that it takes a lot of extra work (MakeMove + Evaluate + UnMake). The uncertainty in the estimate could probably be taken care of by an insignificant increase of the MARGIN. In that case "static null-move pruning" would simply be a very inefficient implementation of futility pruning.
Thank you , I understand your point about efficiency but wouldn't this be the case only if it was the first thing tried in the child node ? instead you probe the TT or TB first for cuts which should produce much accurate results in addition to providing a cheap eval most of the time ?

Post Reply