Futility Pruning

[theturk1234]

Hi guys,

I'm trying to add futility pruning to my engine. It seems to be a regression though. I'm guessing that I don't understand it fully.
Could you give me the theory behind it and an example of practical application?
Right now I'm simply checking if I'm at a frontier node, and if so I test for the static eval of the position + 200 cp >= alpha. If this is false, I return alpha.

Am I doing something wrong?

[Sven]

Hi guys,

I'm trying to add futility pruning to my engine. It seems to be a regression though. I'm guessing that I don't understand it fully.
Could you give me the theory behind it and an example of practical application?
Right now I'm simply checking if I'm at a frontier node, and if so I test for the static eval of the position + 200 cp >= alpha. If this is false, I return alpha.

Am I doing something wrong?

As described in CPW, you want to avoid searching futile moves. You can do this either within the move loop (i.e., before making a specific move) or at the top of a node (i.e., after making the move). In the first case your futility condition would look like:

Code: Select all

if &#40;staticEval + materialGain + margin <= alpha&#41; skip this move; // at depth==1 this means you save the QS call

while in the second case it would look like:

Code: Select all

if (staticEval - margin >= beta) return staticEval - margin; // or return beta when using fail-hard alpha-beta

"margin" is an optimistic estimate of the possible positional evaluation change caused by the move. The material evaluation change of a move needs to be considered in the first case since it can often be much bigger than the margin.

But the second case in combination with the condition "remaining depth == 1" means you are effectively pruning futile moves that were made at depth == 2.

If your condition mentioned above is applied at the top of a node then it is wrong and needs to be reversed as mentioned into "if (staticEval - margin >= beta)".

[Sven]

Please note also that applying the futility condition within the move loop at a node of remaining depth == 1 is almost redundant if you also have "lazy evaluation" since there the condition is the same, and you do the typical stand-pat cutoff in QS if staticEval >= beta.

It should also be mentioned that there are restrictions to futility pruning: do not apply it when in check, or when alpha or beta are mate scores.

[theturk1234]

Thank you Sven!
As usual you answered my question

Ok, what do you think good margin and material gain values would be?

[Sven]

Thank you Sven!
As usual you answered my question

Ok, what do you think good margin and material gain values would be?

Material gain, needed in case 1, follows directly from the move you possibly want to skip, i.e. you know exactly the gain of captures and promotions. Regarding the margin: that depends on your engine and especially your positional eval, you need to find out what works best for you. Small margin means high risk, high margin may give less or no improvement.

[theturk1234]

Ok, makes sense.

[flok]

Hi,

So something like this?

Code: Select all

if (!isCatchMove) {
        int materialGain = promoteTo != NONE ? materialGain = ChessPiece::evalVal[promoteTo] - ChessPiece::evalVal[PAWN] : 0;
        constexpr int margin = 200; // maximum non-mate eval minus max material gain

        if &#40;depthLeft == 1 && staticEval + materialGain + margin <= alpha && !sd -> s -> isKingUnderAttack&#40;co&#41; && abs&#40;alpha&#41; < value_checkmate_min&#41; &#123;
                sd -> s -> undoMove&#40;);

                continue; // skip move
        &#125;
&#125;

(with staticEval being the evaluation of the current node (calculated outside the loop), not from the node after the move)

Because that gives me a -100 elo

[theturk1234]

Thanks!

I'll see if it works.

[flok]

No please don't use my code! (not yet at least) I was merely asking the others if they think my code is correct as I see a large reduction in elo with it.

[kbhearn]

Your formula for material gain is wrong. It doesn't add in the evaluation value of your victim in the case of a capture.