Should reduction depend on depth?

[Eelco de Groot]

I don't quite follow where the number 24 plies comes from, but to my thinking ANY algorithm that applies to the last 24 plies is silly. Anything that is valid anywhere near that far from the leaf almost certainly must be valid at any distance from the leaf.

Well, but then I could use an even higher number, as long as I was sure the moves pruned where all moves with zero chance of producing a beta cut-off. Which you can never be 100% sure except by a very deep search, but there just is a limit to the amount of moves/positions you can search. But it is just an experiment and as you can see in the futility margins I use (post above), they are growing at a rate that is on the order of the square of the normal rate for Stockfish futility margins so that should undercut most oversights. And also the reductions are no absolute numbers so you could rephrase it a bit by thinking; "Are there moves that need to be searched 24 plies deeper than other moves, before you can be certain whether they are good or not?". Then I think the answer is yes so Larry I am not yet ready to accept that a search difference of 24 plies is silly !

Furthermore, it is almost certainly wrong to prune ANY move (except for something like bishop underpromotion that is extremely rare) more than around ten moves back from the leaf, because pruning at ten moves back eliminates 99.9% of the underlying tree assuming a branching factor of 2; how much more can you save by pruning even earlier?.

True I suppose, but if you cut back a 24 ply tree with ten moves that still leaves a fourteen ply deep tree, that is still a significant save if you could be sure at the root there is a completely irrelevant position. So I'm not completely buying your argument Larry. That's why I said at a certain point, smart algorithms will have to stop searching and store the search-result permanently in position learning, as long as the search-result is deep enough below alpha. In order to do that you can't use a null window search centered on alpha, you will have to go below it, but especially in a cluster I think you will be better off leaving alpha beta anyway. That was my argument.

Can you clarify exactly what you are pruning or reducing 24 plies back, but not 25 plies back?

The pruning rules are not changed much from Stockfish here and neither is the static evaluation much different so that works the same as in Stockfish futility pruning. Only the futility margins after a while are growing much faster than they do near the leaves. I'm not saying it works better this way but it is also not completely useless. I'm just testing what kind of holes this leaves in a search, compared to a more normal search.

Eelco

[lucasart]

Should the amount of LMR reduction be an increasing function of depth, as in Stockfish, or should it be depth-independent, as in Rybka and Ippo and Critter?

actually it looks like the latest IvanHoe has a depth dependant reduction
http://chess.cygnitec.com/engine/ivanhoe/
(look for version 999946h, lowest number highest letter is the latest one). but i'm not sure as their code is very messy and hard to read.

Can you tell whether it appears to be an increasing function of depth? I'm afraid that I am pretty much a novice at reading code. As Uri says, even a decreasing function of depth is possible; it's not obvious which way is better, although an increasing function seems more natural.

increasing
(decreasing would be illogical)

[lkaufman]

I don't quite follow where the number 24 plies comes from, but to my thinking ANY algorithm that applies to the last 24 plies is silly. Anything that is valid anywhere near that far from the leaf almost certainly must be valid at any distance from the leaf.

Well, but then I could use an even higher number, as long as I was sure the moves pruned where all moves with zero chance of producing a beta cut-off. Which you can never be 100% sure except by a very deep search, but there just is a limit to the amount of moves/positions you can search. But it is just an experiment and as you can see in the futilty margins I use (post above), they are growing at a rate that is on the order of the square of the normal rate for Stockfish futility margins so that should undercut most oversights. And also the reductions are no absolute numbers so you could rephrase it a bit by thinking; "Are there moves that need to be searched 24 plies deeper than other moves, before you can be certain whether they are good or not?". Then I think the answer is yes so Larry I am not yet ready to accept that a search difference of 24 plies is silly !

Furthermore, it is almost certainly wrong to prune ANY move (except for something like bishop underpromotion that is extremely rare) more than around ten moves back from the leaf, because pruning at ten moves back eliminates 99.9% of the underlying tree assuming a branching factor of 2; how much more can you save by pruning even earlier?.

True I suppose, but if you cut back a 24 ply tree with ten moves that still leaves a fourteen ply deep tree, that is still a significant save if you could be sure at the root there is a completely irrelevant position. So I'm not completely buying your argument Larry. That's why I said at a certain point, smart algorithms will have to stop searching and store the search-result permanently in position learning, as long as the search-result is deep enough below alpha. In order to do that you can't use a null window search centered on alpha, you will have to go below it, but especially in a cluster I think you will be better off leaving alpha beta anyway. That was my argument.

Can you clarify exactly what you are pruning or reducing 24 plies back, but not 25 plies back?

The pruning rules are not changed much from Stockfish here and neither is the static evaluation much different so that works the same as in Stockfish futility pruning. Only the futility margins after a while are growing much faster then they do near the leaves. I'm not saying it works better this way but it is also not completely useless.

Eelco

I'm not very good at reading code, but it looks like you are doing move-count pruning up to 24 plies back, is that correct? In other words, if you are past some move number (maybe 100? I don't know) you prune the move (if it is "quiet"), regardless of the score. Is that a correct interpretation of what you are doing?
If it is, I have to say I think it is ridiculous. I don't mean to use harsh language, I appreciate your input on various issues, but even with Don I call things as I see them. Of course if the move number is something absurdly high like 500 it would just never come into play, but assuming the move number is one that is sometimes reached, I can tell you with 100% certainty that such a move is not unlikely enough to be best to prune it more than ten ply back, let alone 24. Move ordering is just not that good; sometimes the winning move is the least-likely looking one! Now if you put enough conditions on a move to be 99.99% certain it is not best, you could prune it more than ten plies back, but I'm sure that the cost of testing all these conditions would exceed the miniscule benefit.
Even pruning by the score cannot work that far back. Sometimes a sacrifice of a queen and a rook or more will work; it is very rare, but not rare enough for the tiny benefit you get from pruning that far back.
I can't think of anything besides bishop (and maybe rook) underpromotion that should be pruned more than about ten plies back. What else is 99.9+% certain not to be the best move, that can be identified cheaply?
To prove what I'm saying, change your 24 ply limits to 10 ply, and run the versions against each other at say 15 ply or so fixed depth. You only need record the times, not the results. After you have run a few hundred games, compare the total times taken. I'll predict the difference will be so tiny that it will be swamped by random factors like machine overhead etc. If you can't even detect the time saved, it's clearly not worthwhile to miss occasional surprise moves.

Regards,
Larry

[lucasart]

Joona's post certainly is a good summary.
But Bob also added an interesting point: testing at super fast time control may not be safe. The point is that increasing the LMR reduction at high depth may show no impact at super fast tc (where these high depths are rarely reached) but it may provide some (very small) improvement at longer time control.
You might want to chose some intermediate testing tc for that like 30"+0.5" or sth like that

[lkaufman]

Joona's post certainly is a good summary.
But Bob also added an interesting point: testing at super fast time control may not be safe. The point is that increasing the LMR reduction at high depth may show no impact at super fast tc (where these high depths are rarely reached) but it may provide some (very small) improvement at longer time control.
You might want to chose some intermediate testing tc for that like 30"+0.5" or sth like that

I thought it goes without saying that your test must allow the engine to reach search depths high enough to test whatever algorithm you are trying to test. That is why I think those who use one time limit for all tests are making a mistake; some judgment is needed. The SF algorithm for LMR already makes big differences in the reduction even at depths reached at say 10" +.1", but that might not be so for other schemes.

[zamar]

Here is a related question. Again, assume we are talking about depths beyond the above issues. Stockfish is vastly more aggressive about LMR than Rybka, Ippo, or Critter except at CUT nodes, where it doesn't seem to matter much what you do. I don't expect different programs to use the same parameters, but the difference here is HUGE. Yet, as we know, all of the above named programs are very strong. Can you offer any explanation as to why the above programs other than SF are so conservative (relative to SF) about LMR? Presumably if SF were to copy the Ippo LMR rules it would drop a lot of Elo, as I imagine would also be the case if Ippo copied SF rules. But why should this be so? In case you are wondering, Komodo is in between.

I really wish that I'd know the answer. For some strange reason these programs have climbed to a different local optimum. When IPPO was released we of course tried to fit some IPPO-based schemes in SF, but the only one that really work was the singular extension.

[lkaufman]

Here is a related question. Again, assume we are talking about depths beyond the above issues. Stockfish is vastly more aggressive about LMR than Rybka, Ippo, or Critter except at CUT nodes, where it doesn't seem to matter much what you do. I don't expect different programs to use the same parameters, but the difference here is HUGE. Yet, as we know, all of the above named programs are very strong. Can you offer any explanation as to why the above programs other than SF are so conservative (relative to SF) about LMR? Presumably if SF were to copy the Ippo LMR rules it would drop a lot of Elo, as I imagine would also be the case if Ippo copied SF rules. But why should this be so? In case you are wondering, Komodo is in between.

I really wish that I'd know the answer. For some strange reason these programs have climbed to a different local optimum. When IPPO was released we of course tried to fit some IPPO-based schemes in SF, but the only one that really work was the singular extension.

That is pretty much the same experience we had with Komodo, although we did have some success with one or two other Ippo ideas besides SE. In general our search (not eval) has more in common with SF than with the Ippos. I find it very interesting that both SF and Komodo cannot get a benefit out of Lazy Eval, whereas all the Ippos, as well as Rybka and Critter, do use it very successfully. Do you have any theory as to why this is so?

I note that SF does use the Ippo idea of "expected gain". We don't use it in Komodo, not having detected any benefit. How much of an elo gain would you attribute to this idea in SF?

One other question. Do you do all testing on single-core SF, or do you optimize anything for MP (I'm only talking about terms that are also relevant to SP)? I wonder if this makes much difference?

[rvida]

Stockfish LMR reductions are the largest of any program with which I am familiar. This is the main reason that Stockfish reaches greater depths than any other program at any normal time limit.

(at least partially) true. I just wonder why you didn't agree with this while discussing on the Rybka Forum?

On the Rybka Forum we were discussing LOW DEPTH pruning, which I took to mean the last four plies, which is the Ivanhoe definition and is what you call "selective search". On those plies I claim that Ivanhoe and Critter both prune much more than SF. SF uses higher move counts for pruning, larger margins for futility and static null, etc. I think we only disagreed because you had a different definition of LOW DEPTH in your mind than I did. There is no question that SF uses more aggressive LMR than Ivanhoe or Critter at higher depths; I haven't done the calculation to determine at what depth SF LMR becomes more aggressive than Ivanhoe or Critter, but I imagine it is somewhere around 5 or 6 plies from the root. Please let us know whether you still disagree with me now that I have made clear what I meant by LOW DEPTH.

I meant more selective in general, not only related to low depth pruning. As in SF having a lower EBF.

[lkaufman]

Stockfish LMR reductions are the largest of any program with which I am familiar. This is the main reason that Stockfish reaches greater depths than any other program at any normal time limit.

(at least partially) true. I just wonder why you didn't agree with this while discussing on the Rybka Forum?

On the Rybka Forum we were discussing LOW DEPTH pruning, which I took to mean the last four plies, which is the Ivanhoe definition and is what you call "selective search". On those plies I claim that Ivanhoe and Critter both prune much more than SF. SF uses higher move counts for pruning, larger margins for futility and static null, etc. I think we only disagreed because you had a different definition of LOW DEPTH in your mind than I did. There is no question that SF uses more aggressive LMR than Ivanhoe or Critter at higher depths; I haven't done the calculation to determine at what depth SF LMR becomes more aggressive than Ivanhoe or Critter, but I imagine it is somewhere around 5 or 6 plies from the root. Please let us know whether you still disagree with me now that I have made clear what I meant by LOW DEPTH.

I meant more selective in general, not only related to low depth pruning. As in SF having a lower EBF.

Then we are in complete agreement, we just misunderstood each other. Just to clarify, we clearly agree that SF has a lower EBF at all depths above what you call "selective search"; but do you also agree that SF has a higher EBF WITHIN the last four plies?

[rvida]

... but do you also agree that SF has a higher EBF WITHIN the last four plies?

It is hard to compare, but I think not. SF uses a bit wider margins, but throws out moves based on either of move count / value conditions. Critter throws out moves only when both conditions are true.

SF pruning condition (schematic):

Code: Select all

if &#40;move_count > n || futility_value < beta&#41; 
  skip_move;

Critter condition:

Code: Select all

if &#40;move_count > n && futility_value < beta&#41;
  skip_move;

Just think a bit about consequences of this difference.