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?
True iterative search...
Moderators: hgm, Rebel, chrisw
-
- Posts: 267
- Joined: Thu Jul 07, 2011 10:31 pm
- Location: Denmark
-
- Posts: 27790
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: True iterative search...
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.
-
- Posts: 267
- Joined: Thu Jul 07, 2011 10:31 pm
- Location: Denmark
Re: True iterative search...
I'm afraid this is too theoretic for me. It is a very long time since I read about fail-low and fail-high.hgm wrote: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.
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
-
- Posts: 1822
- Joined: Thu Mar 09, 2006 11:54 pm
- Location: The Netherlands
Re: True iterative search...
When done well, iterative search is faster at modern processors, as storing all the recursions is not so ideal at all processors.JBNielsen wrote: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?
Yet doing it efficient and fast is not so easy.
-
- Posts: 27790
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: True iterative search...
Look for instance here: http://www.talkchess.com/forum/viewtopi ... 4&start=10
-
- Posts: 267
- Joined: Thu Jul 07, 2011 10:31 pm
- Location: Denmark
Re: True iterative search...
Thanks for a good list of possible improvements.hgm wrote:Look for instance here: http://www.talkchess.com/forum/viewtopi ... 4&start=10
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...
-
- Posts: 5557
- Joined: Tue Feb 28, 2012 11:56 pm
Re: True iterative search...
You might want to fix the bug that results in nullmove not working well.JBNielsen wrote:I have disabled nullmoves.
It did not work very well; perhaps colliding with the hashtables.
Since you mention colliding with hash tables, are you hashing the side to move into the hash key?
-
- Posts: 267
- Joined: Thu Jul 07, 2011 10:31 pm
- Location: Denmark
Re: True iterative search...
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......syzygy wrote:You might want to fix the bug that results in nullmove not working well.JBNielsen wrote:I have disabled nullmoves.
It did not work very well; perhaps colliding with the hashtables.
Since you mention colliding with hash tables, are you hashing the side to move into the hash key?
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: True iterative search...
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.JBNielsen wrote: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......syzygy wrote:You might want to fix the bug that results in nullmove not working well.JBNielsen wrote:I have disabled nullmoves.
It did not work very well; perhaps colliding with the hashtables.
Since you mention colliding with hash tables, are you hashing the side to move into the hash key?
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
-
- Posts: 267
- Joined: Thu Jul 07, 2011 10:31 pm
- Location: Denmark
Re: True iterative search...
So the node(s) above the nullmove never contains a PV with the nullmove?! Hmmmm.Sven Schüle wrote: 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
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...