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.

[Don]

I'm looking at a couple of things.

1. the "counter" makes no sense if you don't somehow order the moves as they are searched. I have not been ordering beyond hash, good captures and killers, then the rest of the moves. In that context, no counter is effective since the first N moves are no more likely to be good than the last N. I am experimenting with much stronger move ordering, at least at the first N plies of the search (not all the way to the leaves which is too expensive) so that the N counter will actually have some sort of merit. And it might be that the old history ordering idea will become a good idea again and I plan on testing that as well.

2. I don't care about losing or gaining a ply. What I care about is losing or gaining real Elo in games. I have been experimenting with multiple reduction levels. For example, moving a queen to a square attacked by a pawn is not going to be a good move in general, and reducing it by an extra ply reduces the tree. And produces absolutely no gain in Elo. In fact, doing that for all pieces (any piece moving to a square attacked by a lesser piece gets reduced 2x) produces absolutely no Elo improvement (and this does not include captures of course).

So far I have tried lots of things, and none is any better than the rest. So far... Crafty's normal LMR has no counter at all. And it is working exactly as well as one with a counter for PV and counter for non-PV...

I've done tons of experiments with this, especially the PV / NON PV distinction and I have not once proved that PV nodes should be handled differently for LMR or anything else for that matter. Most of my tests are done at fixed depth below 11 or 12 ply and I generally run several thousand games to make sure I am not drawing false conclusions.

That appears to be a significant mistake to me. If you searched to fixed depth, then reducing the effective branching factor by reductions and such doesn't help at all. In fact, you would do better with even null-move turned off since a 12 ply search without null-move is significantly more accurate than a 12 ply search with null-move. It will take a lot longer of course, but when you exclude time from the equation, you don't see any benefit since you can't go deeper because of the depth limit.

You misunderstand. I run to fixed depth, but I always take time into consideration.

When I test, I report average time per game, ELO rating as computed by bayeselo, and another special value I call "norm" which is an adjusted rating which compensates for time. So, for instance, if one program gets a 2200 ELO rating and another gets a 2180 rating, which is stronger? The answer is not necessarily the one with a 2200 rating. If the one with a 2180 rating spends half as much time, my result table will show that is has a tme adjusted ELO rating that is higher. In this way I can try to make sense of various algorithmic changes that affect the time/quality ratio. The only other reasonable way to do this is run time control games, but that requires me to run at much longer time controls that require days to get a single result.

What I have found is that with most reasonable values of LMR parameters and conditions which are tested, I get almost the same adjusted ELO rating even though some version are much faster than others.

[bob]

I'm looking at a couple of things.

1. the "counter" makes no sense if you don't somehow order the moves as they are searched. I have not been ordering beyond hash, good captures and killers, then the rest of the moves. In that context, no counter is effective since the first N moves are no more likely to be good than the last N. I am experimenting with much stronger move ordering, at least at the first N plies of the search (not all the way to the leaves which is too expensive) so that the N counter will actually have some sort of merit. And it might be that the old history ordering idea will become a good idea again and I plan on testing that as well.

2. I don't care about losing or gaining a ply. What I care about is losing or gaining real Elo in games. I have been experimenting with multiple reduction levels. For example, moving a queen to a square attacked by a pawn is not going to be a good move in general, and reducing it by an extra ply reduces the tree. And produces absolutely no gain in Elo. In fact, doing that for all pieces (any piece moving to a square attacked by a lesser piece gets reduced 2x) produces absolutely no Elo improvement (and this does not include captures of course).

So far I have tried lots of things, and none is any better than the rest. So far... Crafty's normal LMR has no counter at all. And it is working exactly as well as one with a counter for PV and counter for non-PV...

I've done tons of experiments with this, especially the PV / NON PV distinction and I have not once proved that PV nodes should be handled differently for LMR or anything else for that matter. Most of my tests are done at fixed depth below 11 or 12 ply and I generally run several thousand games to make sure I am not drawing false conclusions.

That appears to be a significant mistake to me. If you searched to fixed depth, then reducing the effective branching factor by reductions and such doesn't help at all. In fact, you would do better with even null-move turned off since a 12 ply search without null-move is significantly more accurate than a 12 ply search with null-move. It will take a lot longer of course, but when you exclude time from the equation, you don't see any benefit since you can't go deeper because of the depth limit.

You misunderstand. I run to fixed depth, but I always take time into consideration.

When I test, I report average time per game, ELO rating as computed by bayeselo, and another special value I call "norm" which is an adjusted rating which compensates for time. So, for instance, if one program gets a 2200 ELO rating and another gets a 2180 rating, which is stronger? The answer is not necessarily the one with a 2200 rating. If the one with a 2180 rating spends half as much time, my result table will show that is has a tme adjusted ELO rating that is higher. In this way I can try to make sense of various algorithmic changes that affect the time/quality ratio. The only other reasonable way to do this is run time control games, but that requires me to run at much longer time controls that require days to get a single result.

What I have found is that with most reasonable values of LMR parameters and conditions which are tested, I get almost the same adjusted ELO rating even though some version are much faster than others.

OK, that sounds reasonable. As far as your last comment, that has been my findings so far as well. The only possible divergence is that longer games react differently to LMR than shorter games. How much probably depends on the program. I am trying to quantify that for mine as I write this...

[pedrox]

Moves that increase the pressure of the king should not be reduced. These moves should even be extended.

Any idea to identify these moves?

Perhaps we should not reduce those moves of knight and queen that make these pieces more close to the king?

[bob]

Moves that increase the pressure of the king should not be reduced. These moves should even be extended.

Any idea to identify these moves?

Perhaps we should not reduce those moves of knight and queen that make these pieces more close to the king?

Tried that. No difference in real game performance on cluster testing.

[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.

[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...

[rebel777]

I exclude the hash move, all captures, checks, escaping checks, passed pawn pushes (I am not sure this is a good idea however) and even the hash move and killer moves. Beyond that, anything goes and so far, that has produced the best results... In spite of hundreds of alternative ideas and tests.

What I miss in the list of LMR veto's is an alpha check with the static score of the position, the most effective veto out there as it avoids many reductions.

Ed

[bob]

I exclude the hash move, all captures, checks, escaping checks, passed pawn pushes (I am not sure this is a good idea however) and even the hash move and killer moves. Beyond that, anything goes and so far, that has produced the best results... In spite of hundreds of alternative ideas and tests.

What I miss in the list of LMR veto's is an alpha check with the static score of the position, the most effective veto out there as it avoids many reductions.

Ed

Tried that. And tried a varying window below alpha even. And I used a full Evaluate() call to make a "guess" at the current evaluation. My idea was that I did not care about speed for the moment, first thing was to try to figure out what limit would work to reduce the size of the tree while improving performance in terms of Elo in real games. I then planned to find a more efficient way of doing that, assuming something actually worked.

What I believe is happening is that we are now breaking moves up into three classes. Threats that get extended, minor threats that get searched to normal depth (the moves we exclude LMR on already) and then the rest of the moves that get reduced. It appears that there is not a viable way of recognizing what to reduce or what to not reduce based on static information. At least in my program, although I can't speak for others other than to say the "history threshold in Fruit is completely ineffective as you can change it to 30 or 80 and it makes no difference with respect to Elo in real games.

I found some things that helped in tactical positions. Sometimes finding the key tactical move 2-3 plies sooner, and 2-3x faster. But I also found equivalent positions that it hurt in, and overall the effect was always "any restrictions turns out slightly to moderately worse in real Elo."

I have a few ideas left that I am working on, but so far nothing is working better than the simple "don't reduce suspected good moves (hash, killers, good captures, passed pawn pushes [and I am not sure this is a good one either]"...

More if I find something that might work, and at least one idea sounds theoretically good, but real games will be the final measuring stick.

[Daniel Shawul]

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...