history pruning/ late move pruning

Programming Topics (Computer Chess) and technical aspects as test techniques, book building, program tuning etc

Moderator: Andres Valverde

history pruning/ late move pruning

Postby Tom King » 02 Mar 2006, 14:55

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
Tom King
 
Posts: 19
Joined: 19 Jul 2005, 09:36

Re: history pruning/ late move pruning

Postby Stef Luijten » 02 Mar 2006, 16:03

Tom,
Fully agree, I think Wing has gained over 100 ELO points form adding history pruning!
Stef
Stef Luijten
 
Posts: 12
Joined: 10 Nov 2005, 12:48

Re: history pruning/ late move pruning

Postby Tom King » 02 Mar 2006, 16:10

Stef Luijten wrote: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.

:)
Tom King
 
Posts: 19
Joined: 19 Jul 2005, 09:36

Re: history pruning/ late move pruning

Postby Thomas Mayer » 02 Mar 2006, 17:20

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... :)
User avatar
Thomas Mayer
 
Posts: 40
Joined: 26 Oct 2004, 13:45
Location: Germany

Re: history pruning/ late move pruning

Postby Tord Romstad » 02 Mar 2006, 17:43

Thomas Mayer wrote: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
User avatar
Tord Romstad
 
Posts: 639
Joined: 09 Oct 2004, 12:49
Location: Oslo, Norway

Re: history pruning/ late move pruning

Postby H.G.Muller » 02 Mar 2006, 18:25

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....
User avatar
H.G.Muller
 
Posts: 3119
Joined: 16 Nov 2005, 12:02
Location: Diemen, NL

Re: history pruning/ late move pruning

Postby Alessandro Scotti » 02 Mar 2006, 18:54

H.G.Muller wrote: (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
User avatar
Alessandro Scotti
 
Posts: 306
Joined: 20 Nov 2004, 00:10
Location: Rome, Italy

Re: history pruning/ late move pruning

Postby Tom King » 02 Mar 2006, 20:43

Thomas Mayer wrote: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?
Tom King
 
Posts: 19
Joined: 19 Jul 2005, 09:36

Re: history pruning/ late move pruning

Postby Tord Romstad » 03 Mar 2006, 10:15

Tom King wrote: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
User avatar
Tord Romstad
 
Posts: 639
Joined: 09 Oct 2004, 12:49
Location: Oslo, Norway

Re: history pruning/ late move pruning

Postby Tony van Roon-Werten » 03 Mar 2006, 22:12

Tord Romstad wrote:
Tom King wrote: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
Tony van Roon-Werten
 
Posts: 99
Joined: 02 Oct 2004, 15:31
Location: 's Hertogenbosch, Netherlands

Re: history pruning/ late move pruning

Postby Tom King » 04 Mar 2006, 22:24

Tony van Roon-Werten wrote:
Tord Romstad wrote:
Tom King wrote: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
Tom King
 
Posts: 19
Joined: 19 Jul 2005, 09:36

Re: history pruning/ late move pruning

Postby Tony van Roon-Werten » 05 Mar 2006, 09:50

Tom King wrote:
Tony van Roon-Werten wrote:
Tord Romstad wrote:
Tom King wrote: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
Tony van Roon-Werten
 
Posts: 99
Joined: 02 Oct 2004, 15:31
Location: 's Hertogenbosch, Netherlands

Re: history pruning/ late move pruning

Postby Tom King » 06 Mar 2006, 19:59

Tony van Roon-Werten wrote:
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?
Tom King
 
Posts: 19
Joined: 19 Jul 2005, 09:36

Re: history pruning/ late move pruning

Postby Tord Romstad » 06 Mar 2006, 22:43

Tom King wrote:
Tony van Roon-Werten wrote:
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
User avatar
Tord Romstad
 
Posts: 639
Joined: 09 Oct 2004, 12:49
Location: Oslo, Norway

Re: history pruning/ late move pruning

Postby Dann Corbit » 07 Mar 2006, 01:42

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)?
Dann Corbit
 

Re: history pruning/ late move pruning

Postby Uri Blass » 28 Mar 2006, 09:55

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
User avatar
Uri Blass
 
Posts: 727
Joined: 09 Oct 2004, 05:59
Location: Tel-Aviv

Re: history pruning/ late move pruning

Postby Tom King » 29 Mar 2006, 13:15

Uri Blass wrote: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
Tom King
 
Posts: 19
Joined: 19 Jul 2005, 09:36

Re: history pruning/ late move pruning

Postby Uri Blass » 29 Mar 2006, 18:40

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
User avatar
Uri Blass
 
Posts: 727
Joined: 09 Oct 2004, 05:59
Location: Tel-Aviv

Re: history pruning/ late move pruning

Postby Dann Corbit » 30 Mar 2006, 00:43

Tom King wrote:{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.
Dann Corbit
 

Re: history pruning/ late move pruning

Postby Uri Blass » 30 Mar 2006, 01:15

Dann Corbit wrote:
Tom King wrote:{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
User avatar
Uri Blass
 
Posts: 727
Joined: 09 Oct 2004, 05:59
Location: Tel-Aviv

Next

Return to Programming and Technical Discussions

Who is online

Users browsing this forum: No registered users and 5 guests