Should reduction depend on depth?

[lkaufman]

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? In Komodo we have gone both ways on this issue, and still we are not sure. What say you all? Does anyone have solid data on this issue?

[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? In Komodo we have gone both ways on this issue, and still we are not sure. What say you all? Does anyone have solid data on this issue?

it seems a bit strange to have it depend on depth. it means you introduce a path-dependant condition, no?
i suppose the only way to know is to test, and if the testing gives no clear result, it's best to keep things simple and use an LMR reduction independant on the depth. if critter manages to be so strong w/o doing it, then it can't be worth much

[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.

[Uri Blass]

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? In Komodo we have gone both ways on this issue, and still we are not sure. What say you all? Does anyone have solid data on this issue?

Third option is to be a decreasing function on depth.

I see no logical reason to reduce more plies when the remaining depth is big.

[lkaufman]

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.

[zamar]

I see no logical reason to reduce more plies when the remaining depth is big.

There is a very logical reason to do this:
When we remaining_depth = 5 and we are considering how many plies to reduce, there is an enormous impact to tactical strength. But when remaining_depth = 15 the effect is much milder and we might want to be just a little bit more aggressive.

It's a known fact that ELO-gap between 3-ply and 4-ply fixed depth search is much bigger than between 13-ply and 14-ply fixed depth search.

Now reducing at the end of the move list is nothing more than making program weaker at less important moves, so that it can search deeper and thus become stronger at more important moves. You may also see this as a kind of ELO-strength transfer from the likely less important lines to the likely more important lines. If you want to keep this ELO-strength transfer metric close to constant at each search tree level, it automatically means reducing more heavily in higher depths.

But again we have to deal with the fact that LMR interacts heavily with Null move, LMP (=late move pruning) and maybe even futility pruning, so what works best depends a lot of how other things are done.

ELO-wise I do not expect it to be a big issue (~10 ELOs) whether you decide to go with depth-dependant or depth-independent reductions.

[Eelco de Groot]

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? In Komodo we have gone both ways on this issue, and still we are not sure. What say you all? Does anyone have solid data on this issue?

Third option is to be a decreasing function on depth.

I see no logical reason to reduce more plies when the remaining depth is big.

Maybe Uri is implying something like a reduction that grows faster than depth, or maybe more logical a (reduction) function growing equally fast after a while. That would mean I think shutting down some moves after a while, unless you can't find the stored result in the hashtable anymore. I'm pretty sure that Rybka is experimenting with this, but that is just based on logic again At some point you have to switch from searching to position learning, or at least that seems logical. If a program already has position learning, like Critter, it is easier to adapt this to LMP and LMR.

By the way most Late Move 'Reductions' in Stockfish are in fact in my opinion forward pruning decisions, there is as far as I know very little of the regular LMR. Maybe I have missed that but I don't think what Stockfish does is LMR? Joona calls this Late Move Pruning, at least I think that is what he is referring to. If you don't make that, LMP that is, depth dependant then you are going to remain blind to certain moves in positions, because the static eval you base the pruning on (in Stockfish) is not going to change either. I don't have the slightest idea what the Rybka family is doing instead, but it seems to me comparing apples and oranges if they reduce "late moves" maybe without a depth dependancy, and not prune them instead, because then you are not blind anymore for certain moves.

Regards, Eelco

[Uri Blass]

I see no logical reason to reduce more plies when the remaining depth is big.

There is a very logical reason to do this:
When we remaining_depth = 5 and we are considering how many plies to reduce, there is an enormous impact to tactical strength. But when remaining_depth = 15 the effect is much milder and we might want to be just a little bit more aggressive.

My feeling is that reduction or pruning when the remaining depth is small can be safer because you can use history information to be sure about something.

If you see that in the last million cases when the remaining depth was 5 the move Ke1-e2 failed low in 99.9998% of the cases then you can be almost sure that Ke1-e2 is going to fail low again.

In the case that the remaining depth is 15 you are not going to have million cases when you tried Ke1-e2 so you cannot get the same confidence that the reduction is justified because it is possible that Ke1-e2 is often a good idea but you need to search to relatively big depth to show it.

[mcostalba]

There is a very logical reason to do this:
When we remaining_depth = 5 and we are considering how many plies to reduce, there is an enormous impact to tactical strength. But when remaining_depth = 15 the effect is much milder and we might want to be just a little bit more aggressive.

It's a known fact that ELO-gap between 3-ply and 4-ply fixed depth search is much bigger than between 13-ply and 14-ply fixed depth search.

Now reducing at the end of the move list is nothing more than making program weaker at less important moves, so that it can search deeper and thus become stronger at more important moves. You may also see this as a kind of ELO-strength transfer from the likely less important lines to the likely more important lines. If you want to keep this ELO-strength transfer metric close to constant at each search tree level, it automatically means reducing more heavily in higher depths.

But again we have to deal with the fact that LMR interacts heavily with Null move, LMP (=late move pruning) and maybe even futility pruning, so what works best depends a lot of how other things are done.

ELO-wise I do not expect it to be a big issue (~10 ELOs) whether you decide to go with depth-dependant or depth-independent reductions.

Joona has written a very high quality post: I suggest newbie engine developers to give it a very good read because it is not common to find such a clear and deep description of how things works.

[lkaufman]

I see no logical reason to reduce more plies when the remaining depth is big.

There is a very logical reason to do this:
When we remaining_depth = 5 and we are considering how many plies to reduce, there is an enormous impact to tactical strength. But when remaining_depth = 15 the effect is much milder and we might want to be just a little bit more aggressive.

It's a known fact that ELO-gap between 3-ply and 4-ply fixed depth search is much bigger than between 13-ply and 14-ply fixed depth search.

Now reducing at the end of the move list is nothing more than making program weaker at less important moves, so that it can search deeper and thus become stronger at more important moves. You may also see this as a kind of ELO-strength transfer from the likely less important lines to the likely more important lines. If you want to keep this ELO-strength transfer metric close to constant at each search tree level, it automatically means reducing more heavily in higher depths.

But again we have to deal with the fact that LMR interacts heavily with Null move, LMP (=late move pruning) and maybe even futility pruning, so what works best depends a lot of how other things are done.

ELO-wise I do not expect it to be a big issue (~10 ELOs) whether you decide to go with depth-dependant or depth-independent reductions.

We thought that more aggressive LMR reductions at higher depths were justified by better move ordering at higher depths, but we are having trouble proving any benefit by doing so. Of course at very low depth LMR would interact with futility pruning, LMP, static null, etc. as you say, but I'm not talking about such low depths as this.
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.