5

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:

  1. Is the code correct?
  2. 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!

  • You can move your check with doReduce inside your LMR if-branch. – SmallChess Nov 24 '16 at 1:41
  • I've changed it, see edit please. – Fernando Nov 24 '16 at 1:59
  • 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. – SmallChess Nov 24 '16 at 23:45
  • 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. – Fernando Nov 25 '16 at 12:24
  • What puzzles me is that I've seen people talking about engines playing at 2400+ with only material + passed pawns + king safety evaluation. – Fernando Nov 25 '16 at 12:34
2
  1. 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.

  2. 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.

  1. 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.

  1. 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))
  1. 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.

  1. 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.

  1. 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.

  • 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). – Fernando Nov 22 '16 at 14:46
  • @Fernando Yeah. Please post your questions. – SmallChess Nov 23 '16 at 1:12
  • @Fernando I added my edits for your question. – SmallChess Nov 23 '16 at 1:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.