Is LMR Sound.

[Henk]

Actually I do not understand LMR. LMR depends on good move ordering. But good move ordering costs a lot of CPU Time. If move ordering is not perfect than the search depth of at least one move will be reduced while it shouldn't. If that move was the best move, than the program probably misses that best move. So the play of your program gets worse. Why is it that some say that LMR improved the rating of their chess program with 100 ELO points?

[Don]

Actually I do not understand LMR. LMR depends on good move ordering. But good move ordering costs a lot of CPU Time. If move ordering is not perfect than the search depth of at least one move will be reduced while it shouldn't. If that move was the best move, than the program probably misses that best move. So the play of your program gets worse. Why is it that some say that LMR improved the rating of their chess program with 100 ELO points?

It's very sound, but how it's implemented is pretty important. Just doing any old thing probably won't buy you much. But I can say it's worth a lot in Komodo.

Don

[hgm]

Good move ordering saves a lot of CPU time!

[mcostalba]

Actually I do not understand LMR. LMR depends on good move ordering. But good move ordering costs a lot of CPU Time. If move ordering is not perfect than the search depth of at least one move will be reduced while it shouldn't. If that move was the best move, than the program probably misses that best move. So the play of your program gets worse. Why is it that some say that LMR improved the rating of their chess program with 100 ELO points?

LMR works even without move ordering.

You have written a correct sentence: "LMR depends on good move ordering."

But you have not fully understood what have you wrote: you read "depends" as "requires" but are 2 different concepts.

...you have also written a nonsense: "So the play of your program gets worse".

Worse of what ?

P.S: As a side note I'd change the title in "Can someone explain me why LMR works?" it seems more in line with the rest of the post IMHO.

[Henk]

Does LMR work because the search depth increases which compensates the chance of missing the best moves. Or is it because playing the best moves is not that important, if it plays only good moves that is good enough. So why is LMR sound.

[Don]

Does LMR work because the search depth increases which compensates the chance of missing the best moves. Or is it because playing the best moves is not that important, if it plays only good moves that is good enough. So why is LMR sound.

There is quite a nice depth increase for the additional risk. The principle of LMR was very nicely written up here:

http://www.glaurungchess.com/lmr.html

The moves that are reduced are still searched, so you have a move that is not very likely to be best still being searched just in case, so the risk is not as much as one might expect.

[Henk]

Ok, move ordering saves time but the sort operation on moves costs time. So somewhere there must be balance. For example if the first move is the best move than sorting the remaining moves makes no sense.

[Henk]

I meant worse than playing without LMR. But I cannot prove that. I can only say that it misses the best move.

[mcostalba]

LMR works because after you have tried 25 moves without success (without a cut-off) and you have just another 5 moves remaining the chance that among those five moves there is a successful one is very low (and is low even with unordered moves).

So if you decide to reduce the search depth of those moves the chance you miss to detect a fail high is very low. Instead you have saved some work.

Note that to miss to detect a fail-high you need both conditions to happen

1) A cut-off moves happens to be at the moves tail

2) This moves cut-off only if searched at full depth

[Henk]

Well if LMR checks the move on level n which gives a value of losing 0.1 pawn but on a level deeper the move wins a piece, LMR will think that the move is losing 0.1 pawn, so it misses that move.