Troubles with LMR

[KhepriChess]

I'm not sure how to word this, so please forgive me if I've missed something important or obvious...

I've been working on a rewrite on my engine. It's in working condition and plays just fine. I've been trying to get LMR added, but nothing I do adds any improvement; Every change I try results in a small loss at best. I've looked at and tried things from the CPW and various engines. I've played around with most of the factors I can (as in, which moves to reduce and which not to). All that to say, I'm not just copying code from somewhere and wondering why it's not working. I've spent a few weeks, on and off, messing around with LMR at this point.

In general, I'm doing something like so (though I've also tried completely different blocks than the below):

Code: Select all

if (legalMoves === 0) {
    // Full search
    score = score = -this.Negamax(depth - 1, ply + 1, -beta, -alpha, childPVMoves);
}
else {
    let R = 0;
    
    // I've tried different things in this `if` condition
    if (depth >= lmrDepthLimit && legalMoves >= lmrLegalMovesLimit && moveIsNotCapture && moveIsNotPromotion) {
        // Reduced search
        score = -this.Negamax(depth - 1 - R, ply + 1, -alpha - 1, -alpha, childPVMoves);
        
        if (score > alpha) {
            // Full search
            score = -this.Negamax(depth - 1, ply + 1, -beta, -alpha, childPVMoves);
        }
}

Am I missing something that should be more obvious here? Do I just need to keep trying things until I find the one thing that works? Could LMR just not work and this is all futile?

[pedrojdm2021]

i think your LMR code is not complete, i think it is missing something,

this is a good start point for LMR:
https://web.archive.org/web/20150212051 ... m/lmr.html

please check that code and then you'll know what you are missing, good luck

[KhepriChess]

i think your LMR code is not complete, i think it is missing something,

this is a good start point for LMR:
https://web.archive.org/web/20150212051 ... m/lmr.html

please check that code and then you'll know what you are missing, good luck

I didn't include the entirety of my negamax function, since most of it isn't explicitly relevant to the LMR portion. I have seen that link and I have tried exactly what's shown there, to no avail. There are other implementations that vary (like omitting the "else value = alpha + 1" part).

That being said, I finally managed to have a test finish that resulted in a (potentially small) positive net gain. Basically reduce based on depth, move count, not in check, and not PV node only (so no "do not reduce" captures and promotions). And then used the "double log" function from: https://www.talkchess.com/forum3/viewtopic.php?t=65273. I'm messing around with the constant, but so far I've gotten a 21 +/- 14 Elo result in SPRT testing.

[emadsen]

Am I missing something that should be more obvious here? Do I just need to keep trying things until I find the one thing that works? Could LMR just not work and this is all futile?

LMR = Late Move Reductions. How are you defining "late"?

In other words, have you implemented a history heuristic? Are you incrementing a history score for quiet moves that cause a beta cutoff? And decrementing a history score for quiet moves that failed to cause a beta cutoff when an even later quiet move did? Usually via history[piece][toSquare]. Then sorting quiet moves by history score descending?

In my experience, LMR doesn't add much value unless it's paired with history heuristic + move sorting. History + sorting defines when a move is considered a late move. That is, a move unlikely to cause a beta cutoff, and therefore, may be searched to a shallower depth than early moves.

[KhepriChess]

Am I missing something that should be more obvious here? Do I just need to keep trying things until I find the one thing that works? Could LMR just not work and this is all futile?

LMR = Late Move Reductions. How are you defining "late"?

In other words, have you implemented a history heuristic? Are you incrementing a history score for quiet moves that cause a beta cutoff? And decrementing a history score for quiet moves that failed to cause a beta cutoff when an even later quiet move did? Usually via history[piece][toSquare]. Then sorting quiet moves by history score descending?

In my experience, LMR doesn't add much value unless it's paired with history heuristic + move sorting. History + sorting defines when a move is considered a late move. That is, a move unlikely to cause a beta cutoff, and therefore, may be searched to a shallower depth than early moves.

Thanks. That's given me some info I missed. I do have a history heuristic, "history[side2move][move.from][move.to] += depth*depth;" when the move score is >= beta or > alpha, as long as the move is not a capture move. From your comment though, I was missing decrementing the history score. I'll add that and see how things go.

And my move sorting goes: pv -> captures (with mvv-lva) -> killers -> history

[emadsen]

From your comment though, I was missing decrementing the history score. I'll add that and see how things go.

And my move sorting goes: pv -> captures (with mvv-lva) -> killers -> history

I think you'll have more success with history[piece][move.to] than with history[side2move][move.from][move.to]. Meaning, white bishop to d5, black rook to e8, etc.

You still should benefit from increment only... Also, I encourage you to experiment with reducing by 2, 3, or more ply the later the quiet move is in the move list... One aspect I'm uncertain of (meaning, I have no hard data) is how effective LMR is with a simplistic evaluation. My hunch is LMR is more effective with a more sophisticated evaluation that understands passed pawns, piece mobility, king safety, etc that can cause large, non-linear changes in static score.

Another tricky issue is ageing history scores, either prior to each search, each search iteration, or updating the history score "with decay" as is done in the Ethereal engine.

[KhepriChess]

From your comment though, I was missing decrementing the history score. I'll add that and see how things go.

And my move sorting goes: pv -> captures (with mvv-lva) -> killers -> history

I think you'll have more success with history[piece][move.to] than with history[side2move][move.from][move.to]. Meaning, white bishop to d5, black rook to e8, etc.

You still should benefit from increment only... Also, I encourage you to experiment with reducing by 2, 3, or more ply the later the quiet move is in the move list... One aspect I'm uncertain of (meaning, I have no hard data) is how effective LMR is with a simplistic evaluation. My hunch is LMR is more effective with a more sophisticated evaluation that understands passed pawns, piece mobility, king safety, etc that can cause large, non-linear changes in static score.

Another tricky issue is ageing history scores, either prior to each search, each search iteration, or updating the history score "with decay" as is done in the Ethereal engine.

I've tried doing "history[piece][move.to]" instead but it really doesn't make any difference for me (I think because it has to do a little extra work to parse out the "piece" part of that line).

To your second point, my evaluation is pretty simplistic. Just PST and some additional pawn evaluations right now.

Regarding the aging history scores, that one thing that I've seen used but I've never found an explanation as to why or what it is for. Is history aging something that's required for it to work? Or is it just an "add-on" for an additional benefit? Does it just reduce the score (by some factor) given to older history moves?

[emadsen]

Regarding the aging history scores, that one thing that I've seen used but I've never found an explanation as to why or what it is for. Is history aging something that's required for it to work? Or is it just an "add-on" for an additional benefit? Does it just reduce the score (by some factor) given to older history moves?

How many good moves from the position at move 20 are still good moves (or even possible or legal) at move 50? Wouldn't the board look completely different? That's the idea.