Futility pruning, Ext futility pruning and Limited Razoring.

[jesper_nielsen]

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

[mcostalba]

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]

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]

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]

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]

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.

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

For me, even 150 cp for the depth=1 futility pruning seems to be best.

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

Please report if you find anything.

[adieguez]

[quote="jesper_nielsen"]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.

[bob]

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]

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]

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.