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 wrote: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.
LMR
Moderators: hgm, Rebel, chrisw
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: LMR
-
- Posts: 5106
- Joined: Tue Apr 29, 2008 4:27 pm
Re: LMR
You misunderstand. I run to fixed depth, but I always take time into consideration.bob wrote:Don wrote: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.bob wrote:
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...
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.
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.
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: LMR
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...Don wrote:You misunderstand. I run to fixed depth, but I always take time into consideration.bob wrote:Don wrote: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.bob wrote:
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...
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.
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.
-
- Posts: 1056
- Joined: Fri Mar 10, 2006 6:07 am
- Location: Basque Country (Spain)
Re: LMR
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?
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?
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: LMR
Tried that. No difference in real game performance on cluster testing.pedrox wrote: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?
-
- Posts: 3196
- Joined: Fri May 26, 2006 3:00 am
- Location: WY, USA
- Full name: Michael Sherwin
Re: LMR
I am not sure that complementary is the right word.bob wrote: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 wrote: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.
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.
If you are on a sidewalk and the covid goes beep beep
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: 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...Michael Sherwin wrote:I am not sure that complementary is the right word.bob wrote: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 wrote: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.
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.
Re: LMR
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.bob wrote: 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.
Ed
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: LMR
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.rebel777 wrote: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.bob wrote: 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.
Ed
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.
-
- Posts: 4185
- Joined: Tue Mar 14, 2006 11:34 am
- Location: Ethiopia
Re: LMR
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 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...