Is LMR Sound.

[Evert]

There is really very little point in discussing whether late move reductions in general work or not. This can be (and has been) tested very easily by playing (a large number of) games.

It works.

All chess programs are different, so it works better for some than for others, and it may work "immediately" or after tweaking. But as a general statement, there is no argument that it does work.

[lucasart]

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.

The latter is also a Troll. Here he is

[Henk]

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.

Yes the test capture/noncapture is cheap, but adding another null move check for thread detection, (deciding whether it's safe to reduce for LMR) is not so cheap.

Also I thought that putting expensive checks near the root of a tree is less harmful then at the leafs. Because they are executed far and far less.
But then I read in earlier posts that extra checks are added for LMR nearby the leafs of the tree. Then I must say I don't understand it anymore.

[hgm]

The test to exempt moves that make a dangerous attack can be implemented in an extremely cheap way as well. The way I do it is that I inform the node that it was reached by a late move. That node starts searching a null move as usual. But I also let nodes always return their best move (in the root this is needed anyway, because you then want to play that move). So if the null move search fails low, and the move it returns was with the piece that did the late move, I add the reduction back to the depth before proceding. (I could also redo the null-move search with this new depth, but this is usually a waste of time.)

This is all almost free.

If after all moves have been searched at the reduced depth the node fails low (meaning the late move leading to it failed high) I also add back the reduction, and go through the moves again ('self deepening').

[Don]

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.

If you lose 3 ply then 15-3 is still much greater than 8.

But what you are missing is that it's actually not very common to lose several ply of "effective" search depth. You might miss ONE move which loses a ply or two (depending on how aggressive your reductions are) but you won't generally find several really hard to find move in a single combination. So yes, the first move might be very profound and difficult to see but rarely are those followed up with another move that is like this, then a 3rd like this and so on.

Think of it statistically. I have done a statistical analysis that shows that the best move is something like 98% likely to be one of the first moves. Even the first move is something well over 90%. If you use 98% as the figure of moves likely to be searched full depth (before reductions) then there is a 2% chance you will reduce the best move. Let's assume you reduce by 2 ply (most program reduce several more moves only 1 ply though.) So you lose 2 ply with only a small chance of losing 2 more ply and so on.

If that was the entire picture then that is bad, however as I showed you before you are practically doubling your depth. We typically do more than 20 ply searches in a tournament level game instead of the 10 we would be doing if were were full width. That means we can afford to lose 10 ply and still be at least as good - but MANY times we will have gained several ply in practical search depth - so the trade-off isn't even a close call.

If you don't like that, then by all means go back to the old days of brute force search and see how you do against Komodo or any of the top programs. I guarantee that they will see MUCH MORE than your program would see without those things.

If you compare all of this to how a human searches I think you will see the point even more. When Komodo is doing a 25 ply middle game search even in the crappiest lines it's looking a few ply deep - much more than any human would bother searching. So this "highly risky" search you are concerned about is really highly conservative compared to how humans do it.

[hgm]

Well, he is right in that nodes don't come from out of nowhere. To elongate the PV and the branchess close to it, other branches will have to be shortened compared to what they would be in a fixed-depth search.

The point he misses, though, is that both the fixed-depth and the LMR search are finite-depth searches that usually have all branches ending at a horizon, which hides lots of tactics from view. So it is better to shape the horizon in such a way that more of the tactics that could hurt you is in few, at the expense of much less tactics in places where you would be easily able to work around it being invisible. Which is exactly what LMR does.

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

But you will search 10 ply in about the same time as a 5 ply search without using these techniques. And you will suffer ONLY when you have a tactical position with 2 quiet moves which are not reduced and that is actually pretty rare.

And you also are not considering that it's ok to have quiet moves, just not quiet moves that are reduced. Komodo tries not to reduce important quiet moves and that is part of a good LMR implementation.

Giving up several ply of depth out of fear of missing a quiet move once in a while is guaranteeing that you will get completely crushed by programs which can see so much more deeply. If you want to talk about what you might miss, why not talk about that?

It's like running from a thief who wants to take your piggy bank away from you and then stopping to pick up a penny that is dropped. He is going to get the whole piggy bank when you stop because you were afraid he would get the penny.

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.

[Don]

A picture is worth 1000 words - so let me paint you a picture. I grabbed the first 20 positions from a tactical problems set and ran them using Komodo, the standard version and a version with LMR and Null Move pruning turned off. I ran each to 10 seconds using polyglot, min depth 3 ply.

The first entry is the brute force programs time and depth and one following is the full strength Komodo. The general trend is that the selective program will often take 1 or more ply more to solve the problem, just as you fear. However, you will find that it generally solves it much faster.

The first position is a case in point. 1 extra ply to solve and yet it solved it over 15x faster. Note also that the full width program failed to solve 2 of the problem within 10 seconds. I ran the 15th problem separately and it took 322 seconds for the brute force program to solve it finally doing a 15 ply search. However the highly selective program took an extra ply to solve it, but only required 2.48 seconds! Almost 5 1/2 minutes versus 2.48 seconds! In this case we solved it about 130x faster!

In some ways the second position is the most convincing of all because it best illustrates what you can get away with. The selective search program still solved this problem a little faster even though it took 4 additional ply! That should be pretty convincing for you.

There are a few cases where there was not a speedup and in fact the selective program took longer. Position 3 took 40% longer to solve while searching 3 ply deeper and position 16 took a whopping 6 ply more - and yet still even in these bad cases the additional time is modest compared to the incredibly impressive speedups on the majority of positions.

If you test this with more difficult problems that take a lot more ply to solve you will see the performance will be even more impressive simply because the low branching factor easily outruns the brute force program with the high branching factor. If you look hard enough you can construct or find examples which might make the brute force approach look good, but in real play with real tactics and positional play you won't have a chance to equal the performance of a highly selective searching program.

Code: Select all

 1:   OK    1 score= +2.23    pv [D=11, T=   2.00s, N=  3086k] =exf6
 1:   OK    1 score= +2.38    pv [D=12, T=   0.13s, N=   212k] =exf6

 2:   OK    2 score= +6.57    pv [D=10, T=   0.64s, N=   870k] =Rxd3
 2:   OK    2 score= +7.31    pv [D=14, T=   0.51s, N=   794k] =Rxd3

 3:   OK    3 score= +1.40    pv [D= 9, T=   0.18s, N=   218k] =Rxe5
 3:   OK    3 score= +2.05    pv [D=12, T=   0.26s, N=   323k] =Rxe5

 4:   OK    4 score= +9.19    pv [D= 6, T=   0.01s, N=    14k] =Nh5
 4:   OK    4 score=+10.52    pv [D= 8, T=   0.02s, N=    22k] =Nh5

 5:   OK    5 score= +0.59    pv [D=11, T=   1.19s, N=  1670k] =Bc5
 5:   OK    5 score= +0.44    pv [D=13, T=   0.36s, N=   544k] =Bc5 

 6:   OK    6 score= +1.91    pv [D= 6, T=   0.02s, N=    28k] =b4 
 6:   OK    6 score= +2.03    pv [D= 8, T=   0.04s, N=    48k] =b4

 7:   OK    7 score= +3.15    pv [D=11, T=   1.93s, N=  2454k] =Qh5
 7:   OK    7 score= +3.06    pv [D=10, T=   0.07s, N=   101k] =Qh5 

 8:   OK    8 score= +3.61    pv [D= 8, T=   0.02s, N=    32k] =Nf5
 8:   OK    8 score= +4.20    pv [D=10, T=   0.06s, N=    75k] =Nf5

 9:   OK    9 score= +0.91    pv [D=11, T=   1.30s, N=  1886k] =Bd3
 9:   OK    9 score= +0.90    pv [D=12, T=   0.22s, N=   325k] =Bd3

10:   OK   10 score= +1.64    pv [D= 9, T=   0.75s, N=   978k] =Qxf6+
10:   OK   10 score= +0.23    pv [D=10, T=   0.10s, N=   145k] =Qxf6+ 

11:   OK   11 score= +0.73    pv [D=10, T=   1.67s, N=  2336k] =f3 
11:   OK   11 score= +0.64    pv [D=12, T=   1.25s, N=  1822k] =f3

12:   OK   12 score= +1.14    pv [D= 7, T=   0.03s, N=    33k] =Rxh5
12:   OK   12 score= +1.63    pv [D= 5, T=   0.01s, N=     5k] =Rxh5 

13:   OK   13 score= +4.49    pv [D= 8, T=   0.07s, N=    88k] =Nxa7+
13:   OK   13 score= +5.00    pv [D= 9, T=   0.03s, N=    39k] =Nxa7+

14:   OK   14 score= +3.29    pv [D= 6, T=   0.03s, N=    29k] =Bxf6
14:   OK   14 score= +3.48    pv [D= 6, T=   0.01s, N=    12k] =Bxf6

15:   --   14 score= +1.90    pv [D= 5, T=   0.00s, N=     3k] =c4 
15:   OK   15 score= +3.79    pv [D=16, T=   2.48s, N=  3475k] =g4

16:   OK   15 score= +1.91    pv [D=11, T=   1.05s, N=  1433k] =Ngf6+ 
16:   OK   16 score= +2.79    pv [D=17, T=   2.76s, N=  4196k] =Ngf6+ 

17:   OK   16 score= -0.03    pv [D= 8, T=   0.09s, N=   115k] =Nxe6+
17:   OK   17 score= -0.35    pv [D= 9, T=   0.05s, N=    57k] =Nxe6+

18:   OK   17 score= +8.26    pv [D=11, T=   5.28s, N=  7172k] =Qb4 
18:   OK   18 score= +8.15    pv [D=12, T=   0.33s, N=   483k] =Qb4 

19:   --   17 score=+99.93    pv [D= 2, T=   0.00s, N=     0k] =Qe5 
19:   OK   19 score= +5.73    pv [D=10, T=   0.03s, N=    47k] =Re8 

20:   OK   18 score= +9.20    pv [D= 9, T=   0.38s, N=   618k] =Rd4+
20:   OK   20 score= +9.76    pv [D= 9, T=   0.06s, N=    98k] =Rd4+

[Henk]

Ok it's about being penny wise and pound foolish.

H.G. Muller explained the test he used to prevent LMR from reducing interesting moves on levels nearby the leaves of the search tree. Could you explain what tests you use in your Chess program on these levels to make LMR work. Or do you want to keep that as a secret ?

[Don]

Ok it's about being penny wise and pound foolish.

I was actually thinking about that exact phrase!

H.G. Muller explained the test he used to prevent LMR from reducing interesting moves on levels nearby the leaves of the search tree. Could you explain what tests you use in your Chess program on these levels to make LMR work. Or do you want to keep that as a secret ?

I already revealed one thing we do. We track specific refutations. We also look at moves of attacked pieces, basically calling SEE() in reverse to see if it's safe just sitting there and whether the target squares we might move to are safe if so. We have a few other tests too but the concept is that we either don't reduced at all in some of these cases or we reduce less. We do massive testing to determine what works and what doesn't.

Obviously what you are trying to do is to get the most "bang for the buck" by always making the right decision. Even though you can never succeed 100% you can still hedge your bets - which is what LMR is all about - otherwise you would prune instead of reduce. So we essentially have rules to reduce and prune in addition to rules to prevent us from going too wild.