lucasart wrote:Don wrote:Over the years there has been a constant tendency to increase the amount of pruning and reductions in my program. What is a bit odd about this is that what didn't work before appears to work now. We do very aggressive forward pruning as well as LMR. So why is this?
One of the the things that has improved over time is our move ordering. We have the classic stuff as well as modern improvements and a couple twists of our own, all designed to improve move ordering. Probably the biggest advance in move ordering beyond the classic capture MVVLVA and killer stuff is the history heuristic. That has been around a very long time but not in it's current form which is basically a rapidly "aged" table of move success rates.
This is true, but at the same time rather obvious.
It's always been obvious to me, but apparently this is not as obvious as you think because many smart people are not aware of how strong that relationship is. For example even Bob Hyatt didn't much believe in history and has been critical of how LMR works - not believing it should have anything to do with the moves position in the list. I think he has fairly recently changed his viewpoint somewhat but you can see his thinking from posts that are not that old. I am very careful about what I say is "obvious" these days because everything becomes obvious once you are educated to it. It's obvious to me the earth is not flat.
I sometimes make posts like this to education those who need to be educated. This was a golden opportunity to prove the powerful connection.
The key breakthrough that allowed LMR to be performant is the combination of Fabien's idea of using the history value for reduction (what he then called "history pruning") and Tord's idea of how to make a better history mechanism.
Treatement of captures hasn't change before/after the Fruit/Glaurung breakthrough. Still sorted by MVV/LVA (or SEE). But sorting quiet moves by history and using the history value (or move count which amounts to the same) to make better reduction decision is *the* breakthrough.
Yes, I agree that this is a very accurate assessment of the state of the art and why it works so well when done right.
Please note that the traditional move ordering was until recently considered "excellent" or state of the art. It generally follows a standard formula: 1. hash table move, 2. MVV/LVA captures, 3. killers 4. "all the rest." A more recent improvement is SEE to place the losing capture either to the end of the capture list or after the killers. Category 4 moves were sometimes sorted by some variant of Jonathon Shaeffer style of history which was a non-trivial gain but apparently is not worth much if anything these days (in that form.) Some programs used other heuristics such as moves to the center first or piece value table sorted but none of these were anything significant and do not compare to the modern way that you are explaining.
Now it's all about "how"
- how to make history tables better: Tord's implementation with piece * square and +/- depth^2 increment was quite an improvement compared to doing +/-1 to the history table (like in Fruit and probably most previous programs). I've also found that the ceiling value after which you reduce the array to prevent overflow is quite impactful (history should have a too long or too short memory so to speak).
- tuning the reduction as a function of the move count etc. Glaurung further extended Fruit's history pruning here: better history table (see above) fractional ply reduction with a well tuned smooth increase in reduction as the move count count increases (or as the history value decreases, take your pick).
Quiet moves are extremely important, because:
1/ there are *lots* of them
2/ therefore sorting them well is of utmost importance
3/ and reducing them too. making good decisions on which quiet moves to reduce is extremely important. come to think of it that's what humans do too! Besides, no reducing a capture isn't so bad: one piece less on the board followed by exchanges etc means less on the board hence smaller branching factor. And captures are important (we musn't miss long and complex capture sequences).
Of course making a modification to history mechanism (and sorting in general) should be considered carefully as it is very intertwined with LMR. For example to experiment with a history table mechanism, I think it makes more sense to switch off any kind of LMR and compare the effect of that only. Good history is good moves sortedf first, hence an improvement over a plain and simple alpha/beta. Then a good LMR comes on top of a good history. Not the other way around or the two at the same time.
Recently I have done some experimentation with improving the way I score history in Komodo. I did not isolate LMR from this experiment as you suggest but without exception I found that anything that improved the strength of the program correlated almost perfectly with increase depth as well as ELO. For example if I tested at fixed depth levels the version that was faster also had a higher ELO. There was no trade-off in this case where you gain some speed at the sacrifice of ELO and have to pick the best trade-off, as most things are. I agree that this doesn't prove the move ordering was actually "better", it is possible that it was only better when combined with LMR - but that's really all that I care about anyway. I would not want to tune it without LMR only to find that I have to re-tuned it for LMR. But I do sometimes do experiments to isolate one thing from another as it can lead to new insights.
It's not just LMR that is at stake here either. We do some pretty severe forward pruning too which is move order sensitive.
Same goes for futility pruning (if move count dependant like in SF) or move count pruning. I think one should optimize sorting as much as possible on a plain alpha/beta (with PVS hash table and everything except LMR and move count dependant reductionb/pruning) before implementing/tuning LMR/move count pruning/futility pruning.
I don't consider that true futility pruning, at least not in the classical sense. Classical futility takes you into quies a ply early - and an extension of the idea is to perhaps go into quies a couple of ply early. Komodo does not go into quies early as such, it just treats a futility node as if it were the first ply of quies (captures and checks) but then returns to the main search. We still call it futility pruning but that is semantics. Stockfish on the other hand has a more sophisticated mechanism which is very futility-like but changes the margin based on the move number and can include quiet moves and also examines it's relationship to the so-called "threat move" which is a by-product of the null move search.
We actually have similar mechanisms too but we don't have any consideration for the threat move - we do not' see it as futility but it's forward pruning based on the move count with some tactical considerations too.
Some of this is just terminology and semantics. The deeper principles are the same and any good program makes use of them. Looking at the chessprogramming wiki I see that definitions of various techniques tend to "evolve" or change over the years. A prime example is the definition of "highly selective" compared to "brute force" which has undergone a complete transformation. What is now considered "brute force" would have been considered ridiculously selective 30 years ago. I blame this on a lack of historical perspective.
That was my initial trial to get history reductions to work and gave 20-30 elo. The history table itself was not used for move-ordering and does not exist any longer. The page is out-dated since I found out that LMR (without history tables) simply gives more. For move-ordering the right place to look for is