Chess Engines : LMR
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.
Posts
1 comment:
As far as I've tested in my engine(much weaker than stockfish of course, but around 2200), LMR by just reducing depths after moves 3,4 or even 6, greatly increases search depth but reduces actual playing strength as well. It's effective to only apply LMR at likely ALL-nodes(ones in which each move will fail low). The logic is that if the first few moves, the captures, promotions and heuristically sound moves(like killer moves) don't improve alpha, the node is likely an ALL-node so LMR can be applied without loss of accuracy(unless in check of course).
Although I believe stockfish applies it just about everywhere reducing the reductions under the above conditions.
Post a Comment