A question about Stockfish and LMR or other pruning...

[Zenmastur]

When a move that has previously been subject to LMR or other pruning becomes the best move why doesn't the search depth get reset to the depth that this move would have been found if no LRM or other pruning took place. e.g. after a move is discovered to be good at a depth of 15 plies (with 6 plies of LMR say) so the main search is already at 21 plies, it would seem beneficial to re-set the depth to 15 plies and continue from there.

On many occasions I have run into the problem where a move is found to be good very deep in the search, say 60 to 70 plies, but at this depth it will take a very long time to flesh-out the best continuation, so I restart the search. Usually the line of play will be picked up at a much shallower depth were the search will go much faster. I'm wondering if this was incorporated into an engine if it would show an ELO gain if done under the proper conditions. My suspicion is that it would.

Has this been tried before?

Regards,

Forrest

[bob]

When a move that has previously been subject to LMR or other pruning becomes the best move why doesn't the search depth get reset to the depth that this move would have been found if no LRM or other pruning took place. e.g. after a move is discovered to be good at a depth of 15 plies (with 6 plies of LMR say) so the main search is already at 21 plies, it would seem beneficial to re-set the depth to 15 plies and continue from there.

On many occasions I have run into the problem where a move is found to be good very deep in the search, say 60 to 70 plies, but at this depth it will take a very long time to flesh-out the best continuation, so I restart the search. Usually the line of play will be picked up at a much shallower depth were the search will go much faster. I'm wondering if this was incorporated into an engine if it would show an ELO gain if done under the proper conditions. My suspicion is that it would.

Has this been tried before?

Regards,

Forrest

If you look at any LMR program, when a move fails high, the reductions disappear, because no one reduces the first move at any ply, and the move that failed high would now be the first move searched..

I am not sure what you think you are seeing...

[Zenmastur]

When a move that has previously been subject to LMR or other pruning becomes the best move why doesn't the search depth get reset to the depth that this move would have been found if no LRM or other pruning took place. e.g. after a move is discovered to be good at a depth of 15 plies (with 6 plies of LMR say) so the main search is already at 21 plies, it would seem beneficial to re-set the depth to 15 plies and continue from there.

On many occasions I have run into the problem where a move is found to be good very deep in the search, say 60 to 70 plies, but at this depth it will take a very long time to flesh-out the best continuation, so I restart the search. Usually the line of play will be picked up at a much shallower depth were the search will go much faster. I'm wondering if this was incorporated into an engine if it would show an ELO gain if done under the proper conditions. My suspicion is that it would.

Has this been tried before?

Regards,

Forrest

If you look at any LMR program, when a move fails high, the reductions disappear, because no one reduces the first move at any ply, and the move that failed high would now be the first move searched..

I am not sure what you think you are seeing...

I'm seeing that if I restart the search I arrive at the same or better PV/score in much less time than if I let the program run on its own. E.G.

If I let a search run over night, I do this every night with multiple searches running. Lets say it gets to 59 plies, which is an average depth, and a score of +11.15 and it's associated PV after 8 hours. Now, as a test, I clear the TT and start the search from scratch. I let it run for 20 minutes and it reaches a depth of 44 plies and displays a score of +1.57. At 45 plies the score jumps to +5.63 and the PV changes a move at the 6th ply. Now, I restart the search. After a seconds or so, it re-finds the line leading to the +5.63 score at ply 32 and starts calculating from there. If there is nothing of interest in this line at lower ply levels the program will simply start yanking info out of the cache and in short order return to it's pervious ply level (45 in this example). Most of the time this is not what happens. There are other moves that were also pruned that are NOW of interest and it will do more searching at a depth of 32, 33, etc. Since the program is now working at shallower depths the search goes much quicker. Most times you end up with a superior score in less time.

On some occasions, after a restart, it will get multiple fail high's in a row and you may end up at a depth greater than 45 (say 51) in a few minutes with a score greater than +11.15. More often it will arrive at ply 45 with a much greater score than the first iteration. And if this process is repeated you can easily end up with a score much greater than +11.15 in much, much less time than leaving the program run unattended for 8 hours.
So the point is, there are enough moves missed at lower levels due to LMR and pruning that when a reduce move is found best it may behoove the program to reset the depth to the depth this move was found at and continue from there. (This assumes that there is enough of a difference between the two depths to justify a restart. This isn't always the case.) Doing this manually though a GUI interface generates big gains. I can generally do as much or more in an hour as an 8-hour unattended session run over night. It would be much quicker and less wasteful if the program did it automatically since when this is done manually you start back at ply 1 every time. It would be better to start at the depth that caused the change.

This is at long time controls of course. I see no reason why it wouldn't work at short time controls. The gains may not be as much at short time controls because over head is much higher percentage of time used so you may have to be more selective with the depth differences.

If this explanation isn't clear enough to understand I can generate examples from my analysis.

Crafty does this as well, so its nothing peculiar to SF.


Regards,

Forrest

[zullil]

When a move that has previously been subject to LMR or other pruning becomes the best move why doesn't the search depth get reset to the depth that this move would have been found if no LRM or other pruning took place. e.g. after a move is discovered to be good at a depth of 15 plies (with 6 plies of LMR say) so the main search is already at 21 plies, it would seem beneficial to re-set the depth to 15 plies and continue from there.

On many occasions I have run into the problem where a move is found to be good very deep in the search, say 60 to 70 plies, but at this depth it will take a very long time to flesh-out the best continuation, so I restart the search. Usually the line of play will be picked up at a much shallower depth were the search will go much faster. I'm wondering if this was incorporated into an engine if it would show an ELO gain if done under the proper conditions. My suspicion is that it would.

Has this been tried before?

Regards,

Forrest

Your post reminded me of a feature that Robert Houdart implemented in Houdini. Not sure if this is directly relevant, but you might look at

http://www.talkchess.com/forum/viewtopi ... highlight=

[Uri Blass]

My experience is that stockfish often has wrong fail highs so I am afraid that if I reduce the depth it can also lead to a wrong move.

[Zenmastur]

When a move that has previously been subject to LMR or other pruning becomes the best move why doesn't the search depth get reset to the depth that this move would have been found if no LRM or other pruning took place. e.g. after a move is discovered to be good at a depth of 15 plies (with 6 plies of LMR say) so the main search is already at 21 plies, it would seem beneficial to re-set the depth to 15 plies and continue from there.

On many occasions I have run into the problem where a move is found to be good very deep in the search, say 60 to 70 plies, but at this depth it will take a very long time to flesh-out the best continuation, so I restart the search. Usually the line of play will be picked up at a much shallower depth were the search will go much faster. I'm wondering if this was incorporated into an engine if it would show an ELO gain if done under the proper conditions. My suspicion is that it would.

Has this been tried before?

Regards,

Forrest

Your post reminded me of a feature that Robert Houdart implemented in Houdini. Not sure if this is directly relevant, but you might look at

http://www.talkchess.com/forum/viewtopi ... highlight=

I glanced at this topic and it looks very close to what I was considering. Actually, I was considering allowing the current iteration to complete or at least let the fail-high resolve itself before the depth was re-set. Doing this before then sounds dangerous unless you understand your search very well. I guess it could work, I'll have to read the full thread to get a better understanding of how this affects things.

My experience is that stockfish often has wrong fail highs so I am afraid that if I reduce the depth it can also lead to a wrong move.

It might work the way Robert explains, but waiting until the fail high has resolved it-self then reset the depth, will work. The effect should be almost identical. You may not save as much time, but there wont be any problems with false fail-highs.

The idea is that if the move is significantly reduced before the fail-high this will save time and discover new moves that were formerly thought to be bad and reduced or pruned.

I know it can work because I restart searches all the time for this exact purpose. I just do it manually, which always resets the depth to zero, which is wasteful.

I believe that this could also be done farther down into the search with good effect. I.E. without the a fail high under certain conditions.

Regards,

Zen

Regards,

Zen

[Stan Arts]

Yes it's possible in some cases that when you have to resolve a fail low/high, that searching from a lower depth with the deeper available hash info will resolve you a best line quicker and get through the new depth faster.

I've tried this once.. Reduce depth by one if there's a fail high/low at the root. It behaves a bit funny. Searchdepth going up and down looks a bit confusing, have to take a lot of precautions not to end up in never ending loops, causes a bunch of extra search instability and in a lot of cases you have to do the same amount of work anyway so yeah.. I quickly removed it.
A crude hackjob for something that should probably be more elegantly fixed in the search. (With smarter IID for example.)

[hgm]

It always bothered me that in IID, when at some large depth your hash move fails low for the first time, you will start finding another best move at this large depth, without having zero info on them (as all previous iterations got a cutoff after only the hash move was searched). This could potentially be very expensive, as you might pick a number of nonsense moves as 2nd, 3rd...

It seemed better that when a move fails high in a non-final IID iteration, to first deepen that single move to the ultimate depth, or untill it no longer fails hight, and only then resume iteration at the depth where it first failed high (where the hashed full-depth score will now make it fail low in all subsequent iterations). This allows you to at least cheaply weed out no-good alternatives, and hopefully find another move that wants to fail high, and then deepen that to see if it also works where the other one started to fail low, etc.

This doesn't help in the root, however, where the problem perceived by the OP occurs.

It is true, however, that the new move that improved on the old PV move will be searched to the same depth as the old PV before it is assumed to be indeed better, and that this only involves the sub-tree from that move, and would generally involve IID from there. So in a sense the search does restart at the reduced depth; the engine just doesn't print it, because the deepening takes place in a d=1 node, and it only prints d=0 iterations.

I am not sure how it could be better to deepen in the root. Moves other than the original PV move and the new one replacing it would still have the same reduction, no matter what. So they should be satisfiable from the has table, and there really would not be any difference between deepening from the root or the d=1 node.

[bob]

When a move that has previously been subject to LMR or other pruning becomes the best move why doesn't the search depth get reset to the depth that this move would have been found if no LRM or other pruning took place. e.g. after a move is discovered to be good at a depth of 15 plies (with 6 plies of LMR say) so the main search is already at 21 plies, it would seem beneficial to re-set the depth to 15 plies and continue from there.

On many occasions I have run into the problem where a move is found to be good very deep in the search, say 60 to 70 plies, but at this depth it will take a very long time to flesh-out the best continuation, so I restart the search. Usually the line of play will be picked up at a much shallower depth were the search will go much faster. I'm wondering if this was incorporated into an engine if it would show an ELO gain if done under the proper conditions. My suspicion is that it would.

Has this been tried before?

Regards,

Forrest

If you look at any LMR program, when a move fails high, the reductions disappear, because no one reduces the first move at any ply, and the move that failed high would now be the first move searched..

I am not sure what you think you are seeing...

I'm seeing that if I restart the search I arrive at the same or better PV/score in much less time than if I let the program run on its own. E.G.

If I let a search run over night, I do this every night with multiple searches running. Lets say it gets to 59 plies, which is an average depth, and a score of +11.15 and it's associated PV after 8 hours. Now, as a test, I clear the TT and start the search from scratch. I let it run for 20 minutes and it reaches a depth of 44 plies and displays a score of +1.57. At 45 plies the score jumps to +5.63 and the PV changes a move at the 6th ply. Now, I restart the search. After a seconds or so, it re-finds the line leading to the +5.63 score at ply 32 and starts calculating from there. If there is nothing of interest in this line at lower ply levels the program will simply start yanking info out of the cache and in short order return to it's pervious ply level (45 in this example). Most of the time this is not what happens. There are other moves that were also pruned that are NOW of interest and it will do more searching at a depth of 32, 33, etc. Since the program is now working at shallower depths the search goes much quicker. Most times you end up with a superior score in less time.

On some occasions, after a restart, it will get multiple fail high's in a row and you may end up at a depth greater than 45 (say 51) in a few minutes with a score greater than +11.15. More often it will arrive at ply 45 with a much greater score than the first iteration. And if this process is repeated you can easily end up with a score much greater than +11.15 in much, much less time than leaving the program run unattended for 8 hours.
So the point is, there are enough moves missed at lower levels due to LMR and pruning that when a reduce move is found best it may behoove the program to reset the depth to the depth this move was found at and continue from there. (This assumes that there is enough of a difference between the two depths to justify a restart. This isn't always the case.) Doing this manually though a GUI interface generates big gains. I can generally do as much or more in an hour as an 8-hour unattended session run over night. It would be much quicker and less wasteful if the program did it automatically since when this is done manually you start back at ply 1 every time. It would be better to start at the depth that caused the change.

This is at long time controls of course. I see no reason why it wouldn't work at short time controls. The gains may not be as much at short time controls because over head is much higher percentage of time used so you may have to be more selective with the depth differences.

If this explanation isn't clear enough to understand I can generate examples from my analysis.

Crafty does this as well, so its nothing peculiar to SF.


Regards,

Forrest

That is probably just random noise. History table values affect move ordering, and they change all the time. If you stop/re-start, you start off with different values than when you previously did the search. And as a result, you get different move ordering. LMR is sensitive to ordering and the shape of the tree can change dramatically due to this simple action. Hash table entries also affect move ordering (hash move is usually searched first) so you get yet another random change when you start over...

[Zenmastur]

Yes it's possible in some cases that when you have to resolve a fail low/high, that searching from a lower depth with the deeper available hash info will resolve you a best line quicker and get through the new depth faster.

I've tried this once.. Reduce depth by one if there's a fail high/low at the root. It behaves a bit funny. Searchdepth going up and down looks a bit confusing, have to take a lot of precautions not to end up in never ending loops, causes a bunch of extra search instability and in a lot of cases you have to do the same amount of work anyway so yeah.. I quickly removed it.
A crude hackjob for something that should probably be more elegantly fixed in the search. (With smarter IID for example.)

I'm not talking about a reduction of a single ply since this is unlikely to produce much of a savings in time, especially at shorter time controls. Also, you can't have a never ending loop since you will run out of time. If you are doing the same amount of work anyway, it means you aren't using the right conditional trigger. Nothing more or less.

That is probably just random noise...

He says with a completely dismissive tone in his voice...

If it's just random noise than it wouldn't be repeatable from occasion to occasion. Therefore it's not JUST random noise!

History table values affect move ordering, and they change all the time. If you stop/re-start, you start off with different values than when you previously did the search. And as a result, you get different move ordering. LMR is sensitive to ordering and the shape of the tree can change dramatically due to this simple action. Hash table entries also affect move ordering (hash move is usually searched first) so you get yet another random change when you start over...

OK, lets consider the conditions when this might be useful. First, I don't use this technique unless one side has an advantage. Second, a move failing high isn't sufficient reason to use this technique. At a very minimum, a fail high must have occurred and a move change in the PV at a relatively high level, i.e. close to the root. How much of an advantage is needed for this to be useful is up for debate (25-50 centi-pawn?? of course higher is better here). I don't know how close the move change in the PV need to be to the root as I haven't tried to systematically test this. A rough guess is at least half the search depth and a third is probably better. e.g. on a 30 ply search if one or more fail-highs have occurred and a move change in the PV occurred at ply 10 (a third of the search depth) then its probably going to save time. The exact parameters would have to be determined by testing of course. This would be relatively easy to test in the SF testing framework I would think.

In any case, it does work and its not just random noise. I use it all the time to drive a good position to a winning position by finding better moves in less time!

Regards,

Forrest