Reverse Futility Pruning

[Michel]

and find the guess in the hash table, be used to take again that same drastic decision.

Well as said it has to be tested. It was already pointed out that testing in Stockfish showed it was beneficial not to return eval-margin in some cases.

Perhaps it has to do with returning to the same position at different depths (futility margins depend on depth).

It is on my test queue for GnuChess.

[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 (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

Actually as the number of games increases, it seems the improvement is significant. Nothing huge, but it *is* significant.

[hgm]

Perhaps it has to do with returning to the same position at different depths (futility margins depend on depth).

That could very well be, but that still means the margins are not optimally chosen as a function of depth. Returning another value than
eval - margin will effectively cause another margin to be used next time you encounter the node. If that is on average better, it should also be better to use that margin now. And the effect of using it now should be much larger than using it on the next hash hit (which might never come).

I remember now I encountered something similar with depth bootstrapping. At some point I had the choice of considering a QS node that returned eval (through stand-pat) a d=1 node returning eval - margin1, because in such a node all non-captures would be futile. So it was a trade-off between storing it with better depth, or with better score. Turned out this made a significant difference in the tree size! Unfortunately I have forgotten which was better. (I guess I should look in the Spartacus code what I am doing now...)

It might be something similar here: to make a score at high depth (and thus with large margin) more useful for causing hash cuts in low-depth probes, you might have to ly about the score, and it does not hurt you because at the lower depth the margin is smaller. Of course it would hurt you for hash cuts at the same depth.

So it would be better not to make it a trade-off, but let the engine be aware of what it is doing. (i.e. if a hashed score is futility-based, and if so, what margin was used, so the prober can correct it for the margin it wants to use now.) Trade-offs hardly ever give you a huge improvement...

[ZirconiumX]

Lucas, the code provided works wonders for Magic, which won't be winning the computer chess championship any time soon. I'll experiment with returning Eval() but it goes against fail-hard theory.

Matthew:out