Answers.Body: <ol>
  <li><p>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.</p></li>
  <li><p>LMR works like this:</p></li>
  </ol>
  
  <blockquote>
  <pre><code>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
      }
  }
  </code></pre>
  </blockquote>
  
  <p>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 <a href="https://github.com/official-stockfish/Stockfish/blob/master/src/search.cpp" rel="nofollow noreferrer">https://github.com/official-stockfish/Stockfish/blob/master/src/search.cpp</a>.</p>
  
  <ol start="3">
  <li><strong>If this is a late move</strong>. 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:</li>
  </ol>
  
  <blockquote>
  <pre><code>if (... moveCount &gt; 1 ...)
  </code></pre>
  </blockquote>
  
  <p>Stockfish starts LMR search if there's enough  depth to reduce and the move is not the first move in iterative deepening (<code>moveCount &gt; 1</code>). 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 <strong>fail-low</strong>. The CPW wiki suggests:</p>
  
  <blockquote>
    <p>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.</p>
  </blockquote>
  
  <p>This is just a recommendation, as Stockfish has implemented more aggressive reduction. </p>
  
  <ol start="4">
  <li><p><strong>This late move satisfies certain conditions</strong>. Generally, you don't reduce if:</p>
  
  <ul>
  <li>Tactical sequences</li>
  <li>Checks</li>
  <li>During reduced search</li>
  <li>PV node</li>
  </ul></li>
  </ol>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>This is Stockfish's implementation:</p>
  
  <blockquote>
  <pre><code>if (    depth &gt;= 3 * ONE_PLY &amp;&amp;  moveCount &gt; 1
    &amp;&amp; (!captureOrPromotion || moveCountPruning))
  </code></pre>
  </blockquote>
  
  <ol start="5">
  <li><p><strong>Find a reduced depth to search</strong>. 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:</p>
  
  <ul>
  <li>Cut node</li>
  <li>Poor SEE</li>
  <li>Quiet move</li>
  </ul></li>
  </ol>
  
  <p>Again, there's no right or wrong here. Stockfish has the following:</p>
  
  <pre><code> // Decrease/increase reduction for moves with a good/bad history
   r = std::max(DEPTH_ZERO, (r / ONE_PLY - ss-&gt;history / 20000) * ONE_PLY);
  
   if (cutNode)
       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
               &amp;&amp; type_of(pos.piece_on(to_sq(move))) != PAWN
               &amp;&amp; !pos.see_ge(make_move(to_sq(move), from_sq(move)),  VALUE_ZERO))
        r -= 2 * ONE_PLY;
  </code></pre>
  
  <p>Stockfish considers the history, node type and move type.</p>
  
  <ol start="6">
  <li><strong>Search alpha-beta with the reduced depth</strong>. This is standard. You will need to recursively search for the reduced depth you calculate. Stockfish has this:</li>
  </ol>
  
  <blockquote>
    <p>value = -search(pos, ss+1, -(alpha+1), -alpha, d, true);</p>
  </blockquote>
  
  <p>Note that the reduced depth is passed to the search function.</p>
  
  <ol start="7">
  <li><strong>Do a full-search</strong>. 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:</li>
  </ol>
  
  <blockquote>
  <pre><code>// 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 &lt; beta), otherwise let the
  // parent node fail low with value &lt;= alpha and try another move.
  if (PvNode &amp;&amp; (moveCount == 1 || (value &gt; alpha &amp;&amp; (rootNode || value &lt; beta))))
  </code></pre>
  </blockquote>
  
  <p><strong>EDIT:</strong></p>
  
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-11-22T14:46:16.300Z
Answers.Text: Thanks for the great answer, as always! I'll update the post with some questions, SFs code is tough. Just one quick: I see in a lot of engines checks like this: `if (!pvNode && ...) { do heuristic }`. I understand what  a pv node is, but as I'm not using pvs, do I need this kind of check? (for LMR for example).
Answers.UserDisplayName: Fernando
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-11-23T01:12:53.610Z
Answers.Text: @Fernando Yeah. Please post your questions.
Answers.UserDisplayName: SmallChess
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-11-23T01:14:52.677Z
Answers.Text: @Fernando I added my edits for your question.
Answers.UserDisplayName: SmallChess
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2016-11-21T09:58:53.833Z
Answers.LastActivityDate: 2016-11-23T01:14:35.910Z
Answers.LastEditDate: 2016-11-23T01:14:35.910Z
Answers.UserDisplayName: SmallChess
Body: <p>Here I am trying to improve my engine, and the next feature on the list is LMR.
  I understood the general ideia, but since I don't want to introduce bugs and the <a href="https://chessprogramming.wikispaces.com/Late+Move+Reductions" rel="nofollow noreferrer">CPW</a> on the subject has no code, how do I go about coding it inside an <code>iterative deepening</code> scheme?</p>
  <p>Here's my current code:</p>
  <pre><code>   //inside alpha-beta move loop
     //bool doReduce = false;
     int tmp_mv = moves.get(i);
  
   /* Late move reduction CPW code */
      if (depth &gt; 3 &amp;&amp; legal &gt; 3 &amp;&amp; (!atCheck) &amp;&amp;
          Move::captured(tmp_mv) == 0 &amp;&amp; Move::promoteTo(tmp_mv) == 0 &amp;&amp; 
              (mv_from != Move::from(board.searchKillers[0][board.ply]) || mv_to != Move::to(board.searchKillers[0][board.ply])) &amp;&amp;
              (mv_from != Move::from(board.searchKillers[1][board.ply]) || mv_to != Move::to(board.searchKillers[1][board.ply])) &amp;&amp;
              !oppAtCheck){
                  int reduce = legal &gt; 6 ? 2 : 1;
                  //doReduce = true;
                  score = -alphaBeta(-beta, -alpha, depth - 1 - reduce, true);
  
              //re-search
              if (score &gt; alpha)
                 score = -alphaBeta(-beta, -alpha, depth - 1, true);
          }
          else {//no LMR
              score = -alphaBeta(-beta, -alpha, depth - 1, true);
          }
  
      
  </code></pre>
  <p>This appears to be working, but I have some questions:</p>
  <ol>
  <li><p>Is the code correct?</p>
  </li>
  <li><p>CPW engine (and many others) have code like this:</p>
  <p><code> if (! isPV &amp;&amp; ... ) { apply some heuristic }</code></p>
  </li>
  </ol>
  <p>Since I'm not using <code>PVS</code>, how do I deal with this in my code? Do I need something like this:</p>
  <pre><code>//probe hashtable, at the top of alphabeta
  int hash_move = HashTable::probe(board)
  
  //inside move loop
  if (tmp_mv !=  hash_move &amp;&amp; conditions ){ apply heuristic } 
  </code></pre>
  <p>Thank you!</p>
  
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2016-11-24T01:41:59.553Z
Comments.Text: You can move your check with doReduce inside your LMR if-branch.
Comments.UserDisplayName: SmallChess
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2016-11-24T01:59:11.580Z
Comments.Text: I've changed it, see edit please.
Comments.UserDisplayName: Fernando
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2016-11-24T23:45:24.480Z
Comments.Text: If you did like `int hash_move...`, I'd just skip it and defer the implementation to when you have code to check whether you are in PV node or not. The code looks weird and not something I have seen.
Comments.UserDisplayName: SmallChess
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2016-11-25T12:24:49.973Z
Comments.Text: I didn't, my search code is the same as the Vice engine + LMR and futlity prunning like the CPW engine. I need to implement pvs I guess, the engine is playing at 2050 - 2100 ELO.
Comments.UserDisplayName: Fernando
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2016-11-25T12:34:47.690Z
Comments.Text: What puzzles me is that I've seen people talking about engines playing at 2400+ with only material + passed pawns + king safety evaluation.
Comments.UserDisplayName: Fernando
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2016-11-25T14:09:19.110Z
Comments.Text: I don't think so... Are they open source?
Comments.UserDisplayName: SmallChess
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2016-11-25T14:40:05.780Z
Comments.Text: I guess so, I was reading some posts at talkchess.com, I'll try to get the links. They must have a good prunning scheme.
Comments.UserDisplayName: Fernando
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2016-11-25T16:30:26.117Z
Comments.Text: http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=445193&t=42065
Comments.UserDisplayName: Fernando
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2016-11-28T01:06:26.967Z
Comments.Text: I've sent you an email. Let's talk by emails.
Comments.UserDisplayName: SmallChess
Tags: <engines><programming><computer-chess>
Title: Implementing Late Move Reduction (LMR) inside iterative deepening
ThreadText: # Implementing Late Move Reduction (LMR) inside iterative deepening
  
  (Asked by: username_0 on 2016-11-16)
  
  Here I am trying to improve my engine, and the next feature on the list is LMR.
  I understood the general ideia, but since I don't want to introduce bugs and the CPW on the subject has no code, how do I go about coding it inside an iterative deepening scheme?
  Here's my current code:
     //inside alpha-beta move loop
     //bool doReduce = false;
     int tmp_mv = moves.get(i);
  
   /* Late move reduction CPW code */
      if (depth > 3 && legal > 3 && (!atCheck) &&
          Move::captured(tmp_mv) == 0 && Move::promoteTo(tmp_mv) == 0 && 
              (mv_from != Move::from(board.searchKillers[0][board.ply]) || mv_to != Move::to(board.searchKillers[0][board.ply])) &&
              (mv_from != Move::from(board.searchKillers[1][board.ply]) || mv_to != Move::to(board.searchKillers[1][board.ply])) &&
              !oppAtCheck){
                  int reduce = legal > 6 ? 2 : 1;
                  //doReduce = true;
                  score = -alphaBeta(-beta, -alpha, depth - 1 - reduce, true);
  
              //re-search
              if (score > alpha)
                 score = -alphaBeta(-beta, -alpha, depth - 1, true);
          }
          else {//no LMR
              score = -alphaBeta(-beta, -alpha, depth - 1, true);
          }
  
      
  
  This appears to be working, but I have some questions:
  
  Is the code correct?
  
  CPW engine (and many others) have code like this:
   if (! isPV && ... ) { apply some heuristic }
  
  
  Since I'm not using PVS, how do I deal with this in my code? Do I need something like this:
  //probe hashtable, at the top of alphabeta
  int hash_move = HashTable::probe(board)
  
  //inside move loop
  if (tmp_mv !=  hash_move && conditions ){ apply heuristic } 
  
  Thank you!
  
  **Tags:** engines, programming, computer-chess
  
  > **Comments:**
  > **username_1**: You can move your check with doReduce inside your LMR if-branch.  
  > **username_0**: I've changed it, see edit please.  
  > **username_1**: If you did like `int hash_move...`, I'd just skip it and defer the implementation to when you have code to check whether you are in PV node or not. The code looks weird and not something I have seen.  
  > **username_0**: I didn't, my search code is the same as the Vice engine + LMR and futlity prunning like the CPW engine. I need to implement pvs I guess, the engine is playing at 2050 - 2100 ELO.  
  > **username_0**: What puzzles me is that I've seen people talking about engines playing at 2400+ with only material + passed pawns + king safety evaluation.  
  > **username_1**: I don't think so... Are they open source?  
  > **username_0**: I guess so, I was reading some posts at talkchess.com, I'll try to get the links. They must have a good prunning scheme.  
  > **username_0**: http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=445193&t=42065  
  > **username_1**: I've sent you an email. Let's talk by emails.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2016-11-21. Score: 5 | Accepted answer
  
  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
  Checks
  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);
  
   if (cutNode)
       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))))
  
  
  EDIT:
  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.
  
  > **Comments:**
  > **username_0**: Thanks for the great answer, as always! I'll update the post with some questions, SFs code is tough. Just one quick: I see in a lot of engines checks like this: `if (!pvNode && ...) { do heuristic }`. I understand what  a pv node is, but as I'm not using pvs, do I need this kind of check? (for LMR for example).  
  > **username_1**: @username_0 Yeah. Please post your questions.  
  > **username_1**: @username_0 I added my edits for your question.  
  
  ---
  
  