About LMR & History reductions

[zamar]

LMR decides the reduction by move number. For me this seems a bit artificial as the number of "interesting moves" varies quite a lot from position to position.

* Has anyone tried to use (relative) history value (based on beta cut-offs) instead of move number to decide whether the move should be reduced?

* If you answered yes to question above, have you varied the size of reduction based on history value?

* Has anyone used multiple history tables (in simplest form, let's say you allocate history table for node when it's child node count exceeds for example 100'000)? Then you could use some linear combination of local & global history value.

* Are there other methods to decide move reductions than history value or move number.

[bob]

LMR decides the reduction by move number. For me this seems a bit artificial as the number of "interesting moves" varies quite a lot from position to position.

* Has anyone tried to use (relative) history value (based on beta cut-offs) instead of move number to decide whether the move should be reduced?

Yes. This was the original idea that was used and was the reason it was originally called "history pruning" in Fruit. Unfortunately the history counters get too "noisy" in deep searches and have nothing to do with what you are trying to determine.

Note that most don't just reduce moves that appear later in the move list. We typically try to avoid "interesting" moves such as checks, captures, passed pawn pushes, etc. I've been experimenting with a variable reduction amount so that really "uninteresting" moves are reduced more than just "uninteresting moves"... Sort of like I used to extend some "interesting moves" more than others

* If you answered yes to question above, have you varied the size of reduction based on history value?

Not that I am aware of. I know I never tried it, although as I mentioned, I am experimenting some with varying the reduction amount based on some static characteristics.

* Has anyone used multiple history tables (in simplest form, let's say you allocate history table for node when it's child node count exceeds for example 100'000)? Then you could use some linear combination of local & global history value.

* Are there other methods to decide move reductions than history value or move number.

[jdart]

Many people using this technique use history scores to decide which moves to reduce. As Bob Hyatt said, captures, checks and passed pawn pushes are typically excluded.

Arasan does history based LMR. In addition, Arasan reduces some moves by a double reduction amount, based on move order >6 and depth > 6. I haven't seen any bad effects from this variable reduction amount.

I have tried actually pruning (vs. reducing) moves that have very low history scores. This technique is used in Toga. But I have never gotten it to work satisfactorily.

--Jon