Differences

This shows you the differences between two versions of the page.

--- chess:programming:late_move_reduction [2022/01/06 19:05] – created peter
+++ chess:programming:late_move_reduction [2022/01/06 20:56] (current) – peter
@@ Line 3: / Line 3: @@
 Intended for use in conjunction with move ordering.
-Since strong moves are searched first, it stands to reason that later moves in the list are not as good.
+  * Since strong moves are searched first, it stands to reason that later moves in the list are not as good.
+  * We therefore reduce the search by one ply when searching later moves, reducing the amount of effort spent on moves we expect to be bad.
-We therefore reduce the search by one ply when searching later moves, reducing the amount of effort spent on moves we expect to be bad.
 The starting point of LMR varies between programs, but generally the first four or five moves are searched fully and any moves after this are reduced.
@@ Line 13: / Line 12: @@
 ----
+A late move (as opposed to an early move) is a move that gets sorted late in the list of moves we are about to search.
+  * These moves should rarely produce any good results.
+  * For example the latest moves of them all, the losing captures, need very specific features of the position to be successful.
+    * Things like a sacrifice exposing the enemy king.
+  * But in the general case these moves will just be bad.
+The idea of the late move reductions is since we predict these moves will not produce any good results we might as well reduce the time we spend on them.
+  * One neat feature with LMR is that it considers the moves that are likely to fail low, i.e. moves that are not good enough, as opposed to null-moves that tries to find moves that fail high.
+  * Since these two techniques operates in different ends of the spectrum they are not likely to overlap, which many other reducing techniques are prone to do.
+----
+===== An example approach =====
+Just before the search is about to go into the PVS search.
+<code cpp>
+if (movesSearched >= 4 &&
+    ply >= 3 &&
+    Move.capture(moves[i]) == 0 &&
+    !isInCheck(board))
+{
+  eval=-alphaBeta(board,ply-2,-alpha-1,-alpha,true,depth+1);
+}
+else
+  eval = alpha +1;
+if (eval > alpha) // Continue with PVS search
+</code>
+<WRAP info>
+**NOTE:** This starts with a few conditions for when we are allowed to reduce moves.
+  * Then we do a search with a minimal window (since we are only interested if the move fails low or not) using a reduced depth.
+  * We reduce the depth with 1 extra ply (a usual search is ply-1).
+  * If the eval comes back lower than alpha we are satisfied with this result and can be quite confident that the move was indeed a poor one.
+  * If the search however comes back higher than alpha, something is fishy and we have to continue with the ordinary search at regular depth.
+</WRAP>
+----
+===== When to reduce? =====
+The main idea comes with the first condition; **movesSearched >= 4**.
+  * Start with searching all the likely contenders for best move to full depth.
+    * These include:
+      * The hash move (by far the most common best move).
+      * Good/Equal captures (if there are any).
+      * Killer moves.
+      * and possibly one or two of the best non-captures.
+  * In general 3-4 moves is a good amount of moves searched to full depth before starting to reduce.
+----
+===== What should be reduced among the late moves =====
+Some types of moves that should probably not be reduced:
+  * **Checks**, and any other moves that the engine extends.
+    * If we reduce an extended move, the extension effect is cancelled.
+  * **Captures**, unless they are losing, and maybe not even then.
+  * **Promotions**, at least if they are Queen promotions.
+These are the obvious ones, there are several other techniques for determining if a move is safe to reduce.
+  * Moves that historically failed high might not be good to reduce.
+  * Neither might moves that raises the static evaluation above alpha; or
+  * Moves that can be determined to cause some sort of threat.
+    * These techniques are however a bit more tricky to implement.
+There are endless possibilities how to handle the reductions:
+  * You could for example try to reduce more than one ply or skip the research when a move comes back above alpha.
+----
+Simple late move reduction.
+  * Every move after the first four are reduced with one ply if they were not a capture or a check
+----
 [[Chess:Programming:Late Move Reduction|Late Move Reduction]]