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!
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
Futility pruning, Ext futility pruning and Limited Razoring.
Moderators: hgm, Rebel, chrisw
-
- Posts: 2684
- Joined: Sat Jun 14, 2008 9:17 pm
Re: Futility pruning, Ext futility pruning and Limited Razor
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.jesper_nielsen wrote: Well I tried something like the pruning done in Crafty 23.1, but it does not work for me.
...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.
-
- Posts: 56
- Joined: Sat Nov 11, 2006 11:14 pm
Re: Futility pruning, Ext futility pruning and Limited Razor
Would you mind elaborating a bit over this?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,...
Cheers, Mauro
-
- Posts: 2684
- Joined: Sat Jun 14, 2008 9:17 pm
Re: Futility pruning, Ext futility pruning and Limited Razor
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.yoshiharu wrote:Would you mind elaborating a bit over this?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,...
Cheers, Mauro
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
-
- Posts: 56
- Joined: Sat Nov 11, 2006 11:14 pm
Re: Futility pruning, Ext futility pruning and Limited Razor
Well, actually I was asking if you could say something more on *this* bit...mcostalba wrote:Well, there is not a lot to elaborate here.yoshiharu wrote:Would you mind elaborating a bit over this?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,...
Cheers, Mauro
[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
Nevermind
Cheers, Mauro
-
- Posts: 344
- Joined: Wed Sep 23, 2009 5:56 pm
- Location: Germany
Re: Futility pruning, Ext futility pruning and Limited Razor
I think these were only the upper bounds given by Heinz. His lower bounds are 200, 500 and 900 cp.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.
For me, even 150 cp for the depth=1 futility pruning seems to be best.jesper_nielsen wrote:Well halving the margins to 200, 300 and 500 gained about 19 Elo points!
Please report if you find anything.jesper_nielsen wrote:I am currently running further tests to try and find even better values.
Re: Futility pruning, Ext futility pruning and Limited Razor
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!
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.
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Futility pruning, Ext futility pruning and Limited Razor
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.mcostalba wrote: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.jesper_nielsen wrote: Well I tried something like the pruning done in Crafty 23.1, but it does not work for me.
...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.
Re: Futility pruning, Ext futility pruning and Limited Razor
Hi again!
Even bigger gain with even lower margins.
A very surprising result, to me at least.
Kind regards,
Jesper
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
Kind regards,
Jesper
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Futility pruning, Ext futility pruning and Limited Razor
Shouldn't be surprising. If you had looked at Crafty, you would find this:jesper_nielsen wrote:Hi again!
Even bigger gain with even lower margins.
A very surprising result, to me at least.Code: Select all
400, 600, 1000 => 0 Elo 200, 300, 500 => +19 Elo 100, 150, 250 => +41 Elo
Kind regards,
Jesper
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.