Iterative Deepening Question

[Sven]

[...]
I think the problem comes from misunderstanding the different roles of the ID loop and the full-width search processing the root node.

When someone says "iterative deepening" I use the traditional definition, which is what is done at the root. "internal iterative deepening" is a different topic and there you are correct. Only question is, which is he talking about???

He is not talking about "internal iterative deepening", and nor am I. What you call "traditional definition" (of iterative deepening) seems to be different from what other people think about it. Talking about Crafty, we are at "iterate.c" level (but with aspiration window - I did not look into recent Crafty code to check whether that is present there but older Crafty did not have it as far as I know).

Iterative deepening is exactly what goes on in iterate.c, and yes, I have used aspiration windows in every version of Crafty that was distributed. As has PVS always been there. That is what I call "iterative deepening" which was as defined by Slate in chess 4.x...

Yes, you are right, iterate.c contains aspiration window code for a long time already, sorry. I was reading the code too quickly.

Still my previous comments are valid. The ID loop calls the main search function with "root_alpha, root_beta, depth" and not with "-root_beta, -root_alpha, depth - 1".

[hgm]

I don't "put the deepening loop outside the search function", being outside is the standard.

Well, for one I did not mean 'you' personally, but "If one put ...", and I don't see how it matters that this is stadard. If you follow the standard, which you apparently do, you do put it outside the search function, right?

If you do it differently then this is probably caused by using IID in your code. Apart from that, what you write is correct but I don't see where I claimed the opposite of that ...

Indeed I always do this differently, as Search() in my engines contains an IID loop anyway, which can just as easily be used for ID. I wasn't accusing you of anything; I just pointed out that it doesn't really matter how you implemented ID, and that on fail highs you always immediately re-search the failing move, while on fail lows you redo the iteration. If the deepening loop is inside the search routine this would require addition of some code to handle the fail-high case. But that is basically the same code as you need in PVS, where you also need to re-search moves that fail high.

In fact immediate re-searches are a strong indication of poor design, as you duplicate the effort ofmove generation and sorting for no good reason. So I usually implement it as self-re-searching in the daughter node, where it simply redoes the iteration with enlarged window if the iteration failed low (meaning the move leading to it failed high) compared to the aspirated window limit. Or add extra iteration(s) to the IID loop (for LMR re-searches).

[bob]

[...]
I think the problem comes from misunderstanding the different roles of the ID loop and the full-width search processing the root node.

When someone says "iterative deepening" I use the traditional definition, which is what is done at the root. "internal iterative deepening" is a different topic and there you are correct. Only question is, which is he talking about???

He is not talking about "internal iterative deepening", and nor am I. What you call "traditional definition" (of iterative deepening) seems to be different from what other people think about it. Talking about Crafty, we are at "iterate.c" level (but with aspiration window - I did not look into recent Crafty code to check whether that is present there but older Crafty did not have it as far as I know).

Iterative deepening is exactly what goes on in iterate.c, and yes, I have used aspiration windows in every version of Crafty that was distributed. As has PVS always been there. That is what I call "iterative deepening" which was as defined by Slate in chess 4.x...

Yes, you are right, iterate.c contains aspiration window code for a long time already, sorry. I was reading the code too quickly.

Still my previous comments are valid. The ID loop calls the main search function with "root_alpha, root_beta, depth" and not with "-root_beta, -root_alpha, depth - 1".

As I said, if you are talking about iterate.c, no you do not use -AlphaBeta, nor do you flip alpha and beta and negate them. Internally you do, and that was what I assumed, since the post also had "depth-1" in the call, which is certainly not done at the top of the tree in Iterate()...