Futility pruning ?
Moderators: hgm, Rebel, chrisw
-
- Posts: 234
- Joined: Sat Jan 17, 2015 11:54 pm
Futility pruning ?
could someone provide a pseudo code for the different forms of futility pruning and what are the advantages/disadvantages for one over the other ?
-
- Posts: 170
- Joined: Sun Oct 28, 2012 9:46 pm
Re: Futility pruning ?
Code: Select all
for (move : moveList)
{
if (Depth < FUTILITY_DEPTH && !inCheck && searchedMoves > 1 && !IsInteresting(move) && eval + FUTILITY_MARGIN < Alpha)
continue;
//Rest of moveloop goes here
};
The main considerations for futility pruning is what goes into the IsInteresting function.
-
- Posts: 234
- Joined: Sat Jan 17, 2015 11:54 pm
Re: Futility pruning ?
thank you , but what about this code in sf despite having an equivalent to the above in it's move loop ?cetormenter wrote:More detailed information can be found on the programming wiki https://chessprogramming.wikispaces.com ... ty+Pruning.Code: Select all
for (move : moveList) { if (Depth < FUTILITY_DEPTH && !inCheck && searchedMoves > 1 && !IsInteresting(move) && eval + FUTILITY_MARGIN < Alpha) continue; //Rest of moveloop goes here };
The main considerations for futility pruning is what goes into the IsInteresting function.
Code: Select all
// Step 7. Futility pruning: child node (skipped when in check)
if ( !rootNode
&& depth < 7 * ONE_PLY
&& eval - futility_margin(depth) >= beta
&& eval < VALUE_KNOWN_WIN // Do not return unproven wins
&& pos.non_pawn_material(pos.side_to_move()))
return eval;
-
- Posts: 1494
- Joined: Thu Mar 30, 2006 2:08 pm
Re: Futility pruning ?
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.MahmoudUthman wrote:thank you , but what about this code in sf despite having an equivalent to the above in it's move loop ?cetormenter wrote:More detailed information can be found on the programming wiki https://chessprogramming.wikispaces.com ... ty+Pruning.Code: Select all
for (move : moveList) { if (Depth < FUTILITY_DEPTH && !inCheck && searchedMoves > 1 && !IsInteresting(move) && eval + FUTILITY_MARGIN < Alpha) continue; //Rest of moveloop goes here };
The main considerations for futility pruning is what goes into the IsInteresting function.Code: Select all
// Step 7. Futility pruning: child node (skipped when in check) if ( !rootNode && depth < 7 * ONE_PLY && eval - futility_margin(depth) >= beta && eval < VALUE_KNOWN_WIN // Do not return unproven wins && pos.non_pawn_material(pos.side_to_move())) return eval;
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
-
- Posts: 27808
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Futility pruning ?
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
In the daughter (after making 'move') that condition would look like
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.
Code: Select all
if(currentEval + MaterialCaptured(move) < alpha - MARGIN) continue; // prune move
Code: Select all
if(-(parentEval + MaterialCaptured(lastMove)) > beta + MARGIN) return; // prune node
-
- Posts: 234
- Joined: Sat Jan 17, 2015 11:54 pm
Re: Futility pruning ?
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"mjlef wrote: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.MahmoudUthman wrote:thank you , but what about this code in sf despite having an equivalent to the above in it's move loop ?cetormenter wrote:More detailed information can be found on the programming wiki https://chessprogramming.wikispaces.com ... ty+Pruning.Code: Select all
for (move : moveList) { if (Depth < FUTILITY_DEPTH && !inCheck && searchedMoves > 1 && !IsInteresting(move) && eval + FUTILITY_MARGIN < Alpha) continue; //Rest of moveloop goes here };
The main considerations for futility pruning is what goes into the IsInteresting function.Code: Select all
// Step 7. Futility pruning: child node (skipped when in check) if ( !rootNode && depth < 7 * ONE_PLY && eval - futility_margin(depth) >= beta && eval < VALUE_KNOWN_WIN // Do not return unproven wins && pos.non_pawn_material(pos.side_to_move())) return eval;
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 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 ?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
In the daughter (after making 'move') that condition would look likeCode: Select all
if(currentEval + MaterialCaptured(move) < alpha - MARGIN) continue; // prune move
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.Code: Select all
if(-(parentEval + MaterialCaptured(lastMove)) > beta + MARGIN) return; // prune node