What do you use IID for

[Daniel Shawul]

Has anyone tried pruning a sub-tree on a fail high on a reduced depth search done for IID. The idea is from ProbeCut (probability cut), where it is assumed that a reduced depth search gives scores that are with-in a certain range at 95% or so confidence. Sounds like a nice idea, but has not been much successful in chess supposedly because scores can swing wildly in a ply or two, and that it overlaps with the concept of null-move. Anyway, for me I get a measurable tiny improvement from pruning captures which fail high on a reduced depth search. Stockfish has this in ProbeCut implementation that does its own reduced depth search. My IID search tends to be multi-purpose including this one that does a sort of ProbeCut. Another use of IID I have is to generate candidate moves to test for singularity even when we don't have something stored in TT. So that is two additional uses besides move ordering purposes, but all of this is due to an artificial mental block I have about writing a recursive search call in an iterative search. So that single IID search should use a depth to satisfy all the three needs. I thought it is an intersting approach, otherwise don't flame

[jdart]

pruning captures which fail high on a reduced depth search

Razoring sort of does this too, although it adds an eval test before the search.

Some programs only do IID on PV nodes, or do more reduction on non-PV nodes, or limit it in other ways, which might cause difficulties or limit its effectiveness if used for pruning. But as with anything, it is worth a try.

--Jon

[Daniel Shawul]

pruning captures which fail high on a reduced depth search

Razoring sort of does this too, although it adds an eval test before the search.

Some programs only do IID on PV nodes, or do more reduction on non-PV nodes, or limit it in other ways, which might cause difficulties or limit its effectiveness if used for pruning. But as with anything, it is worth a try.

--Jon

Yes I think razoring can be thought of as ProbCut where the probability aspect is removed with a big enough margin.

I decided to have my IID 'open ended' after noticing that many pruning/reduction/move-ordering decisions needed a call to a shallow call search. Specific reduced depth searches for each case may be better, but the simple one-for-all IID seems to work as well. Also many prunings in chess engines are redundant difficult to analyze. For example, now my qsearch have nothing but the compulsory stand-pat cutoff. Futility is redundant with lazy-eval, even that did not improve the engine, so I removed it.

[hgm]

It seems to me that what you call IID here is indistinguishable from 'conditional reduction' (e.g. like in LMR).

My engines typically implement LMR through 'self deepening', i.e. not by ordering a re-search on a high-failing move by making a second call to the same node with higher (unreduced) depth, but by calling it only once, passing the desired reduction as a parameter. The IID loop of the node will then not search upto the requested depth, but only upto depth-LMR. (Whether it starts there, or precedes it by even lower-depth iterations depends on the usual conditions for doing IID.) When the iteration for this depth fails low, an extra iteration is done at the full depth. No reason to return to the parent, and enter the same node again, having to redo the move generation, lose the move ordering etc.

The same idea also works to eliminate PVS re-searches, which do not need a larger depth, but a larger window. So I never pass -(alpha+1) for the daughter alpha in a null-window search, but always the original -beta (which of course often is already equal to -(alpha+1)), and leave it to the daughter node to close the window before it starts searching (if it is not a PV node, which it also knows). If the search fails low, it then redoes the iteration using the alpha passed to it, rather than beta-1.

[Daniel Shawul]

It seems to me that what you call IID here is indistinguishable from 'conditional reduction' (e.g. like in LMR).

My engines typically implement LMR through 'self deepening', i.e. not by ordering a re-search on a high-failing move by making a second call to the same node with higher (unreduced) depth, but by calling it only once, passing the desired reduction as a parameter. The IID loop of the node will then not search upto the requested depth, but only upto depth-LMR. (Whether it starts there, or precedes it by even lower-depth iterations depends on the usual conditions for doing IID.) When the iteration for this depth fails low, an extra iteration is done at the full depth. No reason to return to the parent, and enter the same node again, having to redo the move generation, lose the move ordering etc.

The same idea also works to eliminate PVS re-searches, which do not need a larger depth, but a larger window. So I never pass -(alpha+1) for the daughter alpha in a null-window search, but always the original -beta (which of course often is already equal to -(alpha+1)), and leave it to the daughter node to close the window before it starts searching (if it is not a PV node, which it also knows). If the search fails low, it then redoes the iteration using the alpha passed to it, rather than beta-1.

Yes I remember we talked about this before, and I also benefit from saving the move-generation too, done after implementing ABDADA. Other advantages are you can sort the move list based nodes count similar to what you do at the root.

Here I am more interested in using IID to do a sort of ProbCut. If a capture/promotion move fails high after IID, I immediately cut off the tree. The idea of ProbCut is that reduced depth search's score does not differ much from a full depth search, so you can cutoff with a certain confidence. I don't really see why we should cutoff only when the best move is a capture, but it is probably because of too many hanging pieces that a chess engine investigates, and also it seems to help so I use it. I wonder if there are other candidate cases (easy moves), that one can safely apply the IID fail high pruning (or ProbCut).

[hgm]

But stopping at a non-final IID iteration because it fails high is equivalent to doing a reduced search first, leave it at that when it fails low, but order a re-search at full depth when the reduced search failed high. But that is just LMR, although perhaps not only applied to 'late' moves.

I don't know if you had in mind to use a margin here, i.e. use a shifted window in the reduced search, and accept the result as final only when it fails low by a sufficiently large margin.

I once tried reducing moves that failed low by more than two Pawns by 4 ply, and only search at nominal depth when it failed low by less. This did not seem to maek the program any weaker, despite the fact that it sort of ruined the hashing (by replacing bounds of one type of high draft by bound of the opposite type and low draft during the reduced search, while the following full-depth search could have benefited from them).

[Daniel Shawul]

But stopping at a non-final IID iteration because it fails high is equivalent to doing a reduced search first, leave it at that when it fails low, but order a re-search at full depth when the reduced search failed high. But that is just LMR, although perhaps not only applied to 'late' moves.

I don't know if you had in mind to use a margin here, i.e. use a shifted window in the reduced search, and accept the result as final only when it fails low by a sufficiently large margin.

I once tried reducing moves that failed low by more than two Pawns by 4 ply, and only search at nominal depth when it failed low by less. This did not seem to make the program any weaker, despite the fact that it sort of ruined the hashing (by replacing bounds of one type of high draft by bound of the opposite type and low draft during the reduced search, while the following full-depth search could have benefited from them).

I just realized my razoring was implemented wrong for God knows how long, after you brought up margins here! I was calling qsearch() with un-shifted window, instead I did a comparison of the final score, score + margin < alpha, just like futility pruning in which score is eval() instead of a search value. This is never gonna catch fail low nodes that return alpha instead of a real score , but this bug may have been hard to detect due to the fact that qsearch() calls stand-pat immediately.

Anyway I don't do this for the IID fail high pruning, where margin is basically set to 0, but in a real ProbeCut when the best move is not as obvious as a capture, I guess the reduced depth search's window need to be shifted by the margin of confidence.

[hgm]

With margin 0 it seems to me that IID fail-high pruning is just LMR. You reduce when in the parent the reduced search fails low.

[bob]

pruning captures which fail high on a reduced depth search

Razoring sort of does this too, although it adds an eval test before the search.

Some programs only do IID on PV nodes, or do more reduction on non-PV nodes, or limit it in other ways, which might cause difficulties or limit its effectiveness if used for pruning. But as with anything, it is worth a try.

--Jon

I only do IID on PV nodes where there is no suggested hash move. That's its only purpose for me, find a good first move on a critical node, with less effort (reduced depth search).

[Daniel Shawul]

With margin 0 it seems to me that IID fail-high pruning is just LMR. You reduce when in the parent the reduced search fails low.

Well you can say the same thing for other fail-high prunings too if you take their effect back to the parent. There are too many prunings that overlap in this manner in modern chess engines.

Note that I use a reduction of 4 for non-pv nodes so it would be equivalent to a large reduction. Also it would be difficult to do the reduction directly on the parent node, because the effect here is that the parent move left some pieces hanging and the opponent found a winning capture. One would have to find moves that leave pieces hanging and reduce them by 4 plies to get the same effect.