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?
Futility Pruning
Moderators: hgm, Rebel, chrisw
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Futility Pruning
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: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?
Code: Select all
if (staticEval + materialGain + margin <= alpha) skip this move; // at depth==1 this means you save the QS call
Code: Select all
if (staticEval - margin >= beta) return staticEval - margin; // or return beta when using fail-hard alpha-beta
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)".
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Futility Pruning
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.
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.
-
- Posts: 52
- Joined: Tue Jul 12, 2016 5:28 am
Re: Futility Pruning
Thank you Sven!
As usual you answered my question
Ok, what do you think good margin and material gain values would be?
As usual you answered my question
Ok, what do you think good margin and material gain values would be?
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Futility Pruning
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 wrote:Thank you Sven!
As usual you answered my question
Ok, what do you think good margin and material gain values would be?
Re: Futility Pruning
Hi,
So something like this?
(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
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 (depthLeft == 1 && staticEval + materialGain + margin <= alpha && !sd -> s -> isKingUnderAttack(co) && abs(alpha) < value_checkmate_min) {
sd -> s -> undoMove();
continue; // skip move
}
}
Because that gives me a -100 elo
-
- Posts: 52
- Joined: Tue Jul 12, 2016 5:28 am
Re: Futility Pruning
Thanks!
I'll see if it works.
I'll see if it works.
Re: Futility Pruning
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.
-
- Posts: 411
- Joined: Thu Dec 30, 2010 4:48 am
Re: Futility Pruning
Your formula for material gain is wrong. It doesn't add in the evaluation value of your victim in the case of a capture.