True iterative search...

[JBNielsen]

Dabbaba performs an iterative search, but not a recursive search inside the tree.

Example:
If Dabbaba in iteration 7 of calculating a move in the starting position tries to reject 1.f4 by -,Nf6 as it has done in the previous iterations, but now suddenly fails to reject it, it must try another move like 1.-,d5.
Dabbaba has not met this position earlier in the search.
So now Dabbaba performs a search from here of depth 5 (7 minus 2) WITHOUT iterative deepening.

Does anyone have an idea how much this missing ability slows the search?

[hgm]

I think almost every engine would search without deepening after an earlier move fell through. Inside the sub-tree (i.e. the node after d5) they might do Internal Iterative Deepening, but many strong engines don't even do that unless it is a PV move. In micro-Max, which does IID in every node, I have experimented with self-deepening, where Search() has two depth parameters, a minimum and a maximum. After the minimum depth is reached it would then only continue deepening as long as iterations fail low, or the maximum is reached. This means that the preceeding high-failing move is automatically deepened to the max, but if at some high depth it starts to fail low, the search of alternatives starts at low depth again. This made micro-Max search 20% faster. But in other engines it helps less.

[JBNielsen]

I think almost every engine would search without deepening after an earlier move fell through. Inside the sub-tree (i.e. the node after d5) they might do Internal Iterative Deepening, but many strong engines don't even do that unless it is a PV move. In micro-Max, which does IID in every node, I have experimented with self-deepening, where Search() has two depth parameters, a minimum and a maximum. After the minimum depth is reached it would then only continue deepening as long as iterations fail low, or the maximum is reached. This means that the preceeding high-failing move is automatically deepened to the max, but if at some high depth it starts to fail low, the search of alternatives starts at low depth again. This made micro-Max search 20% faster. But in other engines it helps less.

I'm afraid this is too theoretic for me. It is a very long time since I read about fail-low and fail-high.
It would be easier for me if some moves/lines were given as examples.

But I understand, that IID will not help much with the challenge I address here: http://74.220.23.57/forum/viewtopic.php?t=46170

[diep]

Dabbaba performs an iterative search, but not a recursive search inside the tree.

Example:
If Dabbaba in iteration 7 of calculating a move in the starting position tries to reject 1.f4 by -,Nf6 as it has done in the previous iterations, but now suddenly fails to reject it, it must try another move like 1.-,d5.
Dabbaba has not met this position earlier in the search.
So now Dabbaba performs a search from here of depth 5 (7 minus 2) WITHOUT iterative deepening.

Does anyone have an idea how much this missing ability slows the search?

When done well, iterative search is faster at modern processors, as storing all the recursions is not so ideal at all processors.

Yet doing it efficient and fast is not so easy.

[hgm]

Look for instance here: http://www.talkchess.com/forum/viewtopi ... 4&start=10

[JBNielsen]

Look for instance here: http://www.talkchess.com/forum/viewtopi ... 4&start=10

Thanks for a good list of possible improvements.

I use a simple A-B search (without a window based on a score of the previous move/iteration)

My Q-search only evaluates quiet positions if possible.

I have 2 simple killers for each ply in the tree.

I have disabled nullmoves.
It did not work very well; perhaps colliding with the hashtables.

I use LMR - and extend other lines with checks(few moves), captures...

I use SEE to find the best moves for the Q-search.
Also for move-ordering in the whole tree.
So much that it fx will defend a rook instead of moving a knight that can be captured.

I do not use IID or PVS (do not really understand what PVS is).

Hope to find something to improve...

[syzygy]

I have disabled nullmoves.
It did not work very well; perhaps colliding with the hashtables.

You might want to fix the bug that results in nullmove not working well.
Since you mention colliding with hash tables, are you hashing the side to move into the hash key?

[JBNielsen]

I have disabled nullmoves.
It did not work very well; perhaps colliding with the hashtables.

You might want to fix the bug that results in nullmove not working well.
Since you mention colliding with hash tables, are you hashing the side to move into the hash key?

Yes I do. But it may be something with the depth stored along the score. What is the depth when there are nullmoves involved in the line......

[Sven]

I have disabled nullmoves.
It did not work very well; perhaps colliding with the hashtables.

You might want to fix the bug that results in nullmove not working well.
Since you mention colliding with hash tables, are you hashing the side to move into the hash key?

Yes I do. But it may be something with the depth stored along the score. What is the depth when there are nullmoves involved in the line......

Is it possible that you store the distance to the root node instead of the remaining depth? That would explain why you think that "nullmoves involved in the line" play any role. The PV of a node will never contain a null move.

By not storing the distance to root you become independent from transpositions occurring at different heights in the tree. The remaining depth is necessary, though, for replacement purposes (you trust more in deep search results than in shallow search results for the same position), but also for the search itself to decide whether a stored hash table value shall be used or not (it must have a stored depth >= the current remaining depth).

Sven

[JBNielsen]

Is it possible that you store the distance to the root node instead of the remaining depth? That would explain why you think that "nullmoves involved in the line" play any role. The PV of a node will never contain a null move.
Sven

So the node(s) above the nullmove never contains a PV with the nullmove?! Hmmmm.

I do store the remaining depht. But as far as I remember I tried with several nullmoves in a line, and perhaps this is causing problems...
It might be worth to have a look at it again...