Futility pruning ?

[MahmoudUthman]

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]

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]

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.

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: child node (skipped when in check)
    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]

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.

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: child node (skipped when in check)
    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

[hgm]

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(-(parentEval + MaterialCaptured(lastMove)) > beta + MARGIN) 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]

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.

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: child node (skipped when in check)
    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"

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(-(parentEval + MaterialCaptured(lastMove)) > beta + MARGIN) 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 ?