Adjustable search pruning depending on time control

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.
jd1
Posts: 263
Joined: Wed Oct 24, 2012 12:07 am

Adjustable search pruning depending on time control

Post by jd1 » Thu Dec 20, 2012 9:48 am

Hi,

There seems to be general knowledge that aggressive pruning is more effective at low depths, and therefore works better at fast games. Conversely, less-aggressive pruning may be stronger at long time controls. Please correct me if this is wrong.

So my idea is to adjust the aggressive of the pruning depending on the time control. This can be done by adjusting the Futility Margins, Move Count pruning, null move reduction, history pruning/reductions, etc. depending on the time control. Does this idea make any sense?

Thanks,
Jerry

User avatar
Eelco de Groot
Posts: 4029
Joined: Sun Mar 12, 2006 1:40 am
Location: Groningen

Re: Adjustable search pruning depending on time control

Post by Eelco de Groot » Thu Dec 20, 2012 2:07 pm

I'm not sure about this. Also I don't remember programmers actually stating this. Actually I feel it is more the opposite of this Jerry although you have to take into account that pruning is only relative to something. If you prune everywhere literally, the effect is only that you do more iterations in a certain amount of time. This can be beneficial because it helps ordering the tree. But if some moves are exempt from pruning, aggressive pruning will mean that those moves are extended. This is a bit I see the state Stockfish is in. "Everything" is very heavily Late Move Pruned and Late Move Reduced (but the tactics are exempt). See for instance a comment here by Joona
It's not a bug. Negative futility pruning values at depth = 1 are okay. Move count based pruning is going to hit us hard anyway razoring everything where moveCount > 4. Negative futility pruning values only mean that side to move needs to have very good position to avoid prunings.

Of course I don't claim that current formula is optimal, but there is no bug
negative futility margins 8-) , and every move beyond the first four (non tactical moves) is running the risk of being LMP pruned. You can't realy reduce much more than that. Exempt from all this are mainly all tactical exchanges, "dangerous" checks but most of the traditional extensions for passed pawns etc. are no longer awarded in recent Stockfish, there was no measurable benefit for them measured by Marco. I think that includes some medium depths, not very long depths but maybe the effect would be even stronger? The general picture I hypothesize: the longer the timecontrol, the more you can prune.

Regards, Eelco
Debugging is twice as hard as writing the code in the first
place. Therefore, if you write the code as cleverly as possible, you
are, by definition, not smart enough to debug it.
-- Brian W. Kernighan

User avatar
Don
Posts: 5106
Joined: Tue Apr 29, 2008 2:27 pm

Re: Adjustable search pruning depending on time control

Post by Don » Thu Dec 20, 2012 2:46 pm

jd1 wrote:Hi,

There seems to be general knowledge that aggressive pruning is more effective at low depths, and therefore works better at fast games. Conversely, less-aggressive pruning may be stronger at long time controls. Please correct me if this is wrong.
This is not clear. The program that probably has the lowest branching factor is Stockfish so it is probably the most aggressive in LMR and pruning. But Stockfish may also be the most scalable program. It's truly terrible at time controls like game in 5 or 10 seconds, but at long time controls it is on par with the very best programs. And it is usually reporting depth 2 or 3 ply more than (for example) Komodo and Houdini. So it gives up a lot for those depths but it doesn't seem to hurt it.

So my idea is to adjust the aggressive of the pruning depending on the time control. This can be done by adjusting the Futility Margins, Move Count pruning, null move reduction, history pruning/reductions, etc. depending on the time control. Does this idea make any sense?

Thanks,
Jerry
Capital punishment would be more effective as a preventive measure if it were administered prior to the crime.

ZirconiumX
Posts: 1327
Joined: Sun Jul 17, 2011 9:14 am

Re: Adjustable search pruning depending on time control

Post by ZirconiumX » Thu Dec 20, 2012 3:53 pm

As far as I can tell, this seems to be the case - the question remains as to how much do you widen the search?

I remember Daniel Homan doing some tests on EXChess - when the plain AB searcher was on even ground with the selective searcher, plain AB won hands down, but when at time controls, rather than node or depth controls, the selective searcher won because it could outsearch the plain AB searcher.

Clearly, at depth or node TCs plain AB is best, but standard time controls mean that selective search is best. So on those grounds, I'd probably disable selectivity on depth or node TCs.

Matthew:out
Some believe in the almighty dollar.

I believe in the almighty printf statement.

rbarreira
Posts: 900
Joined: Tue Apr 27, 2010 1:48 pm

Re: Adjustable search pruning depending on time control

Post by rbarreira » Thu Dec 20, 2012 3:58 pm

ZirconiumX wrote:As far as I can tell, this seems to be the case - the question remains as to how much do you widen the search?

I remember Daniel Homan doing some tests on EXChess - when the plain AB searcher was on even ground with the selective searcher, plain AB won hands down, but when at time controls, rather than node or depth controls, the selective searcher won because it could outsearch the plain AB searcher.

Clearly, at depth or node TCs plain AB is best, but standard time controls mean that selective search is best. So on those grounds, I'd probably disable selectivity on depth or node TCs.

Matthew:out
I doubt that plain AB wins at node TCs, because nodes searched and time are highly correlated.

dchoman
Posts: 171
Joined: Wed Dec 28, 2011 7:44 pm
Location: United States

Re: Adjustable search pruning depending on time control

Post by dchoman » Thu Dec 20, 2012 4:09 pm

rbarreira wrote:
ZirconiumX wrote:As far as I can tell, this seems to be the case - the question remains as to how much do you widen the search?

I remember Daniel Homan doing some tests on EXChess - when the plain AB searcher was on even ground with the selective searcher, plain AB won hands down, but when at time controls, rather than node or depth controls, the selective searcher won because it could outsearch the plain AB searcher.

Clearly, at depth or node TCs plain AB is best, but standard time controls mean that selective search is best. So on those grounds, I'd probably disable selectivity on depth or node TCs.

Matthew:out
I doubt that plain AB wins at node TCs, because nodes searched and time are highly correlated.
Indeed, my test was only fixed depth (full width AB wins easily) vs. regular time control (selective wins easily). I forget the numbers (they are in my earlier posts on this), but it was something like a 300 elo advantage either way. The idea was to see how much could be gained, at least in principle, by doing selective search better so that it doesn't miss any of the important moves. For my engine at a fixed depth of 7, there appears to be about 300 elo of good moves missed by the selective search.

- Dan

diep
Posts: 1780
Joined: Thu Mar 09, 2006 10:54 pm
Location: The Netherlands
Contact:

Re: Adjustable search pruning depending on time control

Post by diep » Thu Dec 20, 2012 4:22 pm

Eelco de Groot wrote:I'm not sure about this. Also I don't remember programmers actually stating this.
It's correct not many stated this over here.

Donald is correct however. For Diep basically getting a few plies deeper at faster time controls at a limited amount of cores , say <= 8 cores, then basically searching deeper works magnificent.

When we move to cluster and/or slower time controls, things become less clear. A crucial depth at bullet/blitz seems to be for example the depth of 12 ply versus 14 ply. That's plies without reductions/pruning. Of course we get a lot deeper seemingly yet positional it's similar then to 12 vs 14 ply.

As some very complicated tactics gets found at those depths. Really seems tactical break even point in my tests. Many forms of pruning winning 2 ply search depth, they really no longer work when you would get that 14 ply (without pruning/reductions).

Realize there is a lot of prunings algorithms out there which hardly ever get attention here in CCC. Now with Diep i might have more options there as it's at turtle speed.

by the way who is J Donald to guess so many things here pretty ok? Did we know him before under a different name? Photo, URL, facebook?

jd1
Posts: 263
Joined: Wed Oct 24, 2012 12:07 am

Re: Adjustable search pruning depending on time control

Post by jd1 » Thu Dec 20, 2012 7:15 pm

Hi Vincent and others, thanks for your replies.

I am a young chess programmer from New Zealand (I know of Graham Banks locally, and I have around for about three and I have read most posts in this forum during that time. So yes, I am sort of new. I don't have facebook or a webpage.

Anyhow thanks for the interesting replies.

Jerry

User avatar
lucasart
Posts: 3023
Joined: Mon May 31, 2010 11:29 am
Full name: lucasart
Contact:

Re: Adjustable search pruning depending on time control

Post by lucasart » Fri Dec 21, 2012 6:31 am

jd1 wrote: There seems to be general knowledge that aggressive pruning is more effective at low depths, and therefore works better at fast games. Conversely, less-aggressive pruning may be stronger at long time controls. Please correct me if this is wrong.
That's not what I've seen in my testing.
Theory and practice sometimes clash. And when that happens, theory loses. Every single time.

lkaufman
Posts: 3251
Joined: Sun Jan 10, 2010 5:15 am
Location: Maryland USA
Contact:

Re: Adjustable search pruning depending on time control

Post by lkaufman » Sun Dec 23, 2012 3:48 pm

Among top engines, only Stockfish changes the LMR formula based on depth, as far as I know. They reduce more as the depth goes up. In our testing with Komodo, we have never found evidence that considering depth in the LMR formula has any benefit. Of course, at very low depths where LMP, futility, etc. are done, you can prune more and more the closer you are to the leaf. Most top engines do increase the amount of null move reduction with increased depth.

As far as I know, everyone bases these depth-related changes on the remaining depth, rather than the time control. It is not apparent how considering the time control would help further, but it is possible.

Post Reply