Don wrote:bob wrote:
Good case is the LMR stuff. I looked briefly at the Stockfish stuff of trying to increase the reduction as you complete more and more moves. But here's a question. Given two sets of moves, MA(i) and MB(i) where both MA and MB have the same number of moves, but in MA the first couple are good and the rest are lemons, while in MB all but the last couple are good. What is the justification for reducing the middle move in MA the same as the middle move in MB, when the middle move in MA is bad while the middle move in MB is good? No justification at all. Just force-fitting a linear value to a polynomial data set, and finding the best liner approximation you can get, even though it is bad in many cases.
I do not like the idea of reducing (or extending) something just because it comes before or after the Nth move in the list. Surely there must be a better reason. I certainly do not do that kind of nonsense as a human. I believe we can do this stuff pretty well (fit the wrong type of curve, but at least optimize the poor fit so that we arrive at the best "poor fit" we can get.)
I think the principle of waiting until the Nth move and then reducing has powerful justification. It turns out that modern chess programs with good move ordering have the characteristic that the first move is by far more likely to the best move than the second, and the second is far more likely than the 3rd and so on. By the time you have gotten to the Nth move, the probability that you have found a good (if not the best) move is extremely high.
If you believe that the "position" of a move should affect its reduction, you can run the test I ran.
Test 1. Rather than just counting fail highs on the first move (which I display in the stats as a rough measure of move ordering) I kept up with fail highs based on the order of the moves. Obviously most (92% on average in my case) happen on the first move. Is there any discernable pattern below that? That is, is there a greater likelihood of a fail high on the second as opposed to the 4th move? Turns out there was. But these were mostly in the good captures, or the killers. So,
Test 2. Count the fail highs by position, but only do this individual counting once I am past the killer move selection. In Crafty parlance, "REMAINING_MOVES" phase of move selection. And guess what? Random. A fail-high was just as likely at the first such move as it was on the last move. Which is why I do not do LMR on non-losing captures, or on killers, but most everything else gets reduced, except for safe checking moves.
granted, if you really do order the moves out in the tree in some way so that somehow "better" moves are searched earlier, then this would make perfect sense. I've not been willing, so far, to evaluate and sort all those moves into some sort of order because of the cost. I may try something with ordering at some point, but at present the "L" in LMR really is not very useful for what I am doing.
But it's not like we just throw out the rest, we evaluate them with a reduced depth search as a "test" to see if they should be search full depth.
So we are actually inspecting every single move pretty thoroughly and leaning on the fact that the best move is almost always one of the first moves considered.
Another way to view this is to speculate how you might improve on this decision without considering a moves position in the move list. The only reasonable thing I can imagine is evaluating each move with a reduced depth search. That is our very best way of evaluating moves. But the hash table move and often the killers are just as good or better than doing that.
Another criteria is dynamic considerations - but we already do that - captures and checks are not reduced either. So what is left?
You might re-think that. I do reduce losing captures, and unsafe checks, and found a measurable Elo gain by doing so. Don't remember the exact amount, but I posted it here a month or two back.
I think the position in the move list is an extremely powerful notion and it's combined with a thorough evaluation on top of that (the reduced depth search) so it's very difficult to improve on this.
You are troubled by the arbitrariness of N and I agree. So you could consider making N variable depending on many other factors such as depth, alpha/beta, score of position, stage of game, type of position and characteristics of moves already tried.
That falls into the trap I was talking to Larry about, that of trying to pick some formula that seems to work overall, but in reality it just works a little better in some positions than in others, just enough better to give a boost, while still being wrong in plenty of cases.
In fact we do a little of that. For LMR purposes we don't count moves that we would not normally reduce anyway. So we require N "quiet" moves before reducing. That is a small but measurable improvement for us and makes N slightly less arbitrary.
Don't disagree there. I try killers because I believe they are good "tries" at producing a cutoff, ditto for non-losing (SEE) captures. But that gives a justification, which is all I am looking for. In Crafty, the remainder of the moves are not in any particular order that suggests that the ones earlier in the list are better moves. I do generate moves by piece, and can control which pieces I search first, and I do control the order of the moves generated for each piece so that advances or centralizing moves come first. But a good knight move might be followed by 8 bad bishop moves followed by a good rook move, etc.
Been twiddling with it for 6+ months now and have some things that are working better.