mcostalba wrote:Don wrote:
None of this changes my belief that you must try to always include the best move and that with any reasonable move ordering you can expect to find this move early in the list. The law of diminishing returns kicks in with a vengeance.
Also with no ordering at all you can expect to find a cut-off move early in the list....or don't find at all.
In my opinion, LMR is less about cut-offs and more about making sure you include the "best" move.
What you say is true of course, a powerful aspect of LMR is that if have not gotten a cut-off you probably won't and so it won't matter which moves you look at (because the search will fail low whether you happened to pick out the best move or not.) But I like to view this as a side-affect.
Imagine using LMR on PV nodes (where the alpha/beta window width is not artificially reduced.) LMR is still powerful and in this case there is no ambiguity about it's purpose - it is going to work well as long as you include the best move and it's not going to work well if you don't.
In my view it's conceptually simpler and more in the spirit of LMR to think of that way. The fact that in some positions you don't need the best move is a fortuitous thing that works to your advantage - but it's not the primary thing.
I know this might be considered just semantics but I think that I can argue that it's more correct in some sense than viewing is a gadget to achieve cut-offs with less work, although both are essentially correct. It's always useful to recast problems to see their various aspects - sort of like look at a diamond in different lighting conditions and different angles.
My primary argument for seeing it this way is simple. Remove alpha/beta and look at LMR from a purely mini-max point of view. Would it still work? Although I have not tried this exact experiment, I'm quite certain that LMR in a mini-max program would be far superior to mini-max without LMR. In fact it would probably be worth hundreds of ELO instead of just the 150-200 ELO it is worth in Komodo.
IMHO good ordering is just a second order optimization above something that already works independently from the order of the moves. And this something that works is move counting based pruning / reducing.
I agree with you on this. But experiments with Komodo prove empirically that this is a MAJOR second order optimization. One of the discoveries Larry and I have found is that once you have good move ordering, improving it does not speed the program up very much, but it helps LMR a LOT. We had previously always assumed that the benefit of better move ordering was pretty much equally divided between smaller trees AND increased likelihood that the best move would be searched full width.
Going along with this we found that we could push LMR farther if we payed attention to how the moves were ordered.
But my point is that IMHO we are _still_ far to find the optimal move counting rule (out of possible thousands) to prune / reduce the move under hypotesis of totally unsorted non-captures. We had a breakthrough about one year ago when in Ippo was shown a working multi reducing LMR approach that now have been adopted by almost all the engines. This demonstartes that IMHO there is still big room for improvment in statistical shaping the reducing / pruning rules, before to go to consider a better non-captures ordering.
We discovered progressive reductions on our own. In fact, a couple of years ago we were worried about the fact that Stockfish was still STRONGER than Komodo and they were not doing this! Our fear is that we would lose a lot of ground when other programs discovered these things. And of course we did lose ground when Stockfish started doing this.
Larry and I joked privately between ourselves about how difficult it would be to catch Stockfish if "they knew what we know" and also about how easy it would be to improve Stockfish but how hard it was to improve Komodo - even though Stockfish was ahead of us!
At that time we did not know anything about what Rybka was doing. Larry did not even know what LMR was and I had to teach him about this - now he is an equal in the engineering of the algorithms we use.
Even though Larry does not write a single line of code, he is an engineer at heart.
Strangely people is concentrated in finding a better ordering (possibly because is a more traditional and well unnderstood argument) then in finding a rule that better takes advantage of the statistical properites of teh search, as the multi reduced LMR was.
I have dreamed of this for a long time. In fact I am interested in applying the Bradley Terry model to the tree search in a probabilistic way. I believe that it's all about making sure the best move is included but it's possible using the Bradley Terry model and statistics gathered during the search (or off-line) to apply this principle in a much more formal way. We do it now with ad-hoc and simplistic rules but I have told Larry many times that I would like to completely scrap our search and rethink it from the ground up, trying to come up with new and interesting ideas and to give some real structure and formalism to existing ideas. Right now Komodo is no different than any other program which is a nasty collection of ad-hoc rules with tons of special case code and exceptions.
One thing that has always bothered me for instance is the sudden transition from main search to quies search. The distinctions is more blurred than it used to be, but so far it's still very clearly identifiable in any program I have looked at. I would like to do something about that and not just ad-hoc but in a very organized and logical way.