LMR musings on a rainy Wednesday night...

[bob]

I am working on various ways to more selectively choose what to reduce and what to not reduce. And in playing with several options, I have noticed one thing that is a bit surprising. If I do an N-ply search, I can practically disable LMR on the first N/2 plies and not affect the playing strength at all, which I did not expect. I have some tests running that do a better move ordering for (currently, just to pick a starting point) the first 1/2 of the plies (not including any chacks, so a 20 ply search spends more ordering time on the first 10 plies, period). And then I thought I would start to exclude a few extra moves from LMR reductions based on the ordering which includes static eval + swap on last move scores. And as I increase the number of moves I exclude, cluster testing shows absolutely no effect on rating so far. I am working my way up to excluding LMR on all these moves just to see if at some point it starts to hurt. My next test series is going to be to vary the depth at which I do this "better ordering" to see how deep I can go before the overhead starts to catch up and slow the thing down enough to make it a net loser.

But so far, this is interesting stuff...

[CRoberson]

I tried something similar several months ago. I turned off LMR
at plies <= N-4. My tests indicated a 60 Elo loss. Of course, I don't
run as many tests as you.

[Dann Corbit]

Is this possibly an artifact of the fact that due to the exponential explosion, the first (0 to N/2) plies contain only a microscopic fraction of the data that plies (N/2+1 to N) contain?

Hence, not trimming them has a very tiny cost. Apparenly, that cost is about equal to the value of deeper search obtained by trimming.

It would be interesting (perhaps) to also experiment with other ratios.

IOW:
What happens if you do not apply LMR until ply N*(1/3)?
What happens if you do not apply LMR until ply N*(2/3)?

[bob]

Is this possibly an artifact of the fact that due to the exponential explosion, the first (0 to N/2) plies contain only a microscopic fraction of the data that plies (N/2+1 to N) contain?

Hence, not trimming them has a very tiny cost. Apparenly, that cost is about equal to the value of deeper search obtained by trimming.

It would be interesting (perhaps) to also experiment with other ratios.

IOW:
What happens if you do not apply LMR until ply N*(1/3)?
What happens if you do not apply LMR until ply N*(2/3)?

The idea, however, is that yes there are not very many nodes at ply <= depth/2, but every one of those nodes is along the path to the tips. In general, you get more by pruning near the root than you do near the tips, because anything near the root has a broader effect on the tips.

But this case is odd. I'm working on testing varying the depth right now. Will see what happens as I try the more complex ordering farther and farther out near the tips, and then once I find a sweet-spot for that, I will re-run this test on varying the number of moves that don't get LMR applied...

[Tony]

I am working on various ways to more selectively choose what to reduce and what to not reduce. And in playing with several options, I have noticed one thing that is a bit surprising. If I do an N-ply search, I can practically disable LMR on the first N/2 plies and not affect the playing strength at all, which I did not expect. I have some tests running that do a better move ordering for (currently, just to pick a starting point) the first 1/2 of the plies (not including any chacks, so a 20 ply search spends more ordering time on the first 10 plies, period). And then I thought I would start to exclude a few extra moves from LMR reductions based on the ordering which includes static eval + swap on last move scores. And as I increase the number of moves I exclude, cluster testing shows absolutely no effect on rating so far. I am working my way up to excluding LMR on all these moves just to see if at some point it starts to hurt. My next test series is going to be to vary the depth at which I do this "better ordering" to see how deep I can go before the overhead starts to catch up and slow the thing down enough to make it a net loser.

But so far, this is interesting stuff...

Just a test idea: How about the first 1/3 Plies no LMR reduction, from 1/3 to 2/3 1 Ply reduction, and the last 1/3 plies 2 Ply reduction.

The idea is to make the effect of lmr more pronounced in the part of the tree where it seems to work mostly.

Toy

[hgm]

I tried something similar several months ago. I turned off LMR
at plies <= N-4. My tests indicated a 60 Elo loss. Of course, I don't
run as many tests as you.

If you turn off LMR for ply <= N-4, you turn it off completely, not? LMR is only done when the remaining depth >= 4. Or am I mising something?

As I described in the other thread, my current implementation of LMR is that I pass a flag to Search() to tell it that the move it is now searching is 'late' (meaning not hash, capture or killer). It then uses R=3 on its null-move search rather than R=2. If this null-move search fails low, it immediately does a normal, unreduced search. (So I don't bother to redo th enull-move search with R=2 first; the fact that a low-depth null move fails low is considered sufficient proof the preceeding move was not a crazy one nd is worth searching.) This implies that setting the flag on a search with d<=4 cannot resut in any effect: even with R=2 reduction the null move directly jumps into QS, and there is no way to reduce it more.

[Uri Blass]

I am working on various ways to more selectively choose what to reduce and what to not reduce. And in playing with several options, I have noticed one thing that is a bit surprising. If I do an N-ply search, I can practically disable LMR on the first N/2 plies and not affect the playing strength at all, which I did not expect. I have some tests running that do a better move ordering for (currently, just to pick a starting point) the first 1/2 of the plies (not including any chacks, so a 20 ply search spends more ordering time on the first 10 plies, period). And then I thought I would start to exclude a few extra moves from LMR reductions based on the ordering which includes static eval + swap on last move scores. And as I increase the number of moves I exclude, cluster testing shows absolutely no effect on rating so far. I am working my way up to excluding LMR on all these moves just to see if at some point it starts to hurt. My next test series is going to be to vary the depth at which I do this "better ordering" to see how deep I can go before the overhead starts to catch up and slow the thing down enough to make it a net loser.

But so far, this is interesting stuff...

I think that it may be interesting if you try to disable LMR except the last n plies for n=1,2,3,4,5,6 and report your results.

It is possible that the benefit from LMR is only when the remaining depth is small.

Uri

[Uri Blass]

Is this possibly an artifact of the fact that due to the exponential explosion, the first (0 to N/2) plies contain only a microscopic fraction of the data that plies (N/2+1 to N) contain?

Hence, not trimming them has a very tiny cost. Apparenly, that cost is about equal to the value of deeper search obtained by trimming.

It would be interesting (perhaps) to also experiment with other ratios.

IOW:
What happens if you do not apply LMR until ply N*(1/3)?
What happens if you do not apply LMR until ply N*(2/3)?

The idea, however, is that yes there are not very many nodes at ply <= depth/2, but every one of those nodes is along the path to the tips. In general, you get more by pruning near the root than you do near the tips, because anything near the root has a broader effect on the tips.

But this case is odd. I'm working on testing varying the depth right now. Will see what happens as I try the more complex ordering farther and farther out near the tips, and then once I find a sweet-spot for that, I will re-run this test on varying the number of moves that don't get LMR applied...

I think that pruning near the root is more risky.
pruning a good move near the root have bigger chance to cause you to miss the right move relative to pruning a good move near the tips.

It is possible that the risk is too big when the remaining depth is high and the same may also be correct for null move pruning.

It may be interesting also to test what happens if you disable null move except the last n plies for different values of n.

Uri

[bob]

Is this possibly an artifact of the fact that due to the exponential explosion, the first (0 to N/2) plies contain only a microscopic fraction of the data that plies (N/2+1 to N) contain?

Hence, not trimming them has a very tiny cost. Apparenly, that cost is about equal to the value of deeper search obtained by trimming.

It would be interesting (perhaps) to also experiment with other ratios.

IOW:
What happens if you do not apply LMR until ply N*(1/3)?
What happens if you do not apply LMR until ply N*(2/3)?

The idea, however, is that yes there are not very many nodes at ply <= depth/2, but every one of those nodes is along the path to the tips. In general, you get more by pruning near the root than you do near the tips, because anything near the root has a broader effect on the tips.

But this case is odd. I'm working on testing varying the depth right now. Will see what happens as I try the more complex ordering farther and farther out near the tips, and then once I find a sweet-spot for that, I will re-run this test on varying the number of moves that don't get LMR applied...

I think that pruning near the root is more risky.
pruning a good move near the root have bigger chance to cause you to miss the right move relative to pruning a good move near the tips.

It is possible that the risk is too big when the remaining depth is high and the same may also be correct for null move pruning.

It may be interesting also to test what happens if you disable null move except the last n plies for different values of n.

Uri

I happen to agree. That is why I was experimenting with better ordering near the root so that I can be a bit more selective in what gets reduced. My first "cut" at this was to say that if I am doing an N ply search, I would be more accurate at the first N/2 plies of the search, and use my normal LMR (anything but captures, killers, etc) the rest of the way out the tree. And while it helped in some tactical cases, it made absolutely no difference in real games...

I am still experimenting with this...

[bob]

I am working on various ways to more selectively choose what to reduce and what to not reduce. And in playing with several options, I have noticed one thing that is a bit surprising. If I do an N-ply search, I can practically disable LMR on the first N/2 plies and not affect the playing strength at all, which I did not expect. I have some tests running that do a better move ordering for (currently, just to pick a starting point) the first 1/2 of the plies (not including any chacks, so a 20 ply search spends more ordering time on the first 10 plies, period). And then I thought I would start to exclude a few extra moves from LMR reductions based on the ordering which includes static eval + swap on last move scores. And as I increase the number of moves I exclude, cluster testing shows absolutely no effect on rating so far. I am working my way up to excluding LMR on all these moves just to see if at some point it starts to hurt. My next test series is going to be to vary the depth at which I do this "better ordering" to see how deep I can go before the overhead starts to catch up and slow the thing down enough to make it a net loser.

But so far, this is interesting stuff...

Just a test idea: How about the first 1/3 Plies no LMR reduction, from 1/3 to 2/3 1 Ply reduction, and the last 1/3 plies 2 Ply reduction.

The idea is to make the effect of lmr more pronounced in the part of the tree where it seems to work mostly.

Toy

I have tried part of that, a little differently. I tried the normal 1-ply reduction during the first 1/2 of the plies, unless a move looked exceptionally bad to my internal ordering (for example, moving a piece to a square where SEE thinks it will be lost) where I tried 2 plies. I then reduced everything by 1 ply during the last 1/2 of the plies. I tried a few variations on this but I can't "flip it over" because the more accurate ordering gets too expensive in the last half of the tree.. However, I have not tried a bigger reduction in the last half, which I will certainly try and report back.

One thing is for certain, I am absolutely convinced that the simplistic approach I am trying now, which is to reduce everything that appears to be non-tactical is best, because this is where I started after removing the old history fail-high counters.

one other idea in the queue is to do an inverse history counter, where each fail low (lack of a score > alpha) for a move gets counted. Fail highs greatly alter this counter downward, perhaps setting it back to zero, and then reducing moves that have primarily failed low, varying the reduction depending on how big the counter is (bigger counter means no fail highs at all, perhaps)...