history pruning/ late move pruning

[Tom King]

Hello all,

Expect a new version of Francesca to roll soon, v0.12

I've been experimenting with history pruning (also seems to be called late move pruning or late move reductions), with some promising results. It is like adding a turbo-charger to the search speed.

A basic implementation seems to give over 50 ELO, at least for Francesca. More testing needed, however!

What are others finding?

Are there any other nice programming breakthroughs of the last two years which I can consider? [you can tell I have little time for chess programming these days].

Regards,
Tom

[Stef Luijten]

Tom,
Fully agree, I think Wing has gained over 100 ELO points form adding history pruning!
Stef

[Tom King]

Tom,
Fully agree, I think Wing has gained over 100 ELO points form adding history pruning!
Stef

100 points! Wow.

This reminds me of the good ol' days when we were all figuring out null move pruning.. Christian Donniger published his paper in the ICCA journal, and suddenly everyone had an instant 200 ELO improvement (or whatever) to their program.

[Thomas Mayer]

Hi Tom,

well, for me it seems not to work... I have tried several things now, but still the resulting engine is simply weaker... But I haven't given up yet...
Experiences seem to be different. I believe e.g. in Fruit it is a big part of it's strength and same about Glaurung. The Spike team speaks in CCC of about 20 Elo improvemant whereas I know that e.g. Richard Pijl had the same experience then I had: weaker version... But I am sure he hasn't given up either...

Greets, Thomas

P.S.: I currently try to track down why I have this problem, it seems to me, that my move ordering is too bad... I have some work to do...

[Tord Romstad]

Hi Tom,

well, for me it seems not to work... I have tried several things now, but still the resulting engine is simply weaker... But I haven't given up yet...

Hi Thomas,

Do you use recapture extensions? My experience is that recapture extensions and late move reductions work very badly together. I suspect that the reason is that I never reduce captures, and that recapture extensions therefore makes the search over-emphasize sequences of captures. Even without recapture extensions, captures are (on average) searched a bit deeper than non-captures.

Fabien has the same experience with Fruit.

Tord

[H.G.Muller]

The recapture extension in isolation seems a bad idea. In my minimalistic engine, which basically had nothing else than a recapture-only QS and a recapture extension, on top of a fixed-depth full-width search, the strength in self-play increased significantly when I dropped the recapture extension and allowed equal number of nodes to be searched. (Score 66%-33%. How many ELO points is that?)

First I blamed this on my definition of recapture also including capture of the piece that moved in a non-capture: many such 'recaptures' are bad because the piece is sufficiently defended, and these bad branches are then searched to greater depth (albeit with a favorable window). But when I explicitly excluded those, I saw no difference. Distinguishing even and odd captures in a sequence (only awarding an extension to the 2nd, 4th etc. true capture to the same square) did not seem to make any difference....

[Alessandro Scotti]

(Score 66%-33%. How many ELO points is that?)

More or less 117 elo. I think I have a percentage/elo table somewhere on my computer chess page (WWW button below) but I can't connect right now to get the precise address.

[Edit] Got it!
http://www.ascotti.org/programming/chess/elo.htm

[Tom King]

Hi Tom,

well, for me it seems not to work... I have tried several things now, but still the resulting engine is simply weaker... But I haven't given up yet...
Experiences seem to be different. I believe e.g. in Fruit it is a big part of it's strength and same about Glaurung. The Spike team speaks in CCC of about 20 Elo improvemant whereas I know that e.g. Richard Pijl had the same experience then I had: weaker version... But I am sure he hasn't given up either...

Greets, Thomas

P.S.: I currently try to track down why I have this problem, it seems to me, that my move ordering is too bad... I have some work to do...

Strange that it seems to offer some programs a lot, and some very little.

Does the extra depth help programs which aren't (relatively) strong at tactics?

[Tord Romstad]

Strange that it seems to offer some programs a lot, and some very little.

Aren't most tricks like that?

Does the extra depth help programs which aren't (relatively) strong at tactics?

I think it's more complicated than that. For instance, The Baron and Glaurung are both relatively weak at tactics, but late move reductions seem to help Glaurung but not The Baron. Perhaps it tends to help more in simple and stupid programs (mine is one of those) than in more complicated and knowledge-loaded programs.

Tord

[Tony van Roon-Werten]

Strange that it seems to offer some programs a lot, and some very little.

Aren't most tricks like that?

Does the extra depth help programs which aren't (relatively) strong at tactics?

I think it's more complicated than that. For instance, The Baron and Glaurung are both relatively weak at tactics, but late move reductions seem to help Glaurung but not The Baron. Perhaps it tends to help more in simple and stupid programs (mine is one of those) than in more complicated and knowledge-loaded programs.

Tord

Not sure, it seems to help XiniX tacticly (XiniX's weak point) while not costing too much positionally (stronger point).

Though, I seem to be limitting the reductions a lot more than others.

Tony

[Tom King]

Strange that it seems to offer some programs a lot, and some very little.

Aren't most tricks like that?

Does the extra depth help programs which aren't (relatively) strong at tactics?

I think it's more complicated than that. For instance, The Baron and Glaurung are both relatively weak at tactics, but late move reductions seem to help Glaurung but not The Baron. Perhaps it tends to help more in simple and stupid programs (mine is one of those) than in more complicated and knowledge-loaded programs.

Tord

Not sure, it seems to help XiniX tacticly (XiniX's weak point) while not costing too much positionally (stronger point).

Though, I seem to be limitting the reductions a lot more than others.

Tony

Hi Tony,

good to hear that Xinix is still going..

What do you think the history pruning/ late move reductions gives Xinix? I'm seeing about +40 ELO from this technique. Maybe a really good implementation gives more?

Regards,
Tom

[Tony van Roon-Werten]

Strange that it seems to offer some programs a lot, and some very little.

Aren't most tricks like that?

Does the extra depth help programs which aren't (relatively) strong at tactics?

I think it's more complicated than that. For instance, The Baron and Glaurung are both relatively weak at tactics, but late move reductions seem to help Glaurung but not The Baron. Perhaps it tends to help more in simple and stupid programs (mine is one of those) than in more complicated and knowledge-loaded programs.

Tord

Not sure, it seems to help XiniX tacticly (XiniX's weak point) while not costing too much positionally (stronger point).

Though, I seem to be limitting the reductions a lot more than others.

Tony

Hi Tony,

good to hear that Xinix is still going..

What do you think the history pruning/ late move reductions gives Xinix? I'm seeing about +40 ELO from this technique. Maybe a really good implementation gives more?

Regards,
Tom

Hi Tom,

I'm not sure, but I think it gives XiniX really a lot. XiniX has always been quite strong positionally, but weak at tactics.

I was already using a relative of this technique, but not to reduce "bad moves" in to search, but rather add "good moves" into first plies of quiescence.

This reduction gives more depth, so it becomes better at tactics, without causing to much weakening positionally.

In addition, it seems to limit explosions of my search, when using "creative extensions"

I guestimate the improvement is >100 Elo. Split out: tacticly it improves 120 and positionally it got worse 20

My guess is that engines stronger tacticly than positionally gain a lot less.

Cheers,

Tony

[Tom King]

Hi Tom,

I'm not sure, but I think it gives XiniX really a lot. XiniX has always been quite strong positionally, but weak at tactics.

I was already using a relative of this technique, but not to reduce "bad moves" in to search, but rather add "good moves" into first plies of quiescence.

This reduction gives more depth, so it becomes better at tactics, without causing to much weakening positionally.

In addition, it seems to limit explosions of my search, when using "creative extensions"

I guestimate the improvement is >100 Elo. Split out: tacticly it improves 120 and positionally it got worse 20

My guess is that engines stronger tacticly than positionally gain a lot less.

Cheers,

Tony

Wow another engine which seems to get 100 ELO from this simple technique! Amazing. Perhaps there is even more to gain by careful tuning?

[Tord Romstad]

Hi Tom,

I'm not sure, but I think it gives XiniX really a lot. XiniX has always been quite strong positionally, but weak at tactics.

I was already using a relative of this technique, but not to reduce "bad moves" in to search, but rather add "good moves" into first plies of quiescence.

This reduction gives more depth, so it becomes better at tactics, without causing to much weakening positionally.

In addition, it seems to limit explosions of my search, when using "creative extensions"

I guestimate the improvement is >100 Elo. Split out: tacticly it improves 120 and positionally it got worse 20

My guess is that engines stronger tacticly than positionally gain a lot less.

Cheers,

Tony

Wow another engine which seems to get 100 ELO from this simple technique! Amazing.

The last time I tested (which was admittedly very long ago), it was worth around 100 Elo for me, too. I got another 40-50 points when I stopped using history counters and replaced them with more intelligent criterions.

My program, like Tony's, has always struggled with tactics. People will laugh at me if I try to claim that it is positionally strong, though.

Perhaps there is even more to gain by careful tuning?

Certainly. Late move reductions as used in current chess programs is a very primitive technique, and I am sure it will be improved considerably in the future.

Tord

[Dann Corbit]

Has anyone tried tossing out null move and using late history reductions only for trimming branches?

Has anyone tried history reductions that scale smoothly from the worst to the best (instead of chuky drops in plies like falling off of a cliff)?

[Uri Blass]

I ran noomen match between movei with late move reduction and movei without late move reduction at 2 minutes/40 moves and the version with late move reduction won 59-41.

I do not know how much it gives against other opponents or at longer time control.

Uri

[Tom King]

I ran noomen match between movei with late move reduction and movei without late move reduction at 2 minutes/40 moves and the version with late move reduction won 59-41.

I do not know how much it gives against other opponents or at longer time control.

Uri

I've done more testing, and I'm now seeing that a combination of late move reductions, tweaked eval, a bug fix, recompiling with a newer compiler is giving about +100 ELO.

My guesstimate is that late move reductions gives about 40 ELO. I strongly suspect more gains would be possible through improved tuning.

Has anyone tried some of the late move pruning ideas found in Toga?

Regards,
Tom

[Uri Blass]

I tried now at 5 minutes/40 moves and after 50 games the result was 25-25

Note that in the first 50 games at 2 minutes/40 moves I got result of
25.5-24.5 and in games 51-100 I got result of 33.5-16.5 and it is possible that there are positions when history pruning is more productive for me.

My rules are relatively complicated and I will probably throw them and try something similiar to tord but I want to know first how much I get from history pruning.

Unlike other people I simply do not know how much I earn from history based pruning.

I hope to have data from the CEGT tests.
I hope to see that I do not earn much from it because it is going to encourage me to drop the history code and make the program more simple and to try to use only evaluation data to decide about late move reduction.

I believe that it is harder for me to get big improvement from late move reduction because I probably earn much from evaluation based pruning when the idea is to have something like if eval>margin(beta,depth,other factores) return beta.

Uri

[Dann Corbit]

{snip}
Has anyone tried some of the late move pruning ideas found in Toga?

Regards,
Tom

Fruit (and hence Toga) along with Glaurung are the pioneers of late move (history) reduction based pruning. It has been found in Fruit for a long time.

[Uri Blass]

{snip}
Has anyone tried some of the late move pruning ideas found in Toga?

Regards,
Tom

Fruit (and hence Toga) along with Glaurung are the pioneers of late move (history) reduction based pruning. It has been found in Fruit for a long time.

Movei is using late move reduction before fruit and glaurung so fruit and glaurung are not the first to try the idea and find that it is productive(my guess is that some commercial programs are also using it before movei).

I guess that doing late move reduction only based on evaluation and not based on history counters can be better and I may try it.

Uri