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.

This should be:

If move ordering is not perfect and alfa-beta search algorithm is used, then the search depth of at least one move will be reduced while it shouldn't, if no fail-high is encountered before that move is reached.

So how big is the chance that a fail-high is encountered before a move is reduced by LMR ? At the root level there is never a fail-high when you start with alfa = -infinity, beta = infinity.

[hgm]

The problem is that you want things to be perfect. But they never will be, if you are not solving mate-in-N problems.

So you occasionally might reduce a move that did not deserve it... So what? The nodes you save on its search go towards searching another move that did not deserve it, and often enough you see something important there then that you would otherwise not have seen.

'Perfection' in the sense that you can 100% accurately search exactly the tree you planned to search isn't worth anything. Because what you planned to search is no good anyway, and will miss zillions of essential tactical shots. You are bit like someone who wants to hire a master-painter forger to copy a painting made by a Chimpanzee. While in fact it would be good enough to just splash the paint on the canvas, and no one would see the difference!

[Henk]

The problem is that you want things to be perfect. But they never will be, if you are not solving mate-in-N problems.

So you occasionally might reduce a move that did not deserve it... So what? The nodes you save on its search go towards searching another move that did not deserve it, and often enough you see something important there then that you would otherwise not have seen.

'Perfection' in the sense that you can 100% accurately search exactly the tree you planned to search isn't worth anything. Because what you planned to search is no good anyway, and will miss zillions of essential tactical shots. You are bit like someone who wants to hire a master-painter forger to copy a painting made by a Chimpanzee. While in fact it would be good enough to just splash the paint on the canvas, and no one would see the difference!

I talked about the case that move ordering is far from perfect.

[hgm]

Well, so you gain by making it better. As always. With LMR you would gain even more by that than without, because the better your ordering, the more you can reduce the really late ones without measurable effects..

[Henk]

The problem is that you want things to be perfect. But they never will be, if you are not solving mate-in-N problems.

So you occasionally might reduce a move that did not deserve it... So what? The nodes you save on its search go towards searching another move that did not deserve it, and often enough you see something important there then that you would otherwise not have seen.

'Perfection' in the sense that you can 100% accurately search exactly the tree you planned to search isn't worth anything. Because what you planned to search is no good anyway, and will miss zillions of essential tactical shots. You are bit like someone who wants to hire a master-painter forger to copy a painting made by a Chimpanzee. While in fact it would be good enough to just splash the paint on the canvas, and no one would see the difference!

I talked about the case that move ordering is far from perfect.

So does it make sense to apply LMR when moves are ordered random(ly) ?

[Henk]

So you occasionally might reduce a move that did not deserve it... So what? The nodes you save on its search go towards searching another move that did not deserve it, and often enough you see something important there then that you would otherwise not have seen.
difference!

The search algorithm should prevent that too often the nodes go towards moves that have already been searched deep enough.

[Don]

The problem is that you want things to be perfect. But they never will be, if you are not solving mate-in-N problems.

So you occasionally might reduce a move that did not deserve it... So what? The nodes you save on its search go towards searching another move that did not deserve it, and often enough you see something important there then that you would otherwise not have seen.

'Perfection' in the sense that you can 100% accurately search exactly the tree you planned to search isn't worth anything. Because what you planned to search is no good anyway, and will miss zillions of essential tactical shots. You are bit like someone who wants to hire a master-painter forger to copy a painting made by a Chimpanzee. While in fact it would be good enough to just splash the paint on the canvas, and no one would see the difference!

I talked about the case that move ordering is far from perfect.

So does it make sense to apply LMR when moves are ordered random(ly) ?

I don't think you can get any benefit with random ordering, but you might still get a tiny benefit if you try several moves first and do not reduce captures, checks, out of checks - but I cannot vouch for that.

However if your order captures correctly and use killers and hash table moves the way you should you already have good enough move ordering that you could probably still get a small benefit.

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

This should be:

If move ordering is not perfect and alfa-beta search algorithm is used, then the search depth of at least one move will be reduced while it shouldn't, if no fail-high is encountered before that move is reached.

So how big is the chance that a fail-high is encountered before a move is reduced by LMR ? At the root level there is never a fail-high when you start with alfa = -infinity, beta = infinity.

I did a study on this once, where I basically turned off LMR and simply noted the move number of the BEST move, whether it was a cutoff or not and kept statistics on it.

The numbers were impressive. The first move was the best move a surprisingly high number of times but if you combined the first N it was ridiculously high. And there was a nice progression downward, so that what the first move didn't catch, the second move caught "most" of the time, then the 3rd move and so on.

I don't have the numbers but they are buried in my email to Larry and this was a few years ago. But it is trivial to reproduce this study, why don't you give it a try?

I get the impression that you want this to be perfect and that you think it's a complete failure if you reduce the wrong move. If you are thinking that way then forget about building a strong program because EVERYTHING in computer chess is about amortized risk. If you extend a move, you are wasting time - how do you know you are extending the right move? Check extensions slow a chess program down and could prevent you from seeing tactics that don't involve any checks, what do you do about that? What about null move pruning? It's amortized risk.

What about your evaluation function itself? Do you have mobility? What if mobility is completely irrelevant for some piece? Once we played against Joel Benjamin in the hotel room (years ago with a different program) and my program place the rook on the 7th rank when it was useless. Should I remove the rook to the 7th bonus? (These days it's a much better rule, but it's still broken as are all positional heuristics in chess engines.)

The only thing you can reasonably do it to simply TRY things and see if they work. Take an idea that seems to make sense and TRY it. If it doesn't work then think about what it's weakeness are and how it can be improved. But the number one consideration is that everything in computer chess is a calculated risk, especially when it comes to pruning and reductions.

Incidentally, it's that way with people too. They miss things because their search is highly directed and highly selective. Do you think they should stop using a selective search?

Don

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

This should be:

If move ordering is not perfect and alfa-beta search algorithm is used, then the search depth of at least one move will be reduced while it shouldn't, if no fail-high is encountered before that move is reached.

So how big is the chance that a fail-high is encountered before a move is reduced by LMR ? At the root level there is never a fail-high when you start with alfa = -infinity, beta = infinity.

I did a study on this once, where I basically turned off LMR and simply noted the move number of the BEST move, whether it was a cutoff or not and kept statistics on it.

The numbers were impressive. The first move was the best move a surprisingly high number of times but if you combined the first N it was ridiculously high. And there was a nice progression downward, so that what the first move didn't catch, the second move caught "most" of the time, then the 3rd move and so on.

I don't have the numbers but they are buried in my email to Larry and this was a few years ago. But it is trivial to reproduce this study, why don't you give it a try?

I get the impression that you want this to be perfect and that you think it's a complete failure if you reduce the wrong move. If you are thinking that way then forget about building a strong program because EVERYTHING in computer chess is about amortized risk. If you extend a move, you are wasting time - how do you know you are extending the right move? Check extensions slow a chess program down and could prevent you from seeing tactics that don't involve any checks, what do you do about that? What about null move pruning? It's amortized risk.

What about your evaluation function itself? Do you have mobility? What if mobility is completely irrelevant for some piece? Once we played against Joel Benjamin in the hotel room (years ago with a different program) and my program place the rook on the 7th rank when it was useless. Should I remove the rook to the 7th bonus? (These days it's a much better rule, but it's still broken as are all positional heuristics in chess engines.)

The only thing you can reasonably do it to simply TRY things and see if they work. Take an idea that seems to make sense and TRY it. If it doesn't work then think about what it's weakeness are and how it can be improved. But the number one consideration is that everything in computer chess is a calculated risk, especially when it comes to pruning and reductions.

Incidentally, it's that way with people too. They miss things because their search is highly directed and highly selective. Do you think they should stop using a selective search?

Don

If move ordering is far from perfect, which normally is the case, and alfa-beta search algorithm is used, then the search depth of some moves will be reduced while they shouldn't, if no fail-high is encountered before these move are reached.


Trial and Error method is an inefficient method of doing things if there are a lot of combinations.

If possible it's better to use a search direction [or gradient?].

[tpetzke]

Don,

I think you are wasting you're time here. We all know that and Henk does not listen.

Thomas ...