How does LMR work? Fundamentally, the idea is that when we do move ordering, we sort moves that are more likely to be the best towards the front, and we want to spend proportionally more time on moves that are more likely the best than moves that are less likely to be the best, given the parent position.
In traditional chess engines, the probability distribution is not explicit. When the move ordering returns "A, B, C, D, E", there's no way to tell whether it's "50%, 49%, 0.5%, 0.3%, 0.2%" or "22%, 21%, 20%, 19%, 18%". Obviously the correct reduction schedule is very different for these 2 cases.
Most programs use a fixed reduction schedule (except for Stockfish, which has a few tables and adjustments). That works on average because we know that the probability distribution is monotonically decreasing, so we are right more often than we are wrong, when we just apply a simple constant reduction schedule.
But can we do better?
When we do the move sorting, we already had more information. We knew which ones came from hash, good capture, killer, or history (and what the history is). Why throw away all that information and reduce everything to a simple ranking, before deciding on the reductions?
Why not estimate a probability distribution instead, and use that for both sorting and reducing?
How to estimate the probability distribution from all those information? I have no idea. Fortunately for me, I don't have to worry about that too much, because Giraffe is learning it by herself.
I haven't quite figured out how to incorporate path-dependent information, yet, but here's some results with no path-dependent info (model is a neural network of course) -
Code: Select all
0: 15.67% (15.67)
1: 10.64% (26.31)
2: 7.28% (33.59)
3: 4.79% (38.38)
4: 3.72% (42.1)
5: 2.98% (45.08)
6: 2.18% (47.26)
7: 2.07% (49.33)
8: 1.41% (50.74)
9: 1.57% (52.31)
10: 1.32% (53.63)
11: 1.17% (54.8)
12: 0.98% (55.78)
13: 0.85% (56.63)
14: 0.77% (57.4)
15: 0.62% (58.02)
16: 0.46% (58.48)
17: 0.4% (58.88)
18: 0.32% (59.2)
19: 0.26% (59.46)
Average Confidence: 0.152621
Each ranking also comes with a probability distribution. The actual best move, on average, has a predicted probability of 15.26%.
This only includes positions where the best move is not a SEE-winning capture (most of them are regular quiet moves, and a few are sacrifices).
Some programs do things like sorting moves toward the centre first, or by eval change, etc. It should be possible to get better ordering by spending more time on statistical things like how in the opening, pawn moves are more likely to be best than king moves, etc. It may actually be beneficial to spend more time on statically evaluating moves in addition to positions.