Should reduction depend on depth?

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
lkaufman
Posts: 3771
Joined: Sun Jan 10, 2010 5:15 am
Location: Maryland USA
Contact:

Should reduction depend on depth?

Post by lkaufman » Sat Jan 14, 2012 3:56 pm

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?

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

Re: Should reduction depend on depth?

Post by lucasart » Sat Jan 14, 2012 4:00 pm

lkaufman wrote: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

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

Re: Should reduction depend on depth?

Post by lucasart » Sat Jan 14, 2012 4:17 pm

lkaufman wrote: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
Posts: 8611
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: Should reduction depend on depth?

Post by Uri Blass » Sat Jan 14, 2012 5:52 pm

lkaufman wrote: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
Posts: 3771
Joined: Sun Jan 10, 2010 5:15 am
Location: Maryland USA
Contact:

Re: Should reduction depend on depth?

Post by lkaufman » Sat Jan 14, 2012 7:10 pm

lucasart wrote:
lkaufman wrote: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
Posts: 613
Joined: Sun Jan 18, 2009 6:03 am

Re: Should reduction depend on depth?

Post by zamar » Sat Jan 14, 2012 7:41 pm

Uri Blass wrote: 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.
Joona Kiiski

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

Re: Should reduction depend on depth?

Post by Eelco de Groot » Sat Jan 14, 2012 8:16 pm

Uri Blass wrote:
lkaufman wrote: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 :P 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
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

Uri Blass
Posts: 8611
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: Should reduction depend on depth?

Post by Uri Blass » Sat Jan 14, 2012 10:11 pm

zamar wrote:
Uri Blass wrote: 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
Posts: 2684
Joined: Sat Jun 14, 2008 7:17 pm

Re: Should reduction depend on depth?

Post by mcostalba » Sat Jan 14, 2012 10:52 pm

zamar wrote: 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
Posts: 3771
Joined: Sun Jan 10, 2010 5:15 am
Location: Maryland USA
Contact:

Re: Should reduction depend on depth?

Post by lkaufman » Sat Jan 14, 2012 11:17 pm

zamar wrote:
Uri Blass wrote: 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.

Post Reply