Is LMR Sound.

[hgm]

The program can use the null move for detecting threats, that's something I understand. I read the earlier posts and I do not understand the interference of null moves and LMR. To keep it simple: if search depth is reduced by LMR you should decrease R of the null move ?

Most engines actually increase it. And this makes sense: you want to reduce the null move more than the real moves, so if almost all real moves are already reduced, you must reduce the null move more to keep up with it.

[Henk]

At large remaining depth the search would see those tactics with almost perfect accuracy anyway. The static rules would just force you undoing reductions on moves that the search already has proven unworthy.

The problem I encountered is that remaining depth reduces twice as fast when depth is decreased by two instead of one when applying LMR.

So if you start with a depth of 10 your effective search height is only 5 plies and that is far to low to investigate tactical combinations with one or move quiet moves involved.

And when LMR is applied within Null move check and you start with a search depth of 15 your effective search height will be less than 5 plies.

[Steve Maughan]

(...)The problem I encountered is that remaining depth reduces twice as fast when depth is decreased by two instead of one when applying LMR.

So if you start with a depth of 10 your effective search height is only 5 plies and that is far to low to investigate tactical combinations with one or move quiet moves involved.

And when LMR is applied within Null move check and you start with a search depth of 15 your effective search height will be less than 5 plies.

How often do you come across a 10 ply combination where all the moves are "quiet" i.e. no captures, no checks and no null move mate threats. You can also add the condition no consecutive moves by the same piece. There are hardly any combination which fit this description (although I'm sure such a position exists).

Steve

[Don]

At large remaining depth the search would see those tactics with almost perfect accuracy anyway. The static rules would just force you undoing reductions on moves that the search already has proven unworthy.

The problem I encountered is that remaining depth reduces twice as fast when depth is decreased by two instead of one when applying LMR.

So if you start with a depth of 10 your effective search height is only 5 plies and that is far to low to investigate tactical combinations with one or move quiet moves involved.

And when LMR is applied within Null move check and you start with a search depth of 15 your effective search height will be less than 5 plies.

Here is how you should think about this. Any of us who have been in computer chess for a few decades are used to thinking about what we can see on a given iteration. If a tactic is 1 ply deeper you need 1 extra ply to see it, right?

Well .... not necessarily! The old programs had a branching factor of about 5 or so. So think about how much extra TIME you need to see something, not the extra depth. Modern programs are much more aggressive about pruning and reduction and have a branching factor of about 2 or even better. The remarkable thing about this is that it is almost like you are getting 1 free ply for every one you search compared to the older programs. Do you get the point?

So you can be pretty happy if you only need 2 extra ply, your performance is just as good as the older programs! In practice we usually DO get an extra ply of tactics with an extra ply of search but no guarantees. So the trick is to try to get that, but you are still ahead of the game if you don't once in a while.

Let's imagine that your clever tactic takes 3 extra ply to see when compared to the older style programs with a branching factor of 4. It's a 17 ply tactic but you need 20. There is an excellent chance that the new program will race to the 20th iteration before the older program even gets near the 17th iteration it needs. With BF=4 vs BF=2 in fact you can figure that the older program may only get to depth 10 in the same time your new program does 20. So even losing a ply or two once in a while is hardly a problem. Of course we do everything we can NOT to miss anything and actually do a pretty remarkably good job - but the nature of speculative pruning and reductions is that invariably you will "miss" something. But what you gain is far more valuable than what you lose.

So think of this is 2 steps forward, 1/2 step back and repeat.

[Henk]

I put it this way, maybe a bit too simple:

If LMR increases my search depth from 8 to 15 but the effective length of the search path goes from 8 to 5 plies what do I gain. I loose 3 plies.

[Steve Maughan]

(...)If LMR increases my search depth from 8 to 15 but the effective length of the search path goes from 8 to 5 plies what do I gain. I loose 3 plies.

For all practical purposes any half decent implementation of LMR will never let the search go from 15 ply to effectively 5 ply.

I think at this point it has been explained ad-nauseum. If you think people like Don are wrong then so be it and good luck with writing your engine.

To continue arguing at this level without any concrete examples is borderline trolling (IMHO).

Steve

[lucasart]

I put it this way, maybe a bit too simple:

If LMR increases my search depth from 8 to 15 but the effective length of the search path goes from 8 to 5 plies what do I gain. I loose 3 plies.

It's a waste of everybody's time to keep talking about LMR eternally from an "a priori" point of view. The first thing you should do is experiment with it yourself, and do some measurements, then you'll understand better what is going on.

The fact is that LMR is
- theoretically unsound: in the sense that the PVS algorithm, with move count based search reductions, will returns different and unstable results.
- practically useful: the reward is worth more than the risk, if you implement LMR "correctly". In total, LMR is worth close to 100 ELO in my engine, and perhaps it's even more in top engines that do it better than me.

But in the end, it's not about theory, it's about practice. If LMR makes your engine play better, and the risk/reward ratio is favorable, then LMR is good - period.

A lot of things in computer chess are theoretically unsound, and good tuning can make the risk/reward ratio better.

[Henk]

[quote="Don]
Well .... not necessarily! The old programs had a branching factor of about 5 or so. So think about how much extra TIME you need to see something, not the extra depth. Modern programs are much more aggressive about pruning and reduction and have a branching factor of about 2 or even better. The remarkable thing about this is that it is almost like you are getting 1 free ply for every one you search compared to the older programs. Do you get the point?

.[/quote]

Almost like you are getting 1 free ply. The pain is in the word almost.

You can also see it this way. You have a budget of N nodes to distribute over branches of a search tree. Some get more some get less. Interesting moves get more. But when the programs is spending to much processing time in deciding which branches get more than others the search is not efficient.

[AlvaroBegue]

Well, I am done reading this thread. Our friend Henk is either a troll or someone who knows nothing about the subject trying to "teach" his misconceptions to a field of experts. In either case, nothing to see here.

Hopefully some of the clear explanations provided by several people will be useful to others who find this thread in the future, and the whole exercise hasn't been a waste of everybody's time.

[hgm]

You can also see it this way. You have a budget of N nodes to distribute over branches of a search tree. Some get more some get less. Interesting moves get more. But when the programs is spending to much processing time in deciding which branches get more than others the search is not efficient.

That is doubtful, because one goes in the exponent and the other is just the prefactor. If your engine gets 10 times slower in terms of nodes per second, to lower the effective branching ratio by 20%, you will reach a depth of 20 ply 3.8 times faster. In the end there will always be some depth at which the improvement in exponential behavior will outweigh the pre-factor, no matter how large it was.

Apart from that, deciding that branches with captures get more nodes than those without is hardly measurable in terms of CPU time.