Page 1 of 2
Futility Pruning
Posted: Tue Oct 11, 2016 4:21 pm
by 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?
Re: Futility Pruning
Posted: Tue Oct 11, 2016 5:47 pm
by Sven
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 (staticEval + materialGain + margin <= alpha) 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)".
Re: Futility Pruning
Posted: Tue Oct 11, 2016 6:04 pm
by 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.
Re: Futility Pruning
Posted: Tue Oct 11, 2016 6:40 pm
by theturk1234
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
Posted: Tue Oct 11, 2016 6:51 pm
by Sven
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.
Re: Futility Pruning
Posted: Tue Oct 11, 2016 7:33 pm
by theturk1234
Ok, makes sense.
Re: Futility Pruning
Posted: Wed Oct 12, 2016 3:37 pm
by 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 (depthLeft == 1 && staticEval + materialGain + margin <= alpha && !sd -> s -> isKingUnderAttack(co) && abs(alpha) < value_checkmate_min) {
sd -> s -> undoMove();
continue; // skip move
}
}
(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
Re: Futility Pruning
Posted: Wed Oct 12, 2016 3:59 pm
by theturk1234
Thanks!
I'll see if it works.
Re: Futility Pruning
Posted: Wed Oct 12, 2016 7:19 pm
by 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.
Re: Futility Pruning
Posted: Wed Oct 12, 2016 8:09 pm
by 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.