It has been noticed, that even if one is about to search to a given depth, that iterative deepening is faster than searching for the given depth immediately. This is due to dynamic move ordering techniques such as; PV-, hash- and refutation moves determined in previous iteration(s), as well the history heuristic.
It works as follows: the program starts with a one ply search, then increments the search depth and does another search. This process is repeated until the time allocated for the search is exhausted. In case of an unfinished search, the program always has the option to fall back to the move selected in the last iteration of the search. Yet if we make sure that this move is searched first in the next iteration, then overwriting the new move with the old one becomes unnecessary. This way, also the results from the partial search can be accepted - though in case of a severe drop of the score it is wise to allocate some more time, as the first alternative is often a bad capture, delaying the loss instead of preventing it.
Iterative or progressive deepening was first mentioned by Adriaan de Groot in Thought and Choice in Chess[2] . Richard Korf on its "discovery" in Depth-first Iterative-Deepening: An Optimal Admissible Tree Search[3][4] :
Depth-first iterative-deepening has no doubt been rediscovered many times independently. The first use of the algorithm that is documented in the literature is in Slate and Atkin'sChess 4.5 program [5]. Berliner[6] has observed that breadth-first search is inferior to the iterative-deepening algorithm. Winston[7] shows that for two-person game searches where only terminal-node static evaluations are counted in the cost, the extra computation required by iterative-deepening is insignificant. Pearl initially suggested the iterative-deepening extension of A*, and Berliner and Goetsch[8] have implemented such an algorithm concurrently with this work.
Tony Marsland in Computer Chess and Search on the History of ID [9] :
In the early 1970’s several people tried a variety of ways to control the exponential growth of the tree search. A simple fixed depth search is inflexible, especially if it must be completed within a specified time. This difficulty was noted by Scott[10] who reported in 1969 on the effective use of an iterated search. Jim Gillogly, author of the Tech chess program [11] , coined the term iterative deepening to distinguish a full-width search to increasing depths from the progressively more focused search described by de Groot. About the same time David Slate and Larry Atkin (1977) sought a better time control mechanism, and introduced an improved iterated search for carrying out a progressively deeper and deeper analysis. For example, an iterated series of 1-ply, 2-ply, 3-ply ... searches is carried out, with each new search first retracing the best path from the previous iteration and then extending the search by one ply. Early experimenters with this scheme were surprised to find that the iterated search often required less time than an equivalent direct search...
Adriaan de Groot (1965). Thought and Choice in Chess. Mouton & Co Publishers, The Hague, The Netherlands. Second edition 1978. ISBN 90-279-7914-6. (amazon)
Alexander Reinefeld, Tony Marsland (1994). Enhanced Iterative-Deepening Search.IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 16, No. 7, pp. 701-710. ISSN 0162-8828. pdf
^Adriaan de Groot (1965). Thought and Choice in Chess. Mouton & Co Publishers, The Hague, The Netherlands. Second edition 1978. ISBN 90-279-7914-6. (amazon)
^Richard Korf (1985). Depth-first Iterative-Deepening: An Optimal Admissible Tree Search. CiteSeerX
^Tsan-sheng Hsu (2010). Depth-First Iterative-Deepening: An Optimal Admissible Tree Search by R. E. Korf, slides as pdf
^Hans Berliner, Gordon Goetsch (1984). A quantitative study of search methods and the effect of constraint satisfaction. Tech. Report CMU-CS-84-147, Department of Computer Science, Carnegie Mellon University, Pittsburgh, PA.
^Tony Marsland (1992). Computer Chess and Search. Encyclopedia of Artificial Intelligence (2nd ed.) John Wiley & Sons, Inc. pdf preprint
It has been noticed, that even if one is about to search to a given depth, that iterative deepening is faster than searching for the given depth immediately. This is due to dynamic move ordering techniques such as; PV-, hash- and refutation moves determined in previous iteration(s), as well the history heuristic.
Table of Contents
How it Works
It works as follows: the program starts with a one ply search, then increments the search depth and does another search. This process is repeated until the time allocated for the search is exhausted. In case of an unfinished search, the program always has the option to fall back to the move selected in the last iteration of the search. Yet if we make sure that this move is searched first in the next iteration, then overwriting the new move with the old one becomes unnecessary. This way, also the results from the partial search can be accepted - though in case of a severe drop of the score it is wise to allocate some more time, as the first alternative is often a bad capture, delaying the loss instead of preventing it.Iterative deepening, using a TT, embed the depth-first algorithms like alpha-beta into a framework with best-first characteristics.
History
Iterative or progressive deepening was first mentioned by Adriaan de Groot in Thought and Choice in Chess [2] . Richard Korf on its "discovery" in Depth-first Iterative-Deepening: An Optimal Admissible Tree Search [3] [4] :Tony Marsland in Computer Chess and Search on the History of ID [9] :
See also
Publications
1965 ...
1970 ...
1980 ...
1990 ...
Forum Posts
1988
1990 ...
2000 ...
2010 ...
External Links
feat. Michał Urbaniak, Zbigniew Namysłowski, Urszula Dudziak, Kenny Kirkland, Tony Bunn, Laurenda Featherstone
References
Up one Level