Relationship between move ordering and pruning

[Rebel]

Just out of curiosity, what do you feel is the relationship between evaluation quality and LMR/pruning?

Don

That's a hard nut to crack. After all my numeric failures during the years (with all kind of interesting new ideas for a better sorted list) it leaves me with the impression that search has a different kind of logic and responds extremely well on the use of 4 killer slots (2 from the current ply) and also 2 from the parent at least in the very first plies of the search and almost nothing can beat it. I think it has a (reasonable) explanation also. Searching more or less as often as possible the same moves which are good enough for a cut-ff builds a TT with many hits. Whereas adding smart (static) stuff to improve move-ordering pollutes this mechanism in the TT. For example, some 10+15 years ago I added 2 features to move ordering:

1. Give a penalty for moves which destination square has a SEE<0 (even for killers).
2. Give a bonus for moves which piece is hanging and moves to a safe square.
Looks great (better sorted move-list) but only gave a (disappointing) speed-up of 1-2% but perhaps is good for the LMR quality after all.

Therefore my (perhaps premature) gut feeling is that there hardly is a correllation between move ordering and evaluation. Hoewever LMR is a different amimal since it relies on the quality of the first moves. These 2 systems interact and not in a positive sense and a resonable comprise between the two is perhaps the best way out.

It's 1:45 AM, I am tired, hope I did not write too much nonsense. More tomorrow.

[lucasart]

Just out of curiosity, what do you feel is the relationship between evaluation quality and LMR/pruning?

Don

That is a tricky one. I really don't know for sure. But I'll still try a guess: perhaps the search behaves better with a more continuous eval ?

I don't have any sort of proof either, just a hunch. But I believe that a high quality evaluation function has a positive impact on selectivity. My idea here is that the better the evaluation function, the better the moves will be ordered in the absolute chess sense. That should not matter if the program doesn't know the difference, but the search sometimes DOES know the difference. So if you play a bad move because the evaluation doesn't understand, it will eventually show up as a problem that the search has to solve.

A silly example may help. Suppose your program doesn't understand that some move leaves a weak pawn? The evaluation doesn't know about that but the search is forced to defend that weak pawn. I have made the point before that search can enhance the positional play of a program significantly by means of this basic mechanism. Pressure on what it knows can force it to sense what it does not know. So I believe that good evaluation has a compounding effect like money in the bank that compound daily. The deeper you search the more important good evaluation becomes.

Imagine a program that can look 100 ply deep but has only material scoring for an evaluation function. It would probably appear to be playing incredibly strong positional chess. It would simulate to a large extent the missing evaluation features. But because it has poor understanding in general the move order would be horrendous.

Yes, I agree with that. Basically if your eval is good, then your qsearch() is already quite good. So at depth 1, the kind of moves that will fail high are already quite good, and the history is looking decent. And therefore, when ID does depth=2, it will use this for reducing quiet moves with bad history and so on. So there is quite some memory involved in the process. So if your eval is crap then qsearch() is crap, depth=1 is crap, fills history with crap which causes the wrong reductions at depth=2 and so on...

So I would say good eval + good qsearch(), as well as good history mechanism is the secret to good LMR.

PS: I don't like the name LMR. It's a rather poor choice as it puts the emphasis on "late" which is misleading. You do not reduce moves because they are "late" (that doesn't mean anything), you reduce them because they are likely to be bad, and because "late" is highly correlated with "bad" if you have a good history mechanism (but that is only for quiet moves, for example bad captures in front of quiet moves is a perfectly viable solution, IIRC IvanHoe does that?). So the emphasis should not be on late but on history instead. This is the real key! In that sense Fabien's name History Pruning is better, although pruning is also a bad choice. I think we should call it "History Reductions", simply

[Rebel]

PS: I don't like the name LMR. It's a rather poor choice as it puts the emphasis on "late" which is misleading. You do not reduce moves because they are "late" (that doesn't mean anything), you reduce them because they are likely to be bad, and because "late" is highly correlated with "bad" ...

This is not the thought behind LMR. The logic of LMR is about the observation that whenever x (usually 3) moves are searched likely all moves will be searched and thus the remaining moves are candidates for a reduction.

[Rebel]

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.

Ever tried PST move-ordering for the remaining moves? In mine it's still superior to every history mechanism I tried. The advantage of PST is that the information doesn't age.

[lucasart]

PS: I don't like the name LMR. It's a rather poor choice as it puts the emphasis on "late" which is misleading. You do not reduce moves because they are "late" (that doesn't mean anything), you reduce them because they are likely to be bad, and because "late" is highly correlated with "bad" ...

This is not the thought behind LMR. The logic of LMR is about the observation that whenever x (usually 3) moves are searched likely all moves will be searched and thus the remaining moves are candidates for a reduction.

I beg to disagree. Just try to order quiet moves randomly (just give them 0 ascore and let them be sorted as they come out of move generation), and then reduce every quiet move by 1 ply if the move count is >= 3... And do some testing, if you find an important elo gain, let me know, but I really doubt it...

PS: Ok if you are really smart about killers, it may partially compensate, but remove killers too and see what happens...

[lucasart]

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.

Ever tried PST move-ordering for the remaining moves? In mine it's still superior to every history mechanism I tried. The advantage of PST is that the information doesn't age.

Have you tried the Glaurung history method ? I bet it spanks your PST move ordering and other outdated tricks. Also, ageing is a key feature of history! Having a history that never ages is not a good idea.

[Rebel]

PS: I don't like the name LMR. It's a rather poor choice as it puts the emphasis on "late" which is misleading. You do not reduce moves because they are "late" (that doesn't mean anything), you reduce them because they are likely to be bad, and because "late" is highly correlated with "bad" ...

This is not the thought behind LMR. The logic of LMR is about the observation that whenever x (usually 3) moves are searched likely all moves will be searched and thus the remaining moves are candidates for a reduction.

I beg to disagree. Just try to order quiet moves randomly (just give them 0 ascore and let them be sorted as they come out of move generation), and then reduce every quiet move by 1 ply if the move count is >= 3... And do some testing, if you find an important elo gain, let me know, but I really doubt it...

PS: Ok if you are really smart about killers, it may partially compensate, but remove killers too and see what happens...

LMR is *not* about killers nor quiet moves. It's about the observation that once you have searched 3 moves it's likely you have to search all. And if the best move is in those first 3 moves you can safely reduce the remaining moves. That's LMR, the basic idea. The rest (the exceptions we make, captures, checks etc.) is fringe to intercept the unavoidable errors when the best move is not in the those first 3 moves searched at full depth.

[Rebel]

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.

Ever tried PST move-ordering for the remaining moves? In mine it's still superior to every history mechanism I tried. The advantage of PST is that the information doesn't age.

Have you tried the Glaurung history method ?

No, please elaborate.

I bet it spanks your PST move ordering and other outdated tricks. Also, ageing is a key feature of history! Having a history that never ages is not a good idea.

Show me your alpha-beta (move-ordering) percentage and I will show you mine.

[lucasart]

Have you tried the Glaurung history method ?

No, please elaborate.

You can have a look at what Stockfish does, as this part hasn't changed since Glaurung: github.com/mcostalba/stockfish.
It is surprisingly simple, yet very good
- a history table, indexed by piece type (6 piece types, P, N, B, R, Q, K) and target square
- when a move fails high, you add depth*depth
- for all other moves that *have been* searched at this node, you substract depth*depth
- whenever an history vbalue exceeds, in absolute value, HistoryMax = 2000, you divide all the elements of the array by 2

I bet it spanks your PST move ordering and other outdated tricks. Also, ageing is a key feature of history! Having a history that never ages is not a good idea.

Show me your alpha-beta (move-ordering) percentage and I will show you mine.

I don't know what you mean by move ordering %age. Do you mean how often the first move fails high, the second etc ? This can be misleading as we are only focused on quiet moves here, and this may depend on what we do with captures. Anyway, here's my move ordering. Note that capture here means captures and promotions (even non capturing promotions):

=> main search
- TT move if any
- good and equal captures, by descending SEE (in my engine, it performs slightly better than MVV/LVA)
- 2 killers (killerrs are only used for quiet moves)
- other quiet moves by history score
- bad captures by descending SEE

=> qsearch
Exactly the same except that I use MVV/LVA instead of SEE for sorting captures, and that I only generate queen promotions.

[Rebel]

Have you tried the Glaurung history method ?

No, please elaborate.

You can have a look at what Stockfish does, as this part hasn't changed since Glaurung: github.com/mcostalba/stockfish.
It is surprisingly simple, yet very good
- a history table, indexed by piece type (6 piece types, P, N, B, R, Q, K) and target square
- when a move fails high, you add depth*depth
- for all other moves that *have been* searched at this node, you substract depth*depth
- whenever an history vbalue exceeds, in absolute value, HistoryMax = 2000, you divide all the elements of the array by 2

Thanks for sharing. Yes I have tried this and various other variations on this theme during the last 32 years It works great for starters but if you already have a good move-ordering there hardly is any gain. I seldom look at code of others but does Stockfish limit the history values to a certain ply? During my experiments I noticed that there is something to gain if you limit the history table update to 8-10-12 ply (will depend per engine of course) since after that you only collect rubbish.