LMR revisited.

[bob]

I have been experimenting with LMR and various ways one might do it more intelligently. And after about 4 weeks of solid testing, I have produced exactly -nothing- that helps. I have tried things from using a complex ordering early in the tree, and then using either one or two "late" counters, one for PV nodes, one for non-PV nodes (ala glaurung). Doesn't help one bit. Just doing the counters without the ordering. nada. I've tried (again) fruit-like history counters. Either no better or much worse depending on the threshold set. I've tried a more localized history counter, like failhi[ply][from-to] and faillo[ply][from-to] so that the values don't get completely scrambled. Again, either no better or worse depending on how those values are used.

I'm still testing, but so far, looking at several programs that do LMR, absolutely none of the ideas I have seen make any difference at all in testing, unless they make the program weaker. I have tested with very fast games, 1+1 games, 5+5 games, and even a few 60+60 tests (those turn into 3 hours + per game, which means I can play about 256 games every 3 hours, which is really too slow to be usable. But I wanted to make sure that the things I was trying were not just tested on very fast games where they might not matter.

I've tested everything in Glaurung 2, fruit 2, toga 2, and a lot of other ideas as well (some given above, not all). This appears to be an idea that either works, or it doesn't. Tuning seems to either hurt or have no impact.

If anyone has any suggestions while I am testing this stuff, feel free to make suggestions. I'd suspect I have tried at least 75% of what will be suggested, but any new ideas are welcome. I've been convinced for a couple of years now that the history-counter approach is simply no good, and I've not been using that for at least that long now. Some of the other ideas I tried I thought would help, but they didn't.

This is a peculiar algorithm, to say the least, since most things can be tuned somewhat. But this is resisting every effort I throw at it...

[Kempelen]

Hi Bob,

I am going to release today a version of Rodin with include ideas about LMR which I have seen it could be good. My tests show a few elo points of gain.

Ideas:
1) I order root moves with nodes count of previous iterations, as you do on Crafty. I mark a flag when the current node type is 30% of nodes of the first one. If that flag is on and I have no made any reduction in the path. I reduce by two. It helps to me. Idea, this appears to be a node which have less possibilities of be first root move choice. I do this only when a few iterations have been made.

2) An idea I have test with no effect (maybe you could see any gain): normally many people dont reduce captures. I tryed that If I find a capture with see < 0, I dont reduce, but mark a flag. If more depth in the tree I enconter a see capture again <0, then I reduce. The idea is that a bad capture could be good (ie a sacrifice), but the refatutation it usually not involve bad captures.

I have tryed other ideas, but I think you have test what I tryed.
I hope this help.
Regards,

[jdart]

I have done much less testing but I suspect that the effects of LMR interact with other forward pruning and reduction mechanisms commonly used together with it, including null move, futility pruning, and razoring. So you might have no effect just varying LMR in your current configuration but others might be getting a benefit with LMR + their unique combination of other factors. Since some of these are eval based you also get the impact of the eval function.

Toga is interesting because it does very aggressive tree size reduction through a variety of means and still remains quite strong. I see this also in programs like Shredder (assuming it is reporting its depth/nodes correctly).

--Jon

[MattieShoes]

I've never implemented LMR, but I was thinking it could pay off to prune extremely aggressively in ponder searches, sacrificing some accuracy for increased depth. As long as a regular search is performed before moving, maybe the extra depth might be worth the reduced accuracy. For that matter, it could be done during regular search as long as you have enough time to complete a full ply after it.

And I'm betting this falls in the "stuff you've already tested" category.

[Don]

I have been experimenting with LMR and various ways one might do it more intelligently. And after about 4 weeks of solid testing, I have produced exactly -nothing- that helps. I have tried things from using a complex ordering early in the tree, and then using either one or two "late" counters, one for PV nodes, one for non-PV nodes (ala glaurung). Doesn't help one bit. Just doing the counters without the ordering. nada. I've tried (again) fruit-like history counters. Either no better or much worse depending on the threshold set. I've tried a more localized history counter, like failhi[ply][from-to] and faillo[ply][from-to] so that the values don't get completely scrambled. Again, either no better or worse depending on how those values are used.

I'm still testing, but so far, looking at several programs that do LMR, absolutely none of the ideas I have seen make any difference at all in testing, unless they make the program weaker. I have tested with very fast games, 1+1 games, 5+5 games, and even a few 60+60 tests (those turn into 3 hours + per game, which means I can play about 256 games every 3 hours, which is really too slow to be usable. But I wanted to make sure that the things I was trying were not just tested on very fast games where they might not matter.

I've tested everything in Glaurung 2, fruit 2, toga 2, and a lot of other ideas as well (some given above, not all). This appears to be an idea that either works, or it doesn't. Tuning seems to either hurt or have no impact.

If anyone has any suggestions while I am testing this stuff, feel free to make suggestions. I'd suspect I have tried at least 75% of what will be suggested, but any new ideas are welcome. I've been convinced for a couple of years now that the history-counter approach is simply no good, and I've not been using that for at least that long now. Some of the other ideas I tried I thought would help, but they didn't.

This is a peculiar algorithm, to say the least, since most things can be tuned somewhat. But this is resisting every effort I throw at it...

In recent weeks I have found only 1 thing that helps. I reduce later moves more than early moves. At move 4 I start reducing by 1 ply, then at move 12 or so I start reducing 2 ply. Perhaps you could give that a try.

In my program at fast time controls LMR is worth 100 ELO. I don't know how much it's worth at deeper levels. I think it should be worth more in programs with really good evaluation functions but I'm sure Vincent would disagree

I also found that the PV Node distinction seems irrelevant in my program.

I remember you saying that you reduce all non-tactical moves. I don't quite understand that - what if there are no captures or checks? Do you reduce even the first move in that situation? I assume you re-search when the score returned gets above alpha?

[bob]

I have been experimenting with LMR and various ways one might do it more intelligently. And after about 4 weeks of solid testing, I have produced exactly -nothing- that helps. I have tried things from using a complex ordering early in the tree, and then using either one or two "late" counters, one for PV nodes, one for non-PV nodes (ala glaurung). Doesn't help one bit. Just doing the counters without the ordering. nada. I've tried (again) fruit-like history counters. Either no better or much worse depending on the threshold set. I've tried a more localized history counter, like failhi[ply][from-to] and faillo[ply][from-to] so that the values don't get completely scrambled. Again, either no better or worse depending on how those values are used.

I'm still testing, but so far, looking at several programs that do LMR, absolutely none of the ideas I have seen make any difference at all in testing, unless they make the program weaker. I have tested with very fast games, 1+1 games, 5+5 games, and even a few 60+60 tests (those turn into 3 hours + per game, which means I can play about 256 games every 3 hours, which is really too slow to be usable. But I wanted to make sure that the things I was trying were not just tested on very fast games where they might not matter.

I've tested everything in Glaurung 2, fruit 2, toga 2, and a lot of other ideas as well (some given above, not all). This appears to be an idea that either works, or it doesn't. Tuning seems to either hurt or have no impact.

If anyone has any suggestions while I am testing this stuff, feel free to make suggestions. I'd suspect I have tried at least 75% of what will be suggested, but any new ideas are welcome. I've been convinced for a couple of years now that the history-counter approach is simply no good, and I've not been using that for at least that long now. Some of the other ideas I tried I thought would help, but they didn't.

This is a peculiar algorithm, to say the least, since most things can be tuned somewhat. But this is resisting every effort I throw at it...

In recent weeks I have found only 1 thing that helps. I reduce later moves more than early moves. At move 4 I start reducing by 1 ply, then at move 12 or so I start reducing 2 ply. Perhaps you could give that a try.

In my program at fast time controls LMR is worth 100 ELO. I don't know how much it's worth at deeper levels. I think it should be worth more in programs with really good evaluation functions but I'm sure Vincent would disagree

I also found that the PV Node distinction seems irrelevant in my program.

I remember you saying that you reduce all non-tactical moves. I don't quite understand that - what if there are no captures or checks? Do you reduce even the first move in that situation? I assume you re-search when the score returned gets above alpha?

1. already tried that and variations of that including inverting it. I have tried setting a percentage so that in the first x% of the search it reduces by 1, in the last 100-x% it reduces by 2, and varied x from 10% to 100%.. Small X is somewhat worse as more D=2 reductions are happening. I've tried marrying that with the idea of reducing PV nodes less aggressively than non-PV nodes. So far, nothing has improved things at all. Some things have hurt, many make no difference at all.

For your other question, I currently don't reduce anything until I am past the non-bad (SEE) captures, and the hash move, and the killers, not to mention checks, passed pawn pushes, etc. I have tried a counter to say don't reduce the first N, and have tried N from 2 to 100 (100 obviously disables reductions completely). Any sort of restriction on what to reduce, so far, has been bad. I am even going to see what happens on reducing captures. In fact, reducing a SEE > 0 capture might make good sense since the majority of moves in the tree hang material anyway and are refuted by captures. Why not a shallower capture search?

Based on probably 25,000,000 games so far, it seems that reducing more is the direction to go, since any attempt to reduce less has been either no gain, or a loser...

edit:

I missed that last question in responding to the rest. Yes, if a reduced search fails high, I re-search with the original depth before using the fail-high. If the re-search fails low, I keep on searching normally.

[Don]

I did some logging in my program to show me all the positions and moves where LMR would fail. I basically turned LMR off, but applied the rules to see when it would go wrong.

I got a lot of good looking moves like g1f3 and such, they looked like the kind of moves that would be killers (but I don't reduce killers so they were not killers.)

I also measured the percentage of the failures and did tests to see how I might get those down to much lower numbers.

The bottom line is that I was able to reduce the number of bad reductions, but it had no measurable impact on the strength of the program, it just slowed it down a lot!

I have been experimenting with LMR and various ways one might do it more intelligently. And after about 4 weeks of solid testing, I have produced exactly -nothing- that helps. I have tried things from using a complex ordering early in the tree, and then using either one or two "late" counters, one for PV nodes, one for non-PV nodes (ala glaurung). Doesn't help one bit. Just doing the counters without the ordering. nada. I've tried (again) fruit-like history counters. Either no better or much worse depending on the threshold set. I've tried a more localized history counter, like failhi[ply][from-to] and faillo[ply][from-to] so that the values don't get completely scrambled. Again, either no better or worse depending on how those values are used.

I'm still testing, but so far, looking at several programs that do LMR, absolutely none of the ideas I have seen make any difference at all in testing, unless they make the program weaker. I have tested with very fast games, 1+1 games, 5+5 games, and even a few 60+60 tests (those turn into 3 hours + per game, which means I can play about 256 games every 3 hours, which is really too slow to be usable. But I wanted to make sure that the things I was trying were not just tested on very fast games where they might not matter.

I've tested everything in Glaurung 2, fruit 2, toga 2, and a lot of other ideas as well (some given above, not all). This appears to be an idea that either works, or it doesn't. Tuning seems to either hurt or have no impact.

If anyone has any suggestions while I am testing this stuff, feel free to make suggestions. I'd suspect I have tried at least 75% of what will be suggested, but any new ideas are welcome. I've been convinced for a couple of years now that the history-counter approach is simply no good, and I've not been using that for at least that long now. Some of the other ideas I tried I thought would help, but they didn't.

This is a peculiar algorithm, to say the least, since most things can be tuned somewhat. But this is resisting every effort I throw at it...

In recent weeks I have found only 1 thing that helps. I reduce later moves more than early moves. At move 4 I start reducing by 1 ply, then at move 12 or so I start reducing 2 ply. Perhaps you could give that a try.

In my program at fast time controls LMR is worth 100 ELO. I don't know how much it's worth at deeper levels. I think it should be worth more in programs with really good evaluation functions but I'm sure Vincent would disagree

I also found that the PV Node distinction seems irrelevant in my program.

I remember you saying that you reduce all non-tactical moves. I don't quite understand that - what if there are no captures or checks? Do you reduce even the first move in that situation? I assume you re-search when the score returned gets above alpha?

1. already tried that and variations of that including inverting it. I have tried setting a percentage so that in the first x% of the search it reduces by 1, in the last 100-x% it reduces by 2, and varied x from 10% to 100%.. Small X is somewhat worse as more D=2 reductions are happening. I've tried marrying that with the idea of reducing PV nodes less aggressively than non-PV nodes. So far, nothing has improved things at all. Some things have hurt, many make no difference at all.

For your other question, I currently don't reduce anything until I am past the non-bad (SEE) captures, and the hash move, and the killers, not to mention checks, passed pawn pushes, etc. I have tried a counter to say don't reduce the first N, and have tried N from 2 to 100 (100 obviously disables reductions completely). Any sort of restriction on what to reduce, so far, has been bad. I am even going to see what happens on reducing captures. In fact, reducing a SEE > 0 capture might make good sense since the majority of moves in the tree hang material anyway and are refuted by captures. Why not a shallower capture search?

Based on probably 25,000,000 games so far, it seems that reducing more is the direction to go, since any attempt to reduce less has been either no gain, or a loser...

edit:

I missed that last question in responding to the rest. Yes, if a reduced search fails high, I re-search with the original depth before using the fail-high. If the re-search fails low, I keep on searching normally.

[Desperado]

hi,

just a few weeks ago i tried something like this.

Instead of using a "blind" LMR implementation(doesnt matter in what way you use LMR), i started a shallow search on Allnodes before looping the movelist.
When the score really stayed <=alpha i used very aggressive LMR-prunning(not to say i immediatelly returned alpha , i tested this too )

The effect was, although the high costs of the shallow search it payed
off in 2(3) ways.

1. the search was better prepared for the subtree
2. the pruning seemed to be more save (which may gain some elos)(which i conclude from the gameplay results...significantly more points compared to my "poor" LMR)
(3. at the end the there were pruned about the same number of nodes)

Of course my engine is still weak and not really comparable with crafty,
but i would be interested what you think about (?!)

[bob]

I did some logging in my program to show me all the positions and moves where LMR would fail. I basically turned LMR off, but applied the rules to see when it would go wrong.

I got a lot of good looking moves like g1f3 and such, they looked like the kind of moves that would be killers (but I don't reduce killers so they were not killers.)

I also measured the percentage of the failures and did tests to see how I might get those down to much lower numbers.

The bottom line is that I was able to reduce the number of bad reductions, but it had no measurable impact on the strength of the program, it just slowed it down a lot!

That is what I have seen many times. The program gets slower (not nps-wise, but time-to-depth wise) but gets absolutely no stronger. And on occasion, gets weaker... That's why I am about to experiment with capture reductions as well, as it seems that reducing less hurts or doesn't help, so there is only one other direction to try.

I have been experimenting with LMR and various ways one might do it more intelligently. And after about 4 weeks of solid testing, I have produced exactly -nothing- that helps. I have tried things from using a complex ordering early in the tree, and then using either one or two "late" counters, one for PV nodes, one for non-PV nodes (ala glaurung). Doesn't help one bit. Just doing the counters without the ordering. nada. I've tried (again) fruit-like history counters. Either no better or much worse depending on the threshold set. I've tried a more localized history counter, like failhi[ply][from-to] and faillo[ply][from-to] so that the values don't get completely scrambled. Again, either no better or worse depending on how those values are used.

I'm still testing, but so far, looking at several programs that do LMR, absolutely none of the ideas I have seen make any difference at all in testing, unless they make the program weaker. I have tested with very fast games, 1+1 games, 5+5 games, and even a few 60+60 tests (those turn into 3 hours + per game, which means I can play about 256 games every 3 hours, which is really too slow to be usable. But I wanted to make sure that the things I was trying were not just tested on very fast games where they might not matter.

I've tested everything in Glaurung 2, fruit 2, toga 2, and a lot of other ideas as well (some given above, not all). This appears to be an idea that either works, or it doesn't. Tuning seems to either hurt or have no impact.

If anyone has any suggestions while I am testing this stuff, feel free to make suggestions. I'd suspect I have tried at least 75% of what will be suggested, but any new ideas are welcome. I've been convinced for a couple of years now that the history-counter approach is simply no good, and I've not been using that for at least that long now. Some of the other ideas I tried I thought would help, but they didn't.

This is a peculiar algorithm, to say the least, since most things can be tuned somewhat. But this is resisting every effort I throw at it...

In recent weeks I have found only 1 thing that helps. I reduce later moves more than early moves. At move 4 I start reducing by 1 ply, then at move 12 or so I start reducing 2 ply. Perhaps you could give that a try.

In my program at fast time controls LMR is worth 100 ELO. I don't know how much it's worth at deeper levels. I think it should be worth more in programs with really good evaluation functions but I'm sure Vincent would disagree

I also found that the PV Node distinction seems irrelevant in my program.

I remember you saying that you reduce all non-tactical moves. I don't quite understand that - what if there are no captures or checks? Do you reduce even the first move in that situation? I assume you re-search when the score returned gets above alpha?

1. already tried that and variations of that including inverting it. I have tried setting a percentage so that in the first x% of the search it reduces by 1, in the last 100-x% it reduces by 2, and varied x from 10% to 100%.. Small X is somewhat worse as more D=2 reductions are happening. I've tried marrying that with the idea of reducing PV nodes less aggressively than non-PV nodes. So far, nothing has improved things at all. Some things have hurt, many make no difference at all.

For your other question, I currently don't reduce anything until I am past the non-bad (SEE) captures, and the hash move, and the killers, not to mention checks, passed pawn pushes, etc. I have tried a counter to say don't reduce the first N, and have tried N from 2 to 100 (100 obviously disables reductions completely). Any sort of restriction on what to reduce, so far, has been bad. I am even going to see what happens on reducing captures. In fact, reducing a SEE > 0 capture might make good sense since the majority of moves in the tree hang material anyway and are refuted by captures. Why not a shallower capture search?

Based on probably 25,000,000 games so far, it seems that reducing more is the direction to go, since any attempt to reduce less has been either no gain, or a loser...

edit:

I missed that last question in responding to the rest. Yes, if a reduced search fails high, I re-search with the original depth before using the fail-high. If the re-search fails low, I keep on searching normally.

[bob]

hi,

just a few weeks ago i tried something like this.

Instead of using a "blind" LMR implementation(doesnt matter in what way you use LMR), i started a shallow search on Allnodes before looping the movelist.
When the score really stayed <=alpha i used very aggressive LMR-prunning(not to say i immediatelly returned alpha , i tested this too )

The effect was, although the high costs of the shallow search it payed
off in 2(3) ways.

1. the search was better prepared for the subtree
2. the pruning seemed to be more save (which may gain some elos)(which i conclude from the gameplay results...significantly more points compared to my "poor" LMR)
(3. at the end the there were pruned about the same number of nodes)

Of course my engine is still weak and not really comparable with crafty,
but i would be interested what you think about (?!)

I am not exactly sure what you mean when you say "I started a shallow search on allnodes before looping..." How shallow and what do you do inside there? LMR on or off? Etc...

I can test most anything, but so far nothing is helping.