Reverse 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.
ZirconiumX
Posts: 1327
Joined: Sun Jul 17, 2011 9:14 am

Reverse Futility Pruning

Post by ZirconiumX » Fri Dec 02, 2011 4:22 pm

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
Some believe in the almighty dollar.

I believe in the almighty printf statement.

User avatar
Don
Posts: 5106
Joined: Tue Apr 29, 2008 2:27 pm

Re: Reverse Futility Pruning

Post by Don » Fri Dec 02, 2011 4:44 pm

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.

zamar
Posts: 613
Joined: Sun Jan 18, 2009 6:03 am

Re: Reverse Futility Pruning

Post by zamar » Fri Dec 02, 2011 6:33 pm

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"
Joona Kiiski

User avatar
lucasart
Posts: 3023
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: Reverse Futility Pruning

Post by lucasart » Sun Dec 04, 2011 12:21 pm

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

Michel
Posts: 2001
Joined: Sun Sep 28, 2008 11:50 pm

Re: Reverse Futility Pruning

Post by Michel » Sun Dec 04, 2011 1:36 pm

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.

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

Re: Reverse Futility Pruning

Post by hgm » Sun Dec 04, 2011 1:38 pm

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.

Michel
Posts: 2001
Joined: Sun Sep 28, 2008 11:50 pm

Re: Reverse Futility Pruning

Post by Michel » Sun Dec 04, 2011 1:42 pm

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.

User avatar
lucasart
Posts: 3023
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: Reverse Futility Pruning

Post by lucasart » Sun Dec 04, 2011 1:57 pm

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 &#40;UseNull && !is_pv && depth <= 3
		&& !in_check
		&& !is_mate_score&#40;beta&#41;) &#123;
		if &#40;depth == 1 && current_eval-MN >= beta&#41;
			return current_eval;
		else if &#40;depth == 2 && current_eval-MR >= beta&#41;
			return current_eval;
		else if &#40;depth == 3 && current_eval-MQ >= beta&#41;
			depth--;
	&#125;
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

Michel
Posts: 2001
Joined: Sun Sep 28, 2008 11:50 pm

Re: Reverse Futility Pruning

Post by Michel » Sun Dec 04, 2011 2:01 pm

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.

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

Re: Reverse Futility Pruning

Post by hgm » Sun Dec 04, 2011 2:04 pm

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.

Post Reply