LMR based on IID

[thomasahle]

In Leela's search the choice of nodes to search is based partly on the prior and partly on the Q-scores/past search results of the nodes.

It seems to me the equivalent in alpha-beta engines would be using the search scores from low depth search to guide reductions at higher depth. Similar to how static eval scores are already commonly used for LMR.

I thought internal iterative deepening (IID) might be ideal for this, since we already have the child scores at the parent node. But I haven't seen this described anywhere.

Do some engines already bade LMR on lower depth search? Are there any reasons not to?

[xr_a_y]

LMR often have an "history" part (sometimes substancial) that depends on previous searches indeed although not directly linked with IID.

[thomasahle]

Isn't the "history" part just the normal history heuristic used for move sorting? That is "how many times in sibling nodes did this move cause a beta cut?"

[Mike Sherwin]

In Leela's search the choice of nodes to search is based partly on the prior and partly on the Q-scores/past search results of the nodes.

It seems to me the equivalent in alpha-beta engines would be using the search scores from low depth search to guide reductions at higher depth. Similar to how static eval scores are already commonly used for LMR.

I thought internal iterative deepening (IID) might be ideal for this, since we already have the child scores at the parent node. But I haven't seen this described anywhere.

Do some engines already bade LMR on lower depth search? Are there any reasons not to?

Isn't it already being done sortof? One searches to a lower depth in LMR and then if the returned value is > alpha the move is searched to full depth.

[hgm]

In Leela's search the choice of nodes to search is based partly on the prior and partly on the Q-scores/past search results of the nodes.

It seems to me the equivalent in alpha-beta engines would be using the search scores from low depth search to guide reductions at higher depth. Similar to how static eval scores are already commonly used for LMR.

I thought internal iterative deepening (IID) might be ideal for this, since we already have the child scores at the parent node. But I haven't seen this described anywhere.

Do some engines already bade LMR on lower depth search? Are there any reasons not to?

The problem is that LMR is done in all-nodes. In a cut node you only search the cut-move, and never get to the late moves. But unlike Leela, in alpha-beta the scores of all the moves are completely unkown: the only thing you do know is that they all score below alpha. So the lower-depth search gives you no information at all.

Of course you could abandon alpha-beta, and make the window for a lower-depth search in an IID framework larger than needed (lowering alpha). Then scores between the lowered alpha and the true alpha would be exact. But that does make this lower-depth search more expensive than it would otherwise be. So it is probably only affordable at depth that are really a lot lower than the requested depth.

[thomasahle]

Those are good points. I hadn't fully considered the influence of alpha beta on the approach.

What about this: 1) You first search everything at a reduced depth. 2) Then you re-search everything > alpha at full depth. First the moves > beta, and then the moves between alpha and beta sorted reversely by there score. (Of course everything that was above beta you could re-search immediately.) 3) You reduce/ignore the moves that fell below alpha.

Oops, maybe this is exactly how Mike says LMR already works..