| 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: Sun Mar 11, 2012 4:14 am |
  |
|
| micron wrote: |
| diep wrote: |
| 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. |
Certainly I found it a difficult and unrewarding feature to implement.
First there's the speed hit (and consequent Elo loss) from deciding whether each move is prunable.
Next, there's a loss of Elo due to pruning moves that would have given a cutoff. Thanks to Don for pointing out this loss can be quantified by fixed-depth matches.
Those losses have to be more than compensated by the improvement in average time-to-depth.
Also, it's not easy to tune the futility margins, partly because of the shape of the curve, but chiefly because the peak is Not Very Many Elo High.
| Code: |
Elo + +
+ +
0 - - + - - - + - - - - - - - -
+ + + + + + + + + +
+
+
FUTILITY_MARGIN
|
| diep wrote: |
| For futility pruning basically you can easily prove that one needs really lots of chessknowledge in the futlity decision |
Yes, indeed. Really intelligent pruning would allow the margins to be set lower, thus improving time-to-depth. There's a limit on what you can do; preventing, for instance, forks from being pruned would be nice but too complicated and time-consuming.
I have two bitboards (myAttacksTo and oppAttacksTo) with which some pruning decisions can be made a little more intelligent. Even so, futility currently gives me no more than 20 Elo. |
You should initially not focus upon techniques like futility. First of all futility is dead old. Somewhere years 70 and 80s, just like razoring. Just its name isn't old.
An important problem seems to be having a well tuned evaluation function near the leaves.
If the tuning of the evaluation function is far superior to the chessknowledge represented, then you can of course take more risks; on other hand if your evaluation function has more knowledge than the tuning supports, the correction last few plies is far more important.
That said i do believe that last few plies it should be possible on paper to bigtime reduce the search tree.
Please note that nullmove focuses upon nodes >= beta, which is a far stronger assumption than skipping moves that are just a few tenths of a pawn to be expected below alpha.
With a huge evaluation function you simply cannot predict this to be the case prior to evaluating the position. Now in the Rybka(and derivates like houdini)/Stockfish type engines, there simply won't be huge bonuses around the corner, as it simply has hardly knowledge. So it's easier to get to work such techniques then.
Yet realize that basically search is getting used more as a 'mainline checking instrument' for them; that implies passive play of course, as you need knowledge to know how to attack and without the required knowledge you easily mistake there, which is the reason why Houdini is 'outdoing' its own more agressive tuned predecessor Rybka.
This is all so tuned to each other, not deliberate, but by means of testing, that you shouldn't fall in that trap there to assume that what works for them works for you. It's different engine to engine and all can be explained.
Please realize very careful that search is having all engines play more accurate when you search deeper, but if you look careful it doesn't give as much elo per ply to the beancounter engines, for the reason they don't have much knowledge inside.
An engine like Diep when a tad more bugs get out scales elowise much better in elo per won ply. Yet winning plies works in a different manner from what works for the above engines.
I'll get it to work when i do some effort for it 
Yet futility isn't gonna work of course and anything similar to it is not what i intend to experiment with. One of the things i do want to experiment with more is to get a cheaper cutoff if i'm above beta a lot and we have a few plies to go. Say under or equal to a ply or 5.
The safe thing is doing a nullmove there, which in case of depth <= 4 for Diep results in calling qsearch for the other guy there.
Yet that loses on average 7 nodes to Diep, whereas 90%+ of the positions where we nullmove there the evaluation is over 3 pawns above beta.
Still a lot cheaper than a full search, yet the above engines solve it by hard razoring at 1 pawn above beta - cheapest thing possible - they simply do not have the system time to do anything more fancy there and this works well for them - yet that doesn't work for Diep so well - so i have to do a tad more there, but also will pick up more tactics then than the cheap razoring engines of course; it does give a total different search tree though.
Right now all what i tried there (especially experiments from 2005, where i put in again a lot of work to get this to work and failed) failed so far. |
|
| 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
