Futile attempts at futility pruning

[fierz]

Dear all,

I recently tried adding futility pruning to my engine, but my attempts are not working so far.

I tried a variant of futility pruning where I don't attempt to refute a move in the moves loop (because I have no information on the positional evaluation there), but rather go on into the next level of negamax, get an evaluation, and then do:

Code: Select all

if (depth < FUTILITY_DEPTH &&
		!ispv &&
		!ischeck &&
		staticeval > beta + FUTILITY_MARGIN_0 + FUTILITY_MARGIN_PLY*depth)

So I have some kind of basic threshold that (FUTILITY_MARGIN_0) needs to be exceeded, and that is linear in the remaining depth with a slope of FUTILITY_MARGIN_PLY.

I tried some settings in the vicinity of FUTILITY_MARGIN_0 100-200 centipawns and FUTILITY_MARGIN_PLY 50-100 centipawns, and did this on the last 4 plies of the search (FUTILITY_DEPTH 5) but none of this really worked, whether in test positions nor in gauntlet matches. Can anyone suggest an improvement on my code or settings?

cheers
Martin

[cdani]

Maybe you can start with FUTILITY_DEPTH 2? Just to see if it gives something.

[mar]

Code: Select all

		staticeval > beta + FUTILITY_MARGIN_0 + FUTILITY_MARGIN_PLY*depth)

I'm not sure what exactly you do, but assuming you use negamax the condition above looks odd.
(it would be ok if you used plain alphabeta for the min player though)
You want to prune moves that are unlikely to beat alpha, so you want either

Code: Select all

staticeval + margin < beta

or

Code: Select all

staticeval < beta - margin

(assuming scout nodes)

[fierz]

Code: Select all

		staticeval > beta + FUTILITY_MARGIN_0 + FUTILITY_MARGIN_PLY*depth)

I'm not sure what exactly you do, but assuming you use negamax the condition above looks odd.
(it would be ok if you used plain alphabeta for the min player though)
You want to prune moves that are unlikely to beat alpha, so you want either

Code: Select all

staticeval + margin < beta

or

Code: Select all

staticeval < beta - margin

(assuming scout nodes)

Hi Martin,

I'm using the "reverse" version of futility pruning (https://chessprogramming.wikispaces.com ... ty+Pruning) which seems more natural to me as it includes a full evaluation; which is why the condition is sort of the wrong way around. But I guess it shouldn't really matter which version is being used!?

cheers
Martin

[mar]

Hi Martin,

I'm using the "reverse" version of futility pruning (https://chessprogramming.wikispaces.com ... ty+Pruning) which seems more natural to me as it includes a full evaluation; which is why the condition is sort of the wrong way around. But I guess it shouldn't really matter which version is being used!?

cheers
Martin

Ah, I see.
I think the term reverse futility is unfortunate and confusing, however as I understand there's no consensus.
This is certainly very different from "standard" futility pruning though.
The point in this case is that you bet that the eval is so good that you'd get a beta cutoff regardless.
I got a nice gain by doing this so I wonder why it doesn't work for you.

[flok]

I'm also still failing.

In the beginning of search I do:

Code: Select all

        bool allowFutilityPruning = false;
        if (!isCheck) { 
                int score = evaluate(c);

                allowFutilityPruning = score + calcFutilityMargin(sd -> s, c) < alpha;
        }

and then in the move-loop in that search function:

Code: Select all

if (allowFutilityPruning && !move.isCatch && !move.isPromote)
    continue; // skip move

And the calcFutilityMargin() is something that finds the opponent-piece with the highest eval. So if the opponent still has a queen, then it picks 975. If only a pawn is left (and the king of course), then it picks 100. And then it also adds 3 x 16 points for mobility (assuming here that after a move the opponent can do at max. 16 moves more than before), 15 points for passed pawns and 15 for positional increase.

[Henk]

Is there any proof that futility pruning gives an ELO gain. Or does it only give an ELO profit if an engine has a slow evaluation with an inferior LMR implementation.

[flok]

Ok I changed the code a bit. Instead of just assuming that the piece with the highest evaluation can indeed be catched, I now check which pieces are under attack and then pick the one with the highest eval. For depth 7, 242 nodes (out of 161650 nodes) can then do futility pruning and 5.2% of the moves checked are pruned.

[Stan Arts]

How is it not working? Not saving nodes/time at all?

When you are pruning at the leafs by static eval + margin above beta that's basically the same as futility pruning at the leafs - 1 ply.
Probably want to do something at the leafs when you are way below alpha too such as generating just tactical moves to save some makemoves and evaluations because Qsearch stand pat will statically cut off futile nodes next ply where most of the savings with relative low risk comes from then.

In Nemeton I do both. If at the leafs I'm way over beta and no clear statical threat (mainly pawns on the 7th with the promotionsquare not propperly defended) I give a cutoff and when I'm way below alpha I skip quiet moves.
But it's just for my own piece of mind as in general it just takes the edge off of nodes for me saving say, 10-20% max. It also introduces some errors (mainly that deep futility pruning) in the sense that you aren't finding some sneaky threatening move. Say I move my queen somewhere that lets me grab a rook or give checkmate in 1 next turn but this quiet move seems statically futile. But I don't care about that because it works the vast majority of the time and less nodes is better right. Hm.

[flok]

Yes it was not cutting of anything at all. The current version does (see my previous post). Am now running a test on the cluster so tomorrow I know if it helps!