Adjustable search pruning depending on time control

[jd1]

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

[Eelco de Groot]

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 , 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

[Don]

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

[ZirconiumX]

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

[rbarreira]

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]

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]

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]

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

[lucasart]

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.

[lkaufman]

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.