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.
theturk1234
Posts: 52
Joined: Tue Jul 12, 2016 3:28 am

Futility Pruning

Post by theturk1234 » Tue Oct 11, 2016 2:21 pm

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
Posts: 3753
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Futility Pruning

Post by Sven » Tue Oct 11, 2016 3:47 pm

theturk1234 wrote: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 &#40;staticEval - margin >= beta&#41; 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
Posts: 3753
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Futility Pruning

Post by Sven » Tue Oct 11, 2016 4:04 pm

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
Posts: 52
Joined: Tue Jul 12, 2016 3:28 am

Re: Futility Pruning

Post by theturk1234 » Tue Oct 11, 2016 4:40 pm

Thank you Sven!
As usual you answered my question :)

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

Sven
Posts: 3753
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Futility Pruning

Post by Sven » Tue Oct 11, 2016 4:51 pm

theturk1234 wrote: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
Posts: 52
Joined: Tue Jul 12, 2016 3:28 am

Re: Futility Pruning

Post by theturk1234 » Tue Oct 11, 2016 5:33 pm

Ok, makes sense.

flok

Re: Futility Pruning

Post by flok » Wed Oct 12, 2016 1:37 pm

Hi,

So something like this?

Code: Select all

if (!isCatchMove&#41; &#123;
        int materialGain = promoteTo != NONE ? materialGain = ChessPiece&#58;&#58;evalVal&#91;promoteTo&#93; - ChessPiece&#58;&#58;evalVal&#91;PAWN&#93; &#58; 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
Posts: 52
Joined: Tue Jul 12, 2016 3:28 am

Re: Futility Pruning

Post by theturk1234 » Wed Oct 12, 2016 1:59 pm

Thanks!

I'll see if it works.

flok

Re: Futility Pruning

Post by flok » Wed Oct 12, 2016 5:19 pm

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
Posts: 411
Joined: Thu Dec 30, 2010 3:48 am

Re: Futility Pruning

Post by kbhearn » Wed Oct 12, 2016 6:09 pm

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

Post Reply