Futility pruning, Ext futility pruning and Limited Razoring.

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
jesper_nielsen

Futility pruning, Ext futility pruning and Limited Razoring.

Post by jesper_nielsen » Thu Nov 26, 2009 3:03 pm

Hi All!

I have been experimenting with the "Futility Pruning, Extended Futility Pruning and Limited Razoring", as described by Heinz(?)

It has been in my engine for a very long time.

Bob wrote something about replacing this scheme with a more general pruning technique.

Well I tried something like the pruning done in Crafty 23.1, but it does not work for me.

Then I remembered Bob mentining something about the optimal values for the pruning margins used in FP, EFP and LR were a lot lower than the recommended values given by Heinz.

The margins were 400, 600 and 1000 cp respectively, as recommended in the papers describing the techniques.

Well halving the margins to 200, 300 and 500 gained about 19 Elo points! :shock:

I am currently running further tests to try and find even better values.

So if other people are also using this pruning technique, maybe there are some easy Elo points just waiting to be gained?!

Kind regards,
Jesper

mcostalba
Posts: 2684
Joined: Sat Jun 14, 2008 7:17 pm

Re: Futility pruning, Ext futility pruning and Limited Razor

Post by mcostalba » Thu Nov 26, 2009 3:24 pm

jesper_nielsen wrote: Well I tried something like the pruning done in Crafty 23.1, but it does not work for me.
The pruning scheme _now_ used in Crafty 23.1 (that seems what pushed Crafty up in ELO), namely an array of futility margins indexed by depth is the same scheme already used by Stockfish from a long ago.


...and it works, but, as usual with futility, it works only if tuned correctly and the tuning is very dependent on the other parts of your engine, so there isn't a single tune that works for all, only the idea is the same, the coefficents values should be redisocovered for any engine inplementation.

And for people without a cluster, like we are, it takes a lot of time and effort: we have developed a very powerful way to automatically fine tune evaluation terms, but this technique simply does not work with futility where we have to rely on the old and tried (and slow) way of testing the coefficents until you find a recipe that works.

yoshiharu
Posts: 56
Joined: Sat Nov 11, 2006 10:14 pm

Re: Futility pruning, Ext futility pruning and Limited Razor

Post by yoshiharu » Thu Nov 26, 2009 3:46 pm

mcostalba wrote: And for people without a cluster, like we are, it takes a lot of time and effort: we have developed a very powerful way to automatically fine tune evaluation terms,...
Would you mind elaborating a bit over this?

Cheers, Mauro

mcostalba
Posts: 2684
Joined: Sat Jun 14, 2008 7:17 pm

Re: Futility pruning, Ext futility pruning and Limited Razor

Post by mcostalba » Thu Nov 26, 2009 4:34 pm

yoshiharu wrote:
mcostalba wrote: And for people without a cluster, like we are, it takes a lot of time and effort: we have developed a very powerful way to automatically fine tune evaluation terms,...
Would you mind elaborating a bit over this?

Cheers, Mauro
Well, there is not a lot to elaborate here. When you are able to complete 40.000 games in 2 hours time while other people needs weeks for the same task it means you have a x100 advantage in test speed. You have the luxury of avoiding to compromise between accuracy and test speed, you don't need to be smart: just press the button.

If you consider that futility parameters tuning is done (as 90% of all the other tuning) playing games with different versions of your engine you have already elaborated all.



Starting from 1.4 tuning of evaluation parameters is done in a fully automatic fashion, without any human heuristic and, main point, in reasonable times also with a standard hardware. One of us (not me) has tried to be smart because of lack of hardware and at the end he not only proved smart enough but we think that, due the way this tuning system works, it is able to achieve results qualitatively superior to traditional tuning.

We won't publish the method anyhow, well, eventually, we could bargain the tuning secret with a good cluster ;-)

yoshiharu
Posts: 56
Joined: Sat Nov 11, 2006 10:14 pm

Re: Futility pruning, Ext futility pruning and Limited Razor

Post by yoshiharu » Thu Nov 26, 2009 5:59 pm

mcostalba wrote:
yoshiharu wrote:
mcostalba wrote: And for people without a cluster, like we are, it takes a lot of time and effort: we have developed a very powerful way to automatically fine tune evaluation terms,...
Would you mind elaborating a bit over this?

Cheers, Mauro
Well, there is not a lot to elaborate here.
[snip]
Starting from 1.4 tuning of evaluation parameters is done in a fully automatic fashion,
[snip]
We won't publish the method anyhow, well, eventually, we could bargain the tuning secret with a good cluster ;-)
Well, actually I was asking if you could say something more on *this* bit...;-)
Nevermind :-)

Cheers, Mauro

metax
Posts: 344
Joined: Wed Sep 23, 2009 3:56 pm
Location: Germany

Re: Futility pruning, Ext futility pruning and Limited Razor

Post by metax » Thu Nov 26, 2009 8:35 pm

jesper_nielsen wrote:Then I remembered Bob mentining something about the optimal values for the pruning margins used in FP, EFP and LR were a lot lower than the recommended values given by Heinz.

The margins were 400, 600 and 1000 cp respectively, as recommended in the papers describing the techniques.
I think these were only the upper bounds given by Heinz. His lower bounds are 200, 500 and 900 cp.
jesper_nielsen wrote:Well halving the margins to 200, 300 and 500 gained about 19 Elo points! :shock:
For me, even 150 cp for the depth=1 futility pruning seems to be best.
jesper_nielsen wrote:I am currently running further tests to try and find even better values.
Please report if you find anything.

adieguez

Re: Futility pruning, Ext futility pruning and Limited Razor

Post by adieguez » Thu Nov 26, 2009 9:03 pm

jesper_nielsen wrote:Hi All!

I have been experimenting with the "Futility Pruning, Extended Futility Pruning and Limited Razoring", as described by Heinz(?)

It has been in my engine for a very long time.

Bob wrote something about replacing this scheme with a more general pruning technique.

Well I tried something like the pruning done in Crafty 23.1, but it does not work for me.

Then I remembered Bob mentining something about the optimal values for the pruning margins used in FP, EFP and LR were a lot lower than the recommended values given by Heinz.

The margins were 400, 600 and 1000 cp respectively, as recommended in the papers describing the techniques.

Well halving the margins to 200, 300 and 500 gained about 19 Elo points! :shock:

I am currently running further tests to try and find even better values.

So if other people are also using this pruning technique, maybe there are some easy Elo points just waiting to be gained?!

Kind regards,
Jesper[/quote

It may be the case. In amyan 1.6 I think the main improvement I got was simply because lowering the futility margins. Off course they are much lower than this as I use an eval.

bob
Posts: 20401
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Futility pruning, Ext futility pruning and Limited Razor

Post by bob » Thu Nov 26, 2009 9:21 pm

mcostalba wrote:
jesper_nielsen wrote: Well I tried something like the pruning done in Crafty 23.1, but it does not work for me.
The pruning scheme _now_ used in Crafty 23.1 (that seems what pushed Crafty up in ELO), namely an array of futility margins indexed by depth is the same scheme already used by Stockfish from a long ago.


...and it works, but, as usual with futility, it works only if tuned correctly and the tuning is very dependent on the other parts of your engine, so there isn't a single tune that works for all, only the idea is the same, the coefficents values should be redisocovered for any engine inplementation.

And for people without a cluster, like we are, it takes a lot of time and effort: we have developed a very powerful way to automatically fine tune evaluation terms, but this technique simply does not work with futility where we have to rely on the old and tried (and slow) way of testing the coefficents until you find a recipe that works.
The current pruning changes were worth +12 Elo, not a huge change. The primary change is that I no longer do futility/extended-futility/razoring at all, as those were defined at specific depths. Crafty just outright prunes in the last 4 plies of the search, and uses different pruning score thresholds depending on how far it is from the frontier (first depth=0 nodes). It took a good bit of adjusting and tuning, but the current approach is much simpler in terms of lines of code, and is a bit stronger. But only a bit, it is not world-shattering.

jesper_nielsen

Re: Futility pruning, Ext futility pruning and Limited Razor

Post by jesper_nielsen » Fri Nov 27, 2009 2:36 pm

Hi again!

Even bigger gain with even lower margins.

Code: Select all

400, 600, 1000 =>   0 Elo
200, 300, 500  => +19 Elo
100, 150, 250  => +41 Elo
A very surprising result, to me at least.

Kind regards,
Jesper

bob
Posts: 20401
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Futility pruning, Ext futility pruning and Limited Razor

Post by bob » Sat Nov 28, 2009 1:48 am

jesper_nielsen wrote:Hi again!

Even bigger gain with even lower margins.

Code: Select all

400, 600, 1000 =>   0 Elo
200, 300, 500  => +19 Elo
100, 150, 250  => +41 Elo
A very surprising result, to me at least.

Kind regards,
Jesper
Shouldn't be surprising. If you had looked at Crafty, you would find this:

125
125
300
300

(I do this in the last 4 plies, not just last 3). And I can tell you those numbers were _not_ randomly chosen. :)

Post Reply