LMR prescription

[Evert]

I'm making a summary of different ways to do LMR based on remaining depth and move count, and it seems that there are several ways to do it in use. I'm wondering what the experience using these different forms is.

Basically, old descriptions say to reduce by 1 ply moves that are later than the first three or four, independent of depth, excepting some moves (good captures, evasions). Let's call this constant.

Another approach I have seen, as used by Senpai, increases the reduction linearly with move count, beyond a certain depth. Let's call this linear in count.

Other approaches reduce more with larger remaining depth. I think it's important here that the growth with depth is sub-linear, but I have no solid evidence for this. I have seen two approaches.

Fruit reloaded uses sqrt(depth-1) + sqrt(count-1). Let's call this square root.

Finally, Stockfish uses something of the form log(depth)*log(count). Let's call this double log product.

An alternative I haven't really seen has the form log(depth*count), but my impression (from a few testing positions, so take with salt) is that this rises too steeply with depth. Something like log(depth*count**2) seems to perform better. Let's call this logarithmic.

All of these expressions have different overall scaling factors to control the rate at which reductions increase. Are there other common approaches I have missed, or things that are known to work better than others (I get that the details depend a lot on move ordering and other tree-shaping techniques)?

[PK]

You might want to add two step approach: don't reduce up to move n, reduce by one up to move n1, then reduce by two.

Also, Fruit Reloaded approach is really unique - if I remember correctly, it also controls late move pruning, applying it if reduction > depth.

[Michael Sherwin]

New in Romichess.

Code: Select all

s32 m = histTblg[fig][fs][ts];
s32 n = histTbln[fig][fs][ts];
if&#40;n > 49 && m/n < 12&#41; &#123;
reduce += &#40;int&#41;&#40;1.0 + sqrt&#40;sqrt&#40;depth&#41; * sqrt&#40;count&#41;) / &#40;log&#40;m/n+1&#41;+1&#41;);

[cdani]

This is the way of calculating the base lmr array in Andscacs. Is a bit strange, but works well. Is the result of tens of trials and error.
Anyway it can be greatly modified depending on a lot of things before usage.

Code: Select all

	int p, j;
	double idx;
	for &#40;p = 1; p < 64; p++) &#123;
		idx = 2 + 8 / &#40;float&#41;p;
		for &#40;j = 0; j < maxjugadeslmr; j++) &#123;
			reduccio_lmr&#91;p&#93;&#91;j&#93; = 1 + &#40;j >= idx&#41; + &#40;j >= 4 * idx&#41; + &#40;j >= 8 * idx&#41; + &#40;p > 8&#41; + &#40;p > 15&#41;;
		&#125;
		reduccio_lmr&#91;p&#93;&#91;0&#93; = 0;
		reduccio_lmr&#91;p&#93;&#91;1&#93; = 0;
		if &#40;reduccio_lmr&#91;p&#93;&#91;2&#93; > 1&#41;
			reduccio_lmr&#91;p&#93;&#91;1&#93; = 1;
	&#125;

[Evert]

Some plots (I've added the functional form of Romichess, I'll do Andscacs later):







What strikes me is that Senpai and Fruit Reloaded are very agressive when it comes to reductions (Romichess even more so; I used 12 for the ratio m/n, for smaller ratios the reduction is larger) and Stockfish is a lot more conservative (perhaps going somewhat against its reputation). What is interesting about the Stockfish approach is that it will not apply reductions at all at depth 1 (makes sense, of course), which the other approaches do.

[cdani]

...and Stockfish is a lot more conservative (perhaps going somewhat against its reputation)

Reductions are cumulative in each ply, so a reduction of for example 5 is already very agressive. A reduction of 10 or 15 is like saying you don't want to analyze the position, unless is used in a non cumulative way.

[tomitank]

It depends on many things. (Move ordering, dangerous move)

If something works well in the end game (especially in the pawn endgame), then it will probably work well in the middle game as well. But this is just my opinion.

Senpai LMR work me fine in middle game, but not in the endgame.

The older Stockfish formula is very good in the endgame and in the middle game as well. (double log product.)

The difference is around ~10 elo for me.

I need more tests.

[cdani]

Also very important, the engine goes deeper faster, not by reducing more, but by finding better moves quicker. Aggressive reductions that contempt moves that later will be good, increase a lot the number of nodes needed when are found to be good, as the engine finds a lot of contradictions or search instability that make it slower.
So the equilibrium between evaluation and reductions is critical.

[Michael Sherwin]

Something is wrong with the graph for Romi's formula. A maximum possible example only yields a value of about 8.

reduce += (int)(1.0 + sqrt(sqrt(depth) * sqrt(count)) / (log(m/n+1)+1));
1 + sqrt(sqrt(36) * sqrt(100)) / 1
1 + sqrt(6 * 10)
1 + 7
8