Continuing with this series on Modern Chess Engines, in my previous post Chess Engines : Pruning, I omitted one topic because I didn't understand the explanation. Again relying on chessprogramming.wikispaces.com for definitions:-
Late Move Reductions (LMR) Or its version known as History Pruning and History Reductions, save search by reducing moves that are ordered closer to the end of likely fail-low nodes. Typically, most schemes search the first few moves (say 3-4) at full depth, then if no move fails high, many of the remaining moves are reduced in search depth.
Fail-low, fail-high -- what's that all about? First, it's useful to insert a reminder that this pruning is being done on the tree of variations that flow from the current position. Here's a diagram.
From Wikipedia: Alpha–beta pruning
Chess engines are as much about constructing the tree efficiently as they are about evaluating the chess content of specific positions.
Fail-Low A fail-low indicates that this position was not good enough for us. We will not reach this position, because we have some other means of reaching a position that is better. We will not make the move that allowed the opponent to put us in this position.
Fail-High A fail-high indicates that the search found something that was "too good". What this means is that the opponent has some way, already found by the search, of avoiding this position, so you have to assume that they'll do this. If they can avoid this position, there is no longer any need to search successors, since this position won't happen
In other words, LMR means that if a move isn't looking particularly interesting, don't examine every subsequent response. Look at a few responses in depth, then look at the rest quickly. If nothing special is found, move on. Techniques like this are one reason that engines are able to calculate to amazing ply depths that seem to defy mathematical common sense.
Getting back to Stockfish, the engine that triggered this series of posts, there's a good discussion by Tord Romstad titled An Introduction to Late Move Reductions. The page disappeared while I was preparing this post ('This domain has expired'), but lives on in Archive.org.