How to get futility pruning to work?

[micron]

My (2600 Elo) engine distressingly fails to gain from futility pruning.

Code: Select all

ev = NOT_EVALUATED;
for_each_move {
  if ( !pvNode && depth == 1 && !inCheck && move_is_not_the_first && move_is_quiet ) {
    if ( ev == NOT_EVALUATED ) ev = EvalForPrune();
    if ( ev + FUTILITY_MARGIN < alpha ) continue;
  &#125;
  MakeMove&#40;);
  Search&#40;);
  ...
&#125;

Numerous tests, with different values of FUTILITY_MARGIN, different meanings of move_is_quiet, and different implementations of EvalForPrune(), have gone nowhere.
I would be grateful for hints, tips or suggestions as to what may be wrong.

Robert P.

[Ferdy]

My (2600 Elo) engine distressingly fails to gain from futility pruning.

Code: Select all

ev = NOT_EVALUATED;
for_each_move {
  if ( !pvNode && depth == 1 && !inCheck && move_is_not_the_first && move_is_quiet ) {
    if ( ev == NOT_EVALUATED ) ev = EvalForPrune();
    if ( ev + FUTILITY_MARGIN < alpha ) continue;
  &#125;
  MakeMove&#40;);
  Search&#40;);
  ...
&#125;

Numerous tests, with different values of FUTILITY_MARGIN, different meanings of move_is_quiet, and different implementations of EvalForPrune(), have gone nowhere.
I would be grateful for hints, tips or suggestions as to what may be wrong.

Robert P.

Try to mix in the following.
* use depth <= 8 or maybe <= 3
* do not prune if the move checks opp king
* do not prune killer moves
* do not prune hash move
* do not prune when your score is a mate score already
* do not prune when your piece material (pawn not included)
is lower than rook value
* do not prune when opp pieces and pawns are not capable to mate you
* legal_move >= 8
* capture_legal_move >= 2
* do not prune moves with high beta cut-off
* scale futility margin by depth and/or legal_move and/or eval value
and/or material of opponents and /or your material
* do not prune moves when legal_moves are low
* encourage to prune moves that allows opp to capture it freely (like moves with bad see() for capture moves)
* do not prune pawn moves that are somewhat tactical in nature like pushing passers, pushing candidate passers to 6th ranks and pushing pawns to attack opp king
* do not prune moves that blocked opp passer
* create some form of limiting this prunning when your iteration scores
experienced many fail lows
* do not prune king moves when there are many checks from opponents some moves ago in game history

The eval_for_prune is supposed to be a side effect when doing null move prunning in some system like.

full_eval = eval();
//do nmp
if(good_to_null and full_eval >= beta){
...
}

eval_for_prune = full_eval;

[Don]

My (2600 Elo) engine distressingly fails to gain from futility pruning.

Code: Select all

ev = NOT_EVALUATED;
for_each_move {
  if ( !pvNode && depth == 1 && !inCheck && move_is_not_the_first && move_is_quiet ) {
    if ( ev == NOT_EVALUATED ) ev = EvalForPrune();
    if ( ev + FUTILITY_MARGIN < alpha ) continue;
  &#125;
  MakeMove&#40;);
  Search&#40;);
  ...
&#125;

Numerous tests, with different values of FUTILITY_MARGIN, different meanings of move_is_quiet, and different implementations of EvalForPrune(), have gone nowhere.
I would be grateful for hints, tips or suggestions as to what may be wrong.

Robert P.

Robert,

First of all, how does this do at fixed depth searches? What you need to know is two basic things, how much it's impacting speed and also how much it's impacting ELO. If your implementation is correct there should be almost no impact on ELO and you should get a speedup.

If it's impacting ELO then there is a bug or your margin is too small. If it's simply not giving much of a speedup it's probably because you need to have a special capture and check generator to save the overhead of generating all the moves when you know you have a futility condition. Are you executing the moves to test if they are check moves and/or quiet moves? That takes time too for a move you are going to discard.

Take this one step at a time and figure out if your implementation is safe.

You should be able to do at least 3 ply of this, perhaps more if you use appropriate margins. However keep in mind that all pruning interacts with other pruning. What other type of pruning do you do if any on the last ply?

[micron]

@Ferdinand:
Thank you for a thought-provoking and comprehensive set of tips. You give 'futility reasons' and 'late move reasons' for pruning or not pruning. Right now I want to work on plain futility. Assuming some measure of success, I will surely want to add LMP later.

@Don:
I get a modest improvement (15 to 25%) in time-to-depth. There is no impact on Elo (unless I use crazy values or pruning conditions). I am glad to know that, for you, these results are to be expected.
The only other pruning in my engine is at 'node level' (before move generation), where I have static null move pruning and razoring. Turning these off has no influence on futility pruning (which remains stubbornly 0 Elo).

Both of you recommend pruning deeper than at depth == 1, and that's what I'll investigate next.

Another uncertainty is whether to Make() every move before deciding on pruning (so that a check would be non-prunable). Should this time-consuming test be done always, never or only under certain conditions?

[Don]

@Ferdinand:
Thank you for a thought-provoking and comprehensive set of tips. You give 'futility reasons' and 'late move reasons' for pruning or not pruning. Right now I want to work on plain futility. Assuming some measure of success, I will surely want to add LMP later.

@Don:
I get a modest improvement (15 to 25%) in time-to-depth. There is no impact on Elo (unless I use crazy values or pruning conditions). I am glad to know that, for you, these results are to be expected.
The only other pruning in my engine is at 'node level' (before move generation), where I have static null move pruning and razoring. Turning these off has no influence on futility pruning (which remains stubbornly 0 Elo).

Both of you recommend pruning deeper than at depth == 1, and that's what I'll investigate next.

Another uncertainty is whether to Make() every move before deciding on pruning (so that a check would be non-prunable). Should this time-consuming test be done always, never or only under certain conditions?

I don't see any problem if you are getting 15-25 percent speedup with no ELO loss.

You must never prune checks when doing futility (unless you really know what you are doing) - you either need to test a move for check before it's made or build a special capture and check only generator. If you have to make every move just to test for check it's going to impact your speed a lot. I think you can get more than 15% out of this if you do it better but right now you should be happy - it's working. At deeper levels the impact of making all the moves of course is much less, but on the last ply it's a lot.

You do not need to exclude the first move from futility pruning, that might kill some speed too. If there are no captures or checks you should just be able to quit - return the evaluation score so it's treated as a bound and make sure there is code to make sure you don't return a stalemate (because there were no "legal" moves.)

Don

[micron]

More careful measurements of time-to-depth (in many positions) showed only a pathetic 3-5% speedup by my pruning, not the 15-25% claimed earlier. Duh, no wonder I couldn't get any Elo advantage from pruning, whose primary purpose is to reduce ttd significantly.

I've written a new function IsMoveCheck(), which is 3x faster than making the move and then testing for check.

You must never prune checks when doing futility (unless you really know what you are doing)

Thank you, that's very clear.

With these improvements, I now get a definite increase in playing strength due to futility pruning. Wahoo! It's not many Elo, but tuning the margins should help. Then it will be time to try late-move pruning as well.

[Ferdy]

More careful measurements of time-to-depth (in many positions) showed only a pathetic 3-5% speedup by my pruning, not the 15-25% claimed earlier. Duh, no wonder I couldn't get any Elo advantage from pruning, whose primary purpose is to reduce ttd significantly.

I've written a new function IsMoveCheck(), which is 3x faster than making the move and then testing for check.

You must never prune checks when doing futility (unless you really know what you are doing)

Thank you, that's very clear.

With these improvements, I now get a definite increase in playing strength due to futility pruning. Wahoo! It's not many Elo, but tuning the margins should help. Then it will be time to try late-move pruning as well.

More careful measurements of time-to-depth (in many positions) showed only a pathetic 3-5% speedup by my pruning, not the 15-25% claimed earlier. Duh, no wonder I couldn't get any Elo advantage from pruning, whose primary purpose is to reduce ttd significantly.

I am trying to implement some bitboard routines in my engine, and have difficulty figuring out if ttd is a good measure for improvement, though I eventually test it in real games. What specific position should one choose for doing some initial test to measure ttd? Would it be better also to add number of solutions solved? assuming that ttd is very close, by say selecting those positions where the best move has +score and the second best move has -score.

[Ferdy]

You do not need to exclude the first move from futility pruning, that might kill some speed too. If there are no captures or checks you should just be able to quit - return the evaluation score so it's treated as a bound and make sure there is code to make sure you don't return a stalemate (because there were no "legal" moves.)

Thanks Don this is interesting I will try this.

[diep]

My (2600 Elo) engine distressingly fails to gain from futility pruning.

Code: Select all

ev = NOT_EVALUATED;
for_each_move {
  if ( !pvNode && depth == 1 && !inCheck && move_is_not_the_first && move_is_quiet ) {
    if ( ev == NOT_EVALUATED ) ev = EvalForPrune();
    if ( ev + FUTILITY_MARGIN < alpha ) continue;
  &#125;
  MakeMove&#40;);
  Search&#40;);
  ...
&#125;

Numerous tests, with different values of FUTILITY_MARGIN, different meanings of move_is_quiet, and different implementations of EvalForPrune(), have gone nowhere.
I would be grateful for hints, tips or suggestions as to what may be wrong.

Robert P.

Robert,

First of all, how does this do at fixed depth searches? What you need to know is two basic things, how much it's impacting speed and also how much it's impacting ELO. If your implementation is correct there should be almost no impact on ELO and you should get a speedup.

If it's impacting ELO then there is a bug or your margin is too small. If it's simply not giving much of a speedup it's probably because you need to have a special capture and check generator to save the overhead of generating all the moves when you know you have a futility condition. Are you executing the moves to test if they are check moves and/or quiet moves? That takes time too for a move you are going to discard.

Take this one step at a time and figure out if your implementation is safe.

You should be able to do at least 3 ply of this, perhaps more if you use appropriate margins. However keep in mind that all pruning interacts with other pruning. What other type of pruning do you do if any on the last ply?

?????

Futility pruning is highly risky. If you test it well it will for most programs not work at decent time controls of course as compared to other forward pruning methods which prune more and better.

Yet the amount of system time you have in each program will determine what works best for you.

In diep for example futility doesn't work despite intensive testing in 100 different manners. A number of reasons can be given.

a) nullmove pruning last few plies already works magnificent and is a lot less risky, furthermore i store that in transpositiontable as well (the qsearch) which obviously means that for a number of plies i get the result for near free, as opposed to programs that do not hash

b) futility pruning isn't correcting diep's evaluation function as much as the full huge evaluation function of diep; factual a few primitive rules total overrule the sophisticated knowledge in evaluation.

c) it's tactical a lot weaker to use futility pruning for Diep - difference is that Diep needs a few ply more for many tactical problems - i've posted in past also methods which tactical work way better yet also positional didn't break even

For futility pruning basically you can easily prove that one needs really lots of chessknowledge in the futlity decision taking proces in case of Diep - in Diep i just can't afford doing that - besides huge work - it's not gonna break even of course.

That said the disclaimer is i speak about last 3 plies now of course. If you want to do logics just for the last ply that is another discussion obviously.

[micron]

I am trying to implement some bitboard routines in my engine, and have difficulty figuring out if ttd is a good measure for improvement, though I eventually test it in real games. What specific position should one choose for doing some initial test to measure ttd?

One position is no good. Some or all of the PV will likely be different with and without pruning, and the time to a particular depth is on occasion actually increased by pruning.
What I did was to measure the time for all 300 WAC.epd problems at fixed depth, to get a broader picture. The number of correct solutions was not much affected by pruning.