LMR

[bob]

That was what I used to do before LMR become popular by Fruit/Glaurung.
I did constrained fail high reductions if eval() >= beta and looking at some other threats. It is same as LMR with the eval() <= alpha criteria. IMO LMR is more effective because it is recursive and has less constraints (The number of candidate nodes significantly reduces if we insert eval in to the equation)

I really want to see a comparison of LMR at PV nodes for different "L" threshold values at longer tc (say 40/10) for a good number of games. I am opposed to shorter tc because I believe the weirdest reduction/pruning gets away unpunished.

The "history pruning" idea of Toga is something I want to experiment with in the future. Again not because it makes a logical sense to me, but just because the trend nowadays to improve the branching factor as much as you can...

I played several sets of 8000 games (1000 initial positions, playing both colors, 4 opponents). I tried LMR counts from 3-18 in increments of 3's (3, 6, etc) at PV nodes, and from 2-10 by twos for non PV nodes. The moves after hash, then non-losing captures and finally killers were all sorted by using Evaluate() + Swap() which is pretty decent ordering. I found absolutely no difference for any of those counts. The idea was that I had to search N moves in "the rest of the search" (after the above moves) before applying LMR. I had a separate counter for PV and non-PV nodes.

Personally I do not believe that an N value makes any sense anyway. In a simple endgame with N > 10 (say fine 70) you _never_ reduce. So I also tried a "percentage" that I varied from 10% to 90%, which said "don't reduce until N% of the remaining moves have been searched. I then repeated this and counted the first moves as well (good captures, killers, etc.)

And for each and every test I tried, it was either no better, or actually worse. It gets worse as you increase the value as LMR slowly gets turned off. A value of 0 was equivalent to the way I have been reducing with LMR...

I originally tried the history counter approach used in Fruit, with some tweaks for making the data a bit more usable. That also did not help. I have a couple of more ideas to try, but am not sure anything is going to help since it is nearly impossible to figure out which moves are going to be important farther down in the tree, until after they have been searched. And then it is too late...

[Aleks Peshkov]

the trend nowadays to improve the branching factor as much as you can...

As far as I remember Vas said that Rybka 3 have worse branching factor then Rybka 2 by design and tests.

[Daniel Shawul]

Personally I do not believe that an N value makes any sense anyway. In a simple endgame with N > 10 (say fine 70) you _never_ reduce. So I also tried a "percentage" that I varied from 10% to 90%, which said "don't reduce until N% of the remaining moves have been searched. I then repeated this and counted the first moves as well (good captures, killers, etc.)

The constant N values may have a good effect in that case.
That basically says do less LMR when the number of moves is low,
usually when there are threats and forced moves.
If we stick to percentages only we might reduce too much at these nodes.
For example for 10% reduction threshold, the Fine 70 positon (assuming N <= 10)
gets at least one move reduced at every node. For N = 6,7 etc, _every_ move
gets reduced so may be a bound like the popular L=3 could help for this case.
But I agree that using percentage looks better overall. I never experimented
with history counters for LMR ,where usually the percentage of fail high
moves is taken into consideration.

A value of 0 was equivalent to the way I have been reducing with LMR...

I think that is too risky...

I originally tried the history counter approach used in Fruit, with some tweaks for making the data a bit more usable. That also did not help. I have a couple of more ideas to try, but am not sure anything is going to help since it is nearly impossible to figure out which moves are going to be important farther down in the tree, until after they have been searched. And then it is too late...

I hear you. If there is no concrete criteria to tell us the move we are about
to reduce is good or bad when we start the search, we could take the risk of reducing all moves. The "late" idea of LMR assumes that we use a good
move ordering mechanism, so that 'late moves' are infact late/worthless.

[Daniel Shawul]

Daniel Shawul wrote:
the trend nowadays to improve the branching factor as much as you can...
As far as I remember Vas said that Rybka 3 have worse branching factor then Rybka 2 by design and tests.

Hmm.. Rybka doesn't tell us its real search depth (Not that I have any issue with it) May be he did far more reductions/pruning than was necessary in Rybka 2 and then later found out that tempering it down works better. My own so so engine has actually a smaller BF than Rybka.
I do a lot extensions which is keeping down the search depth, and I am yet to be convinced if i should be going the "extend less" road.

[Daniel Shawul]

I meant .. "smaller BF than rybka" not "larger"

[bob]

Personally I do not believe that an N value makes any sense anyway. In a simple endgame with N > 10 (say fine 70) you _never_ reduce. So I also tried a "percentage" that I varied from 10% to 90%, which said "don't reduce until N% of the remaining moves have been searched. I then repeated this and counted the first moves as well (good captures, killers, etc.)

The constant N values may have a good effect in that case.
That basically says do less LMR when the number of moves is low,
usually when there are threats and forced moves.
If we stick to percentages only we might reduce too much at these nodes.
For example for 10% reduction threshold, the Fine 70 positon (assuming N <= 10)
gets at least one move reduced at every node. For N = 6,7 etc, _every_ move
gets reduced so may be a bound like the popular L=3 could help for this case.
But I agree that using percentage looks better overall. I never experimented
with history counters for LMR ,where usually the percentage of fail high
moves is taken into consideration.

A value of 0 was equivalent to the way I have been reducing with LMR...

I think that is too risky...

I originally tried the history counter approach used in Fruit, with some tweaks for making the data a bit more usable. That also did not help. I have a couple of more ideas to try, but am not sure anything is going to help since it is nearly impossible to figure out which moves are going to be important farther down in the tree, until after they have been searched. And then it is too late...

I hear you. If there is no concrete criteria to tell us the move we are about
to reduce is good or bad when we start the search, we could take the risk of reducing all moves. The "late" idea of LMR assumes that we use a good
move ordering mechanism, so that 'late moves' are infact late/worthless.

Agreed. But the "late" is really badly flawed since most do not order all the moves. I used to use 4 history moves (old history ordering heuristic by Schaeffer) but removed it a few years ago after testing showed it offered little benefit. But it might be worthwhile for LMR and I am going to add it back in (it is a trivial idea and I have the old code anyway) to see if it will help. But without that, the moves (mine anyway) are tried in random order once I get past the killers. And that is why the N is irrelevant. But when I decided to try a complete evaluation + swap() to detect the expected gain or loss (many moves hang pieces outright by moving to unsafe squares) so that the idea of "N" might have more merit, that also did not improve things at all.

I'm considering an inverse fail-high sort of thing, where the more often a move fails low, the more likely it can be safely reduced. And I might even further test the idea of reducing some of these by more than one ply.

[Michael Sherwin]

I would like to add that LMR does result in a major improvement in the strength of my chess program. I think most people have found that too, but I have heard some claim there was little strength gain.

I ran this test a couple of months ago. If you have null-move already, it is worth about +40 Elo in Crafty. If I don't use null-move and add LMR it is worth about +80. Interestingly, if you don't have LMR, null-move adds about +80 also, and if you already have LMR then null-move is worth about +40. I was surprised at first, but when you think about it, the two ideas are complementary.

I am not sure that complementary is the right word.

Null move suffers some tactical shortcomings because of a more shallow search. However, Null move is much stronger overall.

LMR suffers some tactical shortcomings because of a more shallow search. However, LMR is much stronger overall.

When Null move and LMR reductions are both active at the same time the combined reductions IMO reduces the total benefit.

Using a higher move count before allowing LMR, while in null move, seems to improve strength. And is stronger than making them mutually exclusive. Except at shallower depths when mutual exclusion seems stronger.

Edit: In RomiChess the remaining moves are first scored with a very shallow search that has an open window if remaining depth is greater than three. This allows for very good move ordering of the remaining moves which in turn improves LMR.

I tried that (higher count while searching null-move) as well as a dozen other ideas over the last few weeks. No improvement for me at all. Most ideas I have tried were "zero effect" in fact, although an occasional idea would be a small negative change. Your idea about searching to order moves sounds impossibly expensive...

Here are some numbers for RomiChess in the original position for a 16 ply search on a Q6600, 2.4 GHz using only one core.

These numbers just reflect how the 'remaining' moves are ordered.

No changes:
47,035,963 nodes, 18,919 msec, 2,486,175 nodes/sec

Not counting the nodes of the move ordering searches:
31,062,742 nodes, 18,778 msec, 1,654,209 nodes/sec

Not doing the move ordering searches, only using piece-square table (fs - ts) move ordering:
195,685,842 nodes, 76,736 msec, 2,553,445 nodes/sec

No ordering of remaining moves:
326,677,020 nodes, 117,960 msec, 2,769,387 nodes/sec

This looks to me as though move ordering searches are cheap.

And N then becomes very relevant for LMR.

[bob]

I would like to add that LMR does result in a major improvement in the strength of my chess program. I think most people have found that too, but I have heard some claim there was little strength gain.

I ran this test a couple of months ago. If you have null-move already, it is worth about +40 Elo in Crafty. If I don't use null-move and add LMR it is worth about +80. Interestingly, if you don't have LMR, null-move adds about +80 also, and if you already have LMR then null-move is worth about +40. I was surprised at first, but when you think about it, the two ideas are complementary.

I am not sure that complementary is the right word.

Null move suffers some tactical shortcomings because of a more shallow search. However, Null move is much stronger overall.

LMR suffers some tactical shortcomings because of a more shallow search. However, LMR is much stronger overall.

When Null move and LMR reductions are both active at the same time the combined reductions IMO reduces the total benefit.

Using a higher move count before allowing LMR, while in null move, seems to improve strength. And is stronger than making them mutually exclusive. Except at shallower depths when mutual exclusion seems stronger.

Edit: In RomiChess the remaining moves are first scored with a very shallow search that has an open window if remaining depth is greater than three. This allows for very good move ordering of the remaining moves which in turn improves LMR.

I tried that (higher count while searching null-move) as well as a dozen other ideas over the last few weeks. No improvement for me at all. Most ideas I have tried were "zero effect" in fact, although an occasional idea would be a small negative change. Your idea about searching to order moves sounds impossibly expensive...

Here are some numbers for RomiChess in the original position for a 16 ply search on a Q6600, 2.4 GHz using only one core.

These numbers just reflect how the 'remaining' moves are ordered.

No changes:
47,035,963 nodes, 18,919 msec, 2,486,175 nodes/sec

Not counting the nodes of the move ordering searches:
31,062,742 nodes, 18,778 msec, 1,654,209 nodes/sec

Not doing the move ordering searches, only using piece-square table (fs - ts) move ordering:
195,685,842 nodes, 76,736 msec, 2,553,445 nodes/sec

No ordering of remaining moves:
326,677,020 nodes, 117,960 msec, 2,769,387 nodes/sec

This looks to me as though move ordering searches are cheap.

And N then becomes very relevant for LMR.

I do not understand your "move ordering search" then. It appeared, based on the terminology, to be a real search that somehow gets a score back for each move, which would imply a wide window. In any case, I don't see how one can do a search to order _all_ nodes inside the tree by doing a search, since internal iterative deepening on all nodes would be horribly expensive, particularly since the ALL nodes have no best order anyway...

[rebel777]

Inspired by the current discussion I after 2 years looked into my code again trying to understand the stuff I once wrote, a true hieroglyphic experience. As an experiment I set the LMR parameter of the the minimum number of moves from 3 (Fruit) to the crazy value of 0. Remarkably most positions did a lot better than with the default setting of 3.

I haven't played any game and I am not planning also, so the observation can be meaningless. I just want to mention the phenomenon and ask if anyone has experienced the same.

Ed

[bob]

Inspired by the current discussion I after 2 years looked into my code again trying to understand the stuff I once wrote, a true hieroglyphic experience. As an experiment I set the LMR parameter of the the minimum number of moves from 3 (Fruit) to the crazy value of 0. Remarkably most positions did a lot better than with the default setting of 3.

I haven't played any game and I am not planning also, so the observation can be meaningless. I just want to mention the phenomenon and ask if anyone has experienced the same.

Ed

That's what I had already reported. I have found positions where going from 0 upward helps the time. But the test I resort to is games, and there I can find no significant difference between 0 and very small N, where as N gets larger, LMR phases out and things do get worse.

I've been using zero for a year now, and the past 4 weeks or so of testing has produced no better option (yet).