Page 1 of 2
Reverse Futility Pruning
Posted: Fri Dec 02, 2011 5:22 pm
by ZirconiumX
Reverse Futility Pruning is the reverse of futility pruning.
Code: Select all
if (depth == 1 &&
Eval() - VALUE_BISHOP > beta)
return beta;
if (depth == 2 &&
Eval() - VALUE_ROOK > beta)
return beta;
if (depth == 3 &&
Eval() - VALUE_QUEEN > beta)
depth--;
As you can see, it basically checks if we can fail-high earlier at a cut-node rather than fail-low earlier at an all-node.
It works for me - what do you think?
Matthew:out
Re: Reverse Futility Pruning
Posted: Fri Dec 02, 2011 5:44 pm
by Don
ZirconiumX wrote:Reverse Futility Pruning is the reverse of futility pruning.
Code: Select all
if (depth == 1 &&
Eval() - VALUE_BISHOP > beta)
return beta;
if (depth == 2 &&
Eval() - VALUE_ROOK > beta)
return beta;
if (depth == 3 &&
Eval() - VALUE_QUEEN > beta)
depth--;
As you can see, it basically checks if we can fail-high earlier at a cut-node rather than fail-low earlier at an all-node.
It works for me - what do you think?
Matthew:out
This is already done in Komodo and I think in most of the other top programs. It's a special case of null move pruning but without the "null move" part
It essentially says, if your score is so good you can take a big hit and still get the beta cutoff, go for it. Null move pruning is the same idea but the "big hit" you take is that if the score is so good you can give the opponent 2 moves in a row and still be happy, then take the cutoff.
Re: Reverse Futility Pruning
Posted: Fri Dec 02, 2011 7:33 pm
by zamar
ZirconiumX wrote:Reverse Futility Pruning is the reverse of futility pruning.
Code: Select all
if (depth == 1 &&
Eval() - VALUE_BISHOP > beta)
return beta;
if (depth == 2 &&
Eval() - VALUE_ROOK > beta)
return beta;
if (depth == 3 &&
Eval() - VALUE_QUEEN > beta)
depth--;
As you can see, it basically checks if we can fail-high earlier at a cut-node rather than fail-low earlier at an all-node.
It works for me - what do you think?
Matthew:out
In Stockfish this is called "static null move pruning"
Re: Reverse Futility Pruning
Posted: Sun Dec 04, 2011 1:21 pm
by lucasart
ZirconiumX wrote:Reverse Futility Pruning is the reverse of futility pruning.
Code: Select all
if (depth == 1 &&
Eval() - VALUE_BISHOP > beta)
return beta;
if (depth == 2 &&
Eval() - VALUE_ROOK > beta)
return beta;
if (depth == 3 &&
Eval() - VALUE_QUEEN > beta)
depth--;
As you can see, it basically checks if we can fail-high earlier at a cut-node rather than fail-low earlier at an all-node.
It works for me - what do you think?
Matthew:out
I don't have the answer to this question but: should you return beta or the eval ?
Seems logical to me to return eval() instead of beta. it's more consistent with Null Move pruning.
Also I'd recomment doing this:
* only at non PV nodes
* only when beta is not a mate score
Re: Reverse Futility Pruning
Posted: Sun Dec 04, 2011 2:36 pm
by Michel
should you return beta or the eval ?
In fail hard you should return beta. In fail soft conventional wisdom dictated you should return eval-margin.
However that may be too pessimistic. So you could also decide to
return something in between eval-margin and eval.
Re: Reverse Futility Pruning
Posted: Sun Dec 04, 2011 2:38 pm
by hgm
Michel wrote:However that may be too pessimistic. So you could also decide to
return something in between eval-margin and eval.
If you can afford that, you should have set margin smaller...
What you propose causes inconsistency when you get a hash hit on that same position later, with higher beta. It would behave as if the margin is smaller than anyway.
Re: Reverse Futility Pruning
Posted: Sun Dec 04, 2011 2:42 pm
by Michel
If you can afford that, you should have set margin smaller...
It seems to me that there is a distinction between taking a cutoff (a drastic decision) and making a statistical guess at a good evaluation bound.
It seems to work in GnuChess but I have to retest it.
Re: Reverse Futility Pruning
Posted: Sun Dec 04, 2011 2:57 pm
by lucasart
Michel wrote:If you can afford that, you should have set margin smaller...
It seems to me that there is a distinction between taking a cutoff (a drastic decision) and making a statistical guess at a good evaluation bound.
It seems to work in GnuChess but I have to retest it.
I'm currently testing the following implementation in DoubleCheck:
Code: Select all
// Static Null move pruning (ie. inverted futility pruning)
if (UseNull && !is_pv && depth <= 3
&& !in_check
&& !is_mate_score(beta)) {
if (depth == 1 && current_eval-MN >= beta)
return current_eval;
else if (depth == 2 && current_eval-MR >= beta)
return current_eval;
else if (depth == 3 && current_eval-MQ >= beta)
depth--;
}
It's too early to say, but so far it seems this improvement is quite useless.
When the test finishes, I'll try to return eval-margin, as suggested by Michel. From what I saw in StockFish, returniing eval instead of eval - margin was supposedly better (it's somewhere in a comment on the razoring code in SF). But all that's very hocus-pocus and unproven, so I guess the only right way is the one that works
PS: I don't think this idea is any novelty. I saw it in the first versions of Toga, and I'm sure Thomas Gaksh didn't invent anything and it was already tested in Crafty years ago
Re: Reverse Futility Pruning
Posted: Sun Dec 04, 2011 3:01 pm
by Michel
What you propose causes inconsistency when you get a hash hit on that same position later, with higher beta. It would behave as if the margin is smaller than anyway.
That's a nice point! Only testing can show whether this "inconsistency" is really a problem.
Re: Reverse Futility Pruning
Posted: Sun Dec 04, 2011 3:04 pm
by hgm
Michel wrote:It seems to me that there is a distinction between taking a cutoff (a drastic decision) and making a statistical guess at a good evaluation bound.
The problem is that that statistical guess will later, when you encounter that position again, (or a parent to which the score propagated), and find the guess in the hash table, be used to take again that same drastic decision.
In fact the guess will never be used for anything else. Being a bound, it could never propagate to the root, or become the score of a PV node.