What's Your Engine's Maximum LMR Reduction?

[Steve Maughan]

I'm working on improving Maverick's LMR.

Suppose you have a depth of 10 ply remaining in the search (e.g. you're doing a 20 ply search and you have 10 ply remaining).

What is the maximum reduction you'd make? And what are the conditions for that reduction?

- Steve

[cdani]

In a precalculated array, I have up to 4, depending on the move number:
{1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, ...} int[50]

But this value:
* no lmr if special move like killers and others.
* bad history increases by 1.
* counter moves reduced by 1.
* in endgame can be reduced by 1.
* if previous iteration eval is 0, can be reduced by 1.
* if is check, can be reduced by 1.

[Bloodbane]

My LMR formula is max(1, floor(ln(depth) * ln(moveCount) / 1.70)), where both depth and moveCount are always <= 63. For the case you brought up Hakkapeliitta would reduce by at most 5 (this would happen if moveCount > 40). I don't reduce when the depth is lower than 3, we are in check, when the move is a capture, promotion or a check or when the move is a TT-move, killer move or a counter move. Oh, and moveCount is the position of the move in the movelist, not the number of searched moves. I'm not quite sure which is better.

To be honest, I think the reductions I currently have are way too aggressive, as the average depth reached by the current dev version of Hakkapeliitta in 40/40 games is around 36 while a fairly recent dev version of Andscacs has an average depth of around 28 and it still is stronger than Hakkapeliitta. There's probably a pile of elo points which I could get if I'd just figure out a better way to do reductions.

[Steve Maughan]

Hi Daniel & Mikko,

Great! That's got me thinking.

Mikko - interesting formula. I need to investigate more!

Thanks - Steve

[Henk]

Problem with these formulas is that you can only test them if you can get large search depths in a short time. Otherwise testing takes too much time.
But in order to get large search depths in a short time you have to reduce aggressively. So you can't test if much less aggressive reductions performs better unless you don't mind to wait for days. Expensive and only for very patient developers.

[zd3nik]

If you figure out the ideal LMR formula let us know. I've done a lot of tinkering with LMR. And every time I think I've got a good system down I find out shortly afterward that it made my engine stupider in real play, even though in self play or test positions the LMR change showed an improvement.

[cdani]

I changed the LMR formula of Andscacs a lot of times. And also a lot the other search parameters, which ultimately affect how LMR can be changed.

Obtaining a more or less good way of doing it is a matter of work and patience. It evolves with the rest of the engine.

I also have seen that I can push more LMR in selfplay, but then in real play is worst.

[op12no2]

Just thinking aloud but I wonder if it's possible to self-calibrate to get at least some nominal values perhaps. Pick a time to search and analyse 1000s of positions with no LMR, saving the bm in an output file. Run the whole thing a bunch of times with increasing LMR severity, comparing the bm with the LMR=0 result until the failure rate drops below say 95%. Repeat with other time values and other LMR methods (depth based, move based depth+move based). Draw some graphs and guesstimate some nominal values.

[Stan Arts]

Simply half a ply reduction in Nemeton for anything that is not a capture, check, hashmove or killer.
Early on it helped a fair bit I thought but lately I've tested a lot of wacky values and schemes and it all just sucks. Last days I ran tests with no reductions and for whatever reason Nemeton now that eval is more complicated, has some mobility etc. performs as well with it off too.

So that's confusing. I'll probably leave it in for Leiden this weekend even if just because the half ply reduction burns through plies slightly smoother and reports higher depths which helps me psychologically.

No doubt it can work but somehow everything has to work in unison and that probably involves some black magic, selling your soul and sacrificing a chicken.

[op12no2]

My soul is already sold and we don't have chickens - but we do have lot's of sheep around here - I may try that before HGM's next tourney...

FWIW my LMR is very basic - I'm trying to creep up on it with lots of testing.

Currently R=1 if: numMovesTried > 2 && depth >= 3 && !inCheck && !givesCheck && !(hash||promote||capture||killer||castle).

That's it. The >=3 is so it doesn't drop into QSearch (I do the same with NMP).

I think I came up with numMovesTried > 2 from measuring the average move number that beta cutoffs happen at - which was 1.x. Need to try > 1 as well in LMR.