Reverse Futility Pruning

[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

[Don]

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]

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"

[lucasart]

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]

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.

[hgm]

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]

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.

[lucasart]

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]

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.

[hgm]

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.