| View previous topic :: View next topic |
| Author |
Message |
Vincent Diepeveen
Joined: 09 Mar 2006
Posts: 1738
Location: The Netherlands
|
 Post subject: Re: How to get futility pruning to work? Posted: Thu Mar 08, 2012 7:04 am |
  |
|
| Don wrote: |
| micron wrote: |
My (2600 Elo) engine distressingly fails to gain from futility pruning.
| Code: |
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;
}
MakeMove();
Search();
...
} |
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. |
|
| Back to top |
|
 |
|
| Subject |
Author |
Date/Time |
 How to get futility pruning to work? |
Robert Purves |
Mon Mar 05, 2012 5:16 am |
| Re: How to get futility pruning to work? |
Ferdinand Mosca |
Mon Mar 05, 2012 6:24 am |
| Re: How to get futility pruning to work? |
Don Dailey |
Mon Mar 05, 2012 1:52 pm |
| Re: How to get futility pruning to work? |
Robert Purves |
Mon Mar 05, 2012 10:16 pm |
| Re: How to get futility pruning to work? |
Don Dailey |
Mon Mar 05, 2012 10:42 pm |
| Re: How to get futility pruning to work? |
Robert Purves |
Wed Mar 07, 2012 11:40 pm |
| Re: How to get futility pruning to work? |
Ferdinand Mosca |
Thu Mar 08, 2012 4:30 am |
| Re: How to get futility pruning to work? |
Robert Purves |
Thu Mar 08, 2012 8:55 am |
| Re: How to get futility pruning to work? |
Ferdinand Mosca |
Thu Mar 08, 2012 4:36 am |
| Re: How to get futility pruning to work? |
Vincent Diepeveen |
Thu Mar 08, 2012 7:04 am |
| Re: How to get futility pruning to work? |
Robert Purves |
Sat Mar 10, 2012 12:38 am |
| Re: How to get futility pruning to work? |
Vincent Diepeveen |
Sun Mar 11, 2012 4:14 am |
| Re: How to get futility pruning to work? |
Vincent Diepeveen |
Sun Mar 11, 2012 4:41 am |
| Re: How to get futility pruning to work? |
Vincent Diepeveen |
Sun Mar 11, 2012 5:01 pm |
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
