Implementing Late Move Reduction (LMR) inside iterative deepening 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 &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);
        }

    

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 &amp;&amp; ... ) { 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 &amp;&amp; conditions ){ apply heuristic } 

Thank you!
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 &gt; 1 ...)



Stockfish starts LMR search if there's enough  depth to reduce and the move is not the first move in iterative deepening (moveCount &gt; 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 &gt;= 3 * ONE_PLY &amp;&amp;  moveCount &gt; 1
  &amp;&amp; (!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-&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;


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 &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))))



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.