LMR is a general technique and there is no rule on the best implementation. That is why chess programming is hard, because you are expected to come up with your own interpretation and implementation.
LMR works like this:
if (this is a late move)
if (this late move satisfies certain conditions)
Find a reduced depth to search
Search alpha-beta with the reduced depth
Do a full-search if the result is greater than alpha
LMR is easy to understand but hard to master. Let's go through one by one. We will use Stockfish for our example. The code is https://github.com/official-stockfish/Stockfish/blob/master/src/search.cpp.
- If this is a late move. What is a late move? We know the first move in iterative deepening is definitely not a late move, because we assume the first move is most likely the best move. Stockfish defines a late move like this:
if (... moveCount > 1 ...)
Stockfish starts LMR search if there's enough depth to reduce and the move is not the first move in iterative deepening (
moveCount > 1). There is no right or wrong answer here, in my engine I refused to reduce for the first two moves and I like my idea. Your implementation might be different, but you should always find a move that you think most likely to fail-low. The CPW wiki suggests:
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.
This is just a recommendation, as Stockfish has implemented more aggressive reduction.
This late move satisfies certain conditions. Generally, you don't reduce if:
- Tactical sequences
- During reduced search
- PV node
You should consider to minmise reduction for PV nodes. The PV nodes form the most likely sequence of moves your engine reports, thus it's important to be as precise as possible.
You should also be careful if the move is a capture, because it's easier to make a search horizon mistake if you reduce the move too much.
This is Stockfish's implementation:
if ( depth >= 3 * ONE_PLY && moveCount > 1
&& (!captureOrPromotion || moveCountPruning))
Find a reduced depth to search. This is hard because nobody knows how much to reduce. You'll need to play hundreds and hundreds of games to tune your parameter. Generally, you reduce more if:
- Cut node
- Poor SEE
- Quiet move
Again, there's no right or wrong here. Stockfish has the following:
// Decrease/increase reduction for moves with a good/bad history
r = std::max(DEPTH_ZERO, (r / ONE_PLY - ss->history / 20000) * ONE_PLY);
r += 2 * ONE_PLY;
// Decrease reduction for moves that escape a capture. Filter out
// castling moves, because they are coded as "king captures rook" and
// hence break make_move().
else if ( type_of(move) == NORMAL
&& type_of(pos.piece_on(to_sq(move))) != PAWN
&& !pos.see_ge(make_move(to_sq(move), from_sq(move)), VALUE_ZERO))
r -= 2 * ONE_PLY;
Stockfish considers the history, node type and move type.
- Search alpha-beta with the reduced depth. This is standard. You will need to recursively search for the reduced depth you calculate. Stockfish has this:
value = -search(pos, ss+1, -(alpha+1), -alpha, d, true);
Note that the reduced depth is passed to the search function.
- Do a full-search. This is also standard. If your alpha-beta returns something greater than your lower bound (alpha), you have no choice but to do a full-search. If your LMR implementation is correct, the benefit you gain by reducing should outweight the cost of doing a full-search. Otherwise, LMR is a liability. Stockfish has this:
// For PV nodes only, do a full PV search on the first move or after a fail
// high (in the latter case search only if value < beta), otherwise let the
// parent node fail low with value <= alpha and try another move.
if (PvNode && (moveCount == 1 || (value > alpha && (rootNode || value < beta))))
You don't have to add a check to PV node if you don't want to. But in chess programming, there are lots of things you should and should not be done in PV nodes. For example, we typically don't reduce for PV nodes. Your engine might lose rating if you don't check.