LMR

[bob]

Here's an interesting question. A while back this discussion popped up and we were discussing the idea of LMR on PV nodes vs non-PV nodes. I think Tord said something about using a different "L" definition depending on which type of node he is searching. I believe it was basically to search more moves before starting reductions when on a PV node as opposed to starting reductions after fewer moves on a non-PV node.

The question that came to mind as I am playing around with a completely revamped approach to LMR is "what about the root node"? Since that is a PV node, does that mean you should avoid reducing until late in the move list? Which turns off a significant gain by reducing root moves after the PV has been found (of course, finding a new PV has to stumble over the reduced search depth problem before it can fail high) but it becomes an issue of lower EBF vs reduced error.

Current rewrite can do it either way, and indeed so far, at the root, I reduce everything after the first move excluding the usual checks, captures, etc. however, I do pretty accurate root move ordering up front by doing a series of true-valued searches (quiesce only) to get a good score estimate for each root move. I've got other ideas left to try, one being that instead of the idea of searching some part of a node's moves to normal depth, and the rest to reduced depth, there might be better ways to decide where to break off the full-depth searches and switch to a reduced-effort search. At the root, one might use the true-valued results for each move and when the score(move) is significantly lower than score(move[0]) the reductions could start there.

But the real issue for discussion as that on a PV node does it really make sense to be more conservative, or not?

Thoughts?

[hgm]

I am not sure the score is a good measure for how likely it is the move will turn up a surprise on a deeper search. It is more the forcing nature of the move that does it. If the opponent has many replies that are just good enough to refute it, the score is not so bad. But if on deeper search one move turns into a disaster, he will simply switch to another. and nothing is gained. But if the move loses a piece only through a very specific refutation, the piece might turn out to be poisoned, (e.g. the piece he used to capture was defending a square where we could skewer his Queen and King with a Rook, something you would not detect in QS), and the move suddenly becomes good.

[Daniel Shawul]

I think it makes more sense to be more conservative on pv nodes.
Most programmers have a (node != PV) stuck somewhere in their LMR code.
I once experimented also on the threshold number ("L", I suppose)
for ALL and CUT nodes as well. First L was 3 then 7 then 10 which is where
it is at currently. Going from 3->10 lost a ply on average.

As regards reduction at the root, IMO it should not be done because
that reduces the chance of immediately switching to a plan B incase your
PV fails low. If you reduce all root moves except the first one, then
you effectively have no plan B which has equal privilages (search depth) as
the first move. So it makes more sense to me to search a couple of them
with the same search depth. We also need a really good move ordering there.
Quiescene search on the root moves just doesn't cut it for me. May be
something done with full width for a couple of moves (similar to multi-pv)
at a larger depth would be better. This is really an EBF vs Error issue as you
summed it up. The trend I have followed after this is to improve the EBF by
double reducing the further late moves on non-pv nodes. But this is not as
critical compared to reduction at pv nodes.

[bob]

I think it makes more sense to be more conservative on pv nodes.
Most programmers have a (node != PV) stuck somewhere in their LMR code.
I once experimented also on the threshold number ("L", I suppose)
for ALL and CUT nodes as well. First L was 3 then 7 then 10 which is where
it is at currently. Going from 3->10 lost a ply on average.

As regards reduction at the root, IMO it should not be done because
that reduces the chance of immediately switching to a plan B incase your
PV fails low. If you reduce all root moves except the first one, then
you effectively have no plan B which has equal privilages (search depth) as
the first move. So it makes more sense to me to search a couple of them
with the same search depth. We also need a really good move ordering there.
Quiescene search on the root moves just doesn't cut it for me. May be
something done with full width for a couple of moves (similar to multi-pv)
at a larger depth would be better. This is really an EBF vs Error issue as you
summed it up. The trend I have followed after this is to improve the EBF by
double reducing the further late moves on non-pv nodes. But this is not as
critical compared to reduction at pv nodes.

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

[zamar]

I've been thinking about this a lot lately. So far, haven't yet figured out a good solution.

Current rewrite can do it either way, and indeed so far, at the root, I reduce everything after the first move excluding the usual checks, captures, etc. however, I do pretty accurate root move ordering up front by doing a series of true-valued searches (quiesce only) to get a good score estimate for each root move.

Thoughts?

This was the first thing that also came into my mind, and of course this idea could be generalized to perform depth - N scout search for each move in root node. Haven't tested it, but I guess it must be a bad idea, because you are more likely to miss deep combinations (of which we are currently discussing in other thread.)

It's not the score, but more like the "forcing nature of the move" that should decide. The best (untested) idea I have is following:

In root node:
make move + null move. Make depth - N scout search to get exact score.

If score is high, move is forcing and requires immediate response from opponent. I'd say, move is interesting and should not be reduced. If score is only a bit over beta, it's unlikely that this move will turn out to be a killer and move should be reduced.

But again, this is just an idea And there are practical issues like finding right thresholds.

[Kempelen]

But the real issue for discussion as that on a PV node does it really make sense to be more conservative, or not?

Thoughts?

For root moves I have actually made test based on current iteration (i). At lowers i I am very conservative because the search is not very accurate yet and last moves could be candidates to be pv. But when i is high, the search has enought quality to be sure that those nodes could not be good.

Another idea is to put L a value depending in how many fails has produced last iterations. No fails, where the first move was always the first one say a lot about the score of the other moves.....

All this ideas can surely be apply to internal pv nodesl.

[Tord Romstad]

I currently don't reduce at all at the root, although I did it in the past. I'm not sure if it's better to reduce there or not -- like almost everything else, there has never been enough time to test it.

I'm pretty sure being far more conservative at PV nodes than at zero-width nodes works for me, though. It makes the search a lot more stable. The main drawback is that it makes re-searches after a fail high at the root very expensive.

I've also made various experiments where I use the number of plies up to the closest PV node as one of the ingredients in my reduction and pruning conditions, but I've never been able to prove that it helps. It also has the annoying side-effect of introducing more search inconsistencies.

Tord

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

I'm not saying that it's not important to make this distinction, I am saying that I have yet to have evidence to prove this.

When I'm conservative, the program slows down, but the strength improves at fixed depth. If I'm liberal, the program speeds up but it gets weaker. When I extrapolate the results using something like K * log(time) where K is calibrated by depth, most reasonable versions come within 10 ELO of each other, regardless of the fact that I use wildly varying parameters.

So my program does not seem to be very sensitive to any of these things. However, I can go too far in either direction and then I really do start getting bad results. I found that a reduction of 1 is too conservative and a reduction of 2 is too liberal. So I do reduce only 1 at PV nodes and 2 everywhere else. This is just a way to be more conservative, I have yet to prove there is any magic in the fact that I treat PV nodes differently. I might produce similar results if I simply reduced 2 ply at even depths and 1 ply at odd depths (I never tried this of course since there is no reason to try something this silly without a good reason.)

I also tried using a different number of moves to search and as long as I don't try too many, the program gets stronger but slower (by depth) and it ends up being a decision about whether I want the program to appear fast and dumb or slow and smart. I am like you, I don't care how slow or fast it is, I only care about the actual strength.

I have also experimented with various conditions to VETO LMR. I have all kinds of things I can use beyond the basic 2 or 3 things everyone uses (checks, out of check, captures and promotions) and it's hard to prove whether they make a difference or not. They slow the program down, but improve the quality, and so it seems to be a wash.

The program is measurably weaker if I'm not in the general ballpark. I still have to try at least 3 or 4 moves it seems, and if I try too many before reducing, it has a noticeable impact on strength. I think the sweet spot for my program is somewhere in the range of 3-10 moves that should be tried and again this will determine if my program iterated really fast or slowly, but it won't have much impact on the strength.

The real problem is that I cannot test this at deep levels and get a statistically reasonable number of samples. Being liberal really makes the branching factor low and thus it could really help. However it may also cripple the program beyond belief since I am taking big chances - so without a cluster like you have I have no real way of knowing - unless I am willing to take a couple of months to test this at real time controls.

[Don]

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.

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

I'm not saying that it's not important to make this distinction, I am saying that I have yet to have evidence to prove this.

So far, neither have I. I have found where it helps in some types of positions. Sometimes finding the solution 2-3 plies quicker and in much less time. But in my game testing, using time as the limit, nothing has helped (so far).

When I'm conservative, the program slows down, but the strength improves at fixed depth. If I'm liberal, the program speeds up but it gets weaker. When I extrapolate the results using something like K * log(time) where K is calibrated by depth, most reasonable versions come within 10 ELO of each other, regardless of the fact that I use wildly varying parameters.

So my program does not seem to be very sensitive to any of these things. However, I can go too far in either direction and then I really do start getting bad results. I found that a reduction of 1 is too conservative and a reduction of 2 is too liberal. So I do reduce only 1 at PV nodes and 2 everywhere else. This is just a way to be more conservative, I have yet to prove there is any magic in the fact that I treat PV nodes differently. I might produce similar results if I simply reduced 2 ply at even depths and 1 ply at odd depths (I never tried this of course since there is no reason to try something this silly without a good reason.)

I got worse results with 2 in my testing. And I even tried limiting the "2" reduction to moves that are really questionable, such as moving a piece to a square that is attacked by a lesser piece...

I also tried using a different number of moves to search and as long as I don't try too many, the program gets stronger but slower (by depth) and it ends up being a decision about whether I want the program to appear fast and dumb or slow and smart. I am like you, I don't care how slow or fast it is, I only care about the actual strength.

I have also experimented with various conditions to VETO LMR. I have all kinds of things I can use beyond the basic 2 or 3 things everyone uses (checks, out of check, captures and promotions) and it's hard to prove whether they make a difference or not. They slow the program down, but improve the quality, and so it seems to be a wash.

The program is measurably weaker if I'm not in the general ballpark. I still have to try at least 3 or 4 moves it seems, and if I try too many before reducing, it has a noticeable impact on strength. I think the sweet spot for my program is somewhere in the range of 3-10 moves that should be tried and again this will determine if my program iterated really fast or slowly, but it won't have much impact on the strength.

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.

The real problem is that I cannot test this at deep levels and get a statistically reasonable number of samples. Being liberal really makes the branching factor low and thus it could really help. However it may also cripple the program beyond belief since I am taking big chances - so without a cluster like you have I have no real way of knowing - unless I am willing to take a couple of months to test this at real time controls.

I am running some longer games right now, to compare the fast time controls to longer ones to see if there is any difference between the two different game lengths...