moves are ordered in several ways. There are ways to get better history values. One can also use the evaluation (ala' stockfish and others) to order moves based on how they affect the score. I think the basic assumption that "move ordering is random" is not a given.matthewlai wrote:And like you said before, history heuristic is basically random noise.bob wrote: First they are not ordered randomly. IE the history heuristic for starters.
It doesn't change the fact that in PVS, once we run out of known good moves (hash move, killers, etc), we know very little about the rest of the moves. The 6th move and the 20th move have about the same (low) probability of failing high. Why do we search the 6th deeper than the 20th? If we want to reduce, wouldn't it make sense to reduce all these moves equally?But the main key is that most everyone uses PVS. Which means you search one move or you search all moves. Once you have searched more than one, the probability of this being an ALL node increases rapidly. and if that is the case, reducing effort has no risk at all, except when move ordering breaks down and a very late move suddenly fails high unexpectedly. But since this is rare, the idea of LMR is quite sound. You can prove that for perfectly ordered trees it is just as correct as pure alpha/beta when compared to minimax. So you toss an unfair coin, and most of the time you win. But you will lose some here and there. That's LMR in a nutshell.
Yes, that's more human. But humans are bad at chess. Why are we emulating humans?So to me, LMR is quite natural and sensible. Most people, given a task to do the same thing N times will find that the last instance of the task is done more quickly and more sloppily than the first. Watch someone paint on house trim for a while, and you'll see what I mean.
I ran a few simple tests quite a few months back, where instead of just counting fail highs on the first move, I counted them move by move. The numbers were far from random (i.e. the 20th counter was not the same as the 15th move counter). This done with history + a simple evaluation to sort by.
Move ordering is a topic by itself that deserves a lot of study, since LMR, LMP, et. al. depend on it even more than alpha/beta.