Is LMR Sound.

[Henk]

If you apply LMR after only move 25 then it probably will be safe but you won't gain much CPU time. If you apply LMR earlier say after move 10 or some say 4, the chances of missing best moves are much bigger.

But also if in one turn you have chance of missing the best move is 5%, then in 20 turns you get a chance of 1 - power(0.95, 20) of missing a best move. But now I miss my calculator.


Things gets worse when LMR misses the best move and there was only one good move. So it plays a bad move, or even a move which loses the game.

[AlvaroBegue]

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.

Examining a minimax tree using alpha-beta with the worst possible ordering takes time proportional to (branching_factor ^ depth). The same thing with the best possible ordering takes time proportional to (branching_factor ^ (depth/2)) or, if you prefer, (sqrt(branching_factor)^depth). In practice you'll get something in between. By improving the order you get an asymptotically faster algorithm, at the cost of a small reduction in nodes searched per second.

My experience writing an alpha-beta searchers from scratch and then working on improving move ordering is consistent with the above analysis.

[hgm]

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.

The point is that a non-capture, which also doesn't threaten anything, is very unlikely to gain anything at all. You would not LMR it if it were a capture, and most engines would also not LMR it if it is a non-capture that would refute a following null move by a move with the same piece ('tactically connected').

Otherwise it is just playing the probabilities. You sacrifice some depth on moves that are very unlikely to be any good, so you can spend the nodes you save on moves that are much more likely to be good. That should be a winner.

[Steve Maughan]

Hi Henk,

(...) If that move was the best move, than the program probably misses that best move. So the play of your program gets worse (...)

Welcome to the mystical world of chess programming (which is as much of an art as a science)!

It sounds as if you're at the early stages of wrapping your head around the fascinating subject of chess programming (beware - it's addictive and there are few who manage to go "cold turkey").

I think the one point which may be helpful is virtually all techniques uses to improve the search add potential errors.

Null move move is a good example. It works well as long as there isn't zugzwang, in which case it fails horribly. The good news is zugzwang is rare.

SEE captures and even QSearch all add potential errors. The same goes for LMR. It adds errors but the gain in terms of extra search depth more than compensates.

Best,

Steve

[Henk]

The problem is can a program detect candidate moves for LMR. If a move is a dangerous quiet move. For example freeing an open line for a rook which introduces a severe threat two moves later. Such a move should be extended not reduced.

[hgm]

One way to attempt that is exempt a few moves with the best history scores from LMR. Presumably if opening the line is useful, you would have tried it succesfully in other positions closer to the root (where the depth was enough to see the gain) as well, which would have upped the history score.

If this occurs at the lowest depth where opening the file in a dangerous way is possible, then this wouldn't help. But you should accept that in a finite-depth search there will be a horizon, hiding relevant tactics from view. This would just be an example of the zillions of things that are beyond the horizon. Search is still the most efficient way to find such things, you just have to search deeper.

[AlvaroBegue]

The problem is can a program detect candidate moves for LMR. If a move is a dangerous quiet move. For example freeing an open line for a rook which introduces a severe threat two moves later. Such a move should be extended not reduced.

As others have pointed out, LMR is heuristic in nature, so there will be situations where it will be wrong. What happens in those cases is that you need to search to a higher nominal depth to find the correct move. But even in those cases, getting to the higher nominal depth with LMR often takes less time than getting to the lower nominal depth without LMR, so it's still a win.

[Don]

The problem is can a program detect candidate moves for LMR. If a move is a dangerous quiet move. For example freeing an open line for a rook which introduces a severe threat two moves later. Such a move should be extended not reduced.

The answer is yes. HG mentioned connected moves and Komodo has a few rules to prevent or minimize the impact of moves which might cause trouble.

But most of these rules we apply only late in the tree (near end nodes) when LMR is not very deep. When the search is quit deep many rules are counter productive. For example in LMR we do not reduce moves of pieces that are attacked on the last several ply but we don't find that useful at really deep nodes so we just reduce them. It may be that if these moves are really important they are not near the end of the list anyway perhaps.

[hgm]

But most of these rules we apply only late in the tree (near end nodes) when LMR is not very deep. When the search is quit deep many rules are counter productive.

That makes sense. Static rules are only able to recognize very shallow tactics with any accuracy. 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.

[Henk]

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 ?