TalkChess.com :: View topic - How to get futility pruning to work?

TalkChess.com
Hosted by Your Move Chess & Games

FAQ

Memberlist

Usergroups

Profile

How to get futility pruning to work?

TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions

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 5:01 pm

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.

note that +20 elo is a lot. For diep it's around -150 elo if i use futlility last 3 ply.

Vincent

Display posts from previous:

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

TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions

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