Reductions from internal iterative deepening

[Evert]

I've had an idea that I may not have time to explore for a little while yet, but some preliminary explorations (with test positions) suggested that something could be gained from it, so I was wondering whether anyone has tested something similar more thoroughly.

The idea is quite simple: after internal iterative deepening, we not only have a move (which is the point), we also have an estimate for the score (at reduced depth). If this score is below alpha (with some margin), then this node is likely to be poor and we can reduce the remaining depth (obviously not to the depth reached by iterative deepening, although there may be cases where we could trust the IID score as-is). I suspect it won't do anything (at best) if you only do IID at PV nodes because there's too few of them (I don't; I never found that it was better to only do IID at PV nodes so I always do it).

This seems like an obvious thing to try, so I was wondering whether anyone has played around with this idea?

[hgm]

This is kind of the opposite of what I do in Spartacus. Reducing a node when it fails low is logically equivalent to reducing the move in the caller leading to it when it fails high. Usually this is not what you want, as reducing moves that fail high is an invitation to horizon effect.

So in Spartacus I do the opposite: when a node fails low at the reduced depth (which can be viewed as an earlier IID iteration) I do another iteration at the full depth. This to implement LMR in a more efficient way. In the node-type flag passed to Search it is indicated whether the preceding move was 'late', and if not, the full depth is forced in any case. Even if the move is late, when the (reduced) null move fails low through a refutation with the last-moved piece, I force full depth as well.

[Don]

I've had an idea that I may not have time to explore for a little while yet, but some preliminary explorations (with test positions) suggested that something could be gained from it, so I was wondering whether anyone has tested something similar more thoroughly.

The idea is quite simple: after internal iterative deepening, we not only have a move (which is the point), we also have an estimate for the score (at reduced depth). If this score is below alpha (with some margin), then this node is likely to be poor and we can reduce the remaining depth (obviously not to the depth reached by iterative deepening, although there may be cases where we could trust the IID score as-is). I suspect it won't do anything (at best) if you only do IID at PV nodes because there's too few of them (I don't; I never found that it was better to only do IID at PV nodes so I always do it).

This seems like an obvious thing to try, so I was wondering whether anyone has played around with this idea?

Those type of idea can be very dangerous unless great care is taken but they can give you a small gain if you use appropriate margins. You have to test ideas like that very thoroughly.

[Sven]

Reducing a node when it fails low is logically equivalent to reducing the move in the caller leading to it when it fails high.

How is that equivalent? The move failing low is just one of several moves, and presumably not the best one in this case. But reducing the parent would mean to reduce all its children, which is not the same as reducing only one of them. It would be the same if all siblings would fail low but that is not the situation described by Evert. So I guess the two are not equivalent at all.

Sven

[Don]

Reducing a node when it fails low is logically equivalent to reducing the move in the caller leading to it when it fails high.

How is that equivalent? The move failing low is just one of several moves, and presumably not the best one in this case. But reducing the parent would mean to reduce all its children, which is not the same as reducing only one of them. It would be the same if all siblings would fail low but that is not the situation described by Evert. So I guess the two are not equivalent at all.

Sven

I think this is just semantics, HG didn't say to reduce the parent, he said the MOVE in the caller.

[Sven]

Reducing a node when it fails low is logically equivalent to reducing the move in the caller leading to it when it fails high.

How is that equivalent? The move failing low is just one of several moves, and presumably not the best one in this case. But reducing the parent would mean to reduce all its children, which is not the same as reducing only one of them. It would be the same if all siblings would fail low but that is not the situation described by Evert. So I guess the two are not equivalent at all.

Sven

I think this is just semantics, HG didn't say to reduce the parent, he said the MOVE in the caller.

Ok, I see that I missed that part.

But it is still not "equivalent" for me. There is no such case where you "reduce a move (at the parent node) when it fails low", since if it fails low then you have already searched it. So this is not what Evert wants to do. He wants to reduce a node if IID fails low. The search does not return to the parent after IID is done but continues at the child.

I agree that it may be dangerous to follow that idea by Evert, and that it would require very careful testing, but I don't agree to HGM whose statement could be read as if the idea were simply wrong.

Sven

[Don]

Reducing a node when it fails low is logically equivalent to reducing the move in the caller leading to it when it fails high.

How is that equivalent? The move failing low is just one of several moves, and presumably not the best one in this case. But reducing the parent would mean to reduce all its children, which is not the same as reducing only one of them. It would be the same if all siblings would fail low but that is not the situation described by Evert. So I guess the two are not equivalent at all.

Sven

I think this is just semantics, HG didn't say to reduce the parent, he said the MOVE in the caller.

Ok, I see that I missed that part.

But it is still not "equivalent" for me. There is no such case where you "reduce a move (at the parent node) when it fails low", since if it fails low then you have already searched it. So this is not what Evert wants to do. He wants to reduce a node if IID fails low. The search does not return to the parent after IID is done but continues at the child.

I agree that it may be dangerous to follow that idea by Evert, and that it would require very careful testing, but I don't agree to HGM whose statement could be read as if the idea were simply wrong.

Sven

I don't think it's obviously wrong either.

Why can't you reduce a move and have it fail high or low?

[hgm]

How is that equivalent? The move failing low is just one of several moves, and presumably not the best one in this case.

Evert is not talking about reducing one move when it fails low, but doing one less iteration when an earlier iteration fails low. That is reducing all moves.

There is no such case where you "reduce a move (at the parent node) when it fails low", since if it fails low then you have already searched it.

You do the reduced search first, of course. That is how IID works: you don't start with the maximum depth, and then iterate over lower depth. Then it would have been called IIR in stead of IID...

[Evert]

This is kind of the opposite of what I do in Spartacus. Reducing a node when it fails low is logically equivalent to reducing the move in the caller leading to it when it fails high. Usually this is not what you want, as reducing moves that fail high is an invitation to horizon effect.

I see what you're saying, but I'm not entirely sure that I follow the logic entirely. Why can't you use the same argument against reducing any move, or LMR in general?

LMR is actually what I was thinking of initially, the thought being that you want to apply agressive LMR at nodes where you expect all moves to fail low. The usual criterion is to reduce as you go down the move list (or when move scores drop below a certain threshold) when it becomes less and less likely that a move will cause a cut-off (ie, the move is an All-node). If we've already searched the node (with reduced depth) <i>and</i> it turned out to be an All-node, that could be an indication that the node will again turn out to be an All-node.

There are a number of peculiarities in the search that I didn't mention that interact with this, of course. In Jazz' search, the first move is never reduced, and if there is only a single legal reply out of check the search is also never reduced (rather extended on top of the check extension, under certain conditions). In the "IID reduction" I explicitly excluded in-check and situations where the search bounds indicate a mate-search.
Last but not least, I also do an immediate verification search at full-depth if a reduced move does not fail low as expected. All of these things will affect how well (if at all) this idea works.

I just realised that there is a build-in inconsistency though: I don't do IID (of course) if I already have a move from the TT, which means this reduction is also not triggered in that case. Can't say I think that's pretty, but I don't know if it's a problem.

I ran a quick (self) test with a simple and naive implementation of the idea, and it scored 52%, but with only 2000 games that's inconclusive...

[Evert]

Those type of idea can be very dangerous unless great care is taken but they can give you a small gain if you use appropriate margins. You have to test ideas like that very thoroughly.

So you're saying that with a fairly weak program like mine, I have more productive things to do?