True IID

[MOBMAT]

Harm,
Somewhere, I can't recall if it was on this forum or not, you had some posted some code that implemented what I had always thought was "true" Internal Iterative Deepening (IID). When I first heard about IID I understood the concept to be that inside a search node, the available moves are searched the same way they are from the root, iteratively (p1, p2, p3, etc) up to the maximum search depth for the node, kind of like a recursive Iterative search.

I've seen implementations of what is being called IID that just don't seem to do what IID was originally designed as. Most implementations are just simple lower depth searches to find a possible starting candidate for PV when one isn't available.

If that is the case, then what is being called IID should be called something else, IMHO.

Can you post your code or point to where it is? I would like to play with the idea but want to see an example of a correct implementation.

[Ras]

Do you mean something like this that HGM posted?

http://www.talkchess.com/forum3/viewtop ... 06#p724769
http://www.talkchess.com/forum3/viewtop ... 37#p701916

[flok]

Harm,
Somewhere, I can't recall if it was on this forum or not, you had some posted some code that implemented what I had always thought was "true" Internal Iterative Deepening (IID). When I first heard about IID I understood the concept to be that inside a search node, the available moves are searched the same way they are from the root, iteratively (p1, p2, p3, etc) up to the maximum search depth for the node, kind of like a recursive Iterative search.

With what purpose?
Why not just:

Most implementations are just simple lower depth searches to find a possible starting candidate for PV when one isn't available.

[flok]

Harm,
Somewhere, I can't recall if it was on this forum or not, you had some posted some code that implemented what I had always thought was "true" Internal Iterative Deepening (IID). When I first heard about IID I understood the concept to be that inside a search node, the available moves are searched the same way they are from the root, iteratively (p1, p2, p3, etc) up to the maximum search depth for the node, kind of like a recursive Iterative search.

With what purpose?
Why not just:

Most implementations are just simple lower depth searches to find a possible starting candidate for PV when one isn't available.

Never mind: the post by hgm explains it.

[hgm]

I think it is mainly an implementation question, whether the same thing is achieved iteratively or recursively. You can always rewrite an iterative process for(i=0; i<N; i++) F(i); by a recursive one void G(int n) { if(n) G(n-1); F(n); }. Could be a bit inefficient, though, if F(n) can be decomposed into { H(); F'(n); }, because then you could call H() before the loop, while it would be called in every instance of G(). You can think of F() as Search(), and H() as MoveGen().

Likewise the textbook description of LMR as score = -Search(d-lmr); if(score > alpha) score = -Search(d); should just be considered stupid pseudo-code; an efficient implementation would make sure the depth-independent part of Search() was never executed twice, by merging both calls to Search() into one, and let that one call do both the d-lmr and d search, the latter only when the former fails high.