Iterative Deepening

From Chessprogramming wiki
Jump to: navigation, search

Home * Search * Iterative Deepening

Iterative deepening search [1]

Iterative deepening (ID) has been adopted as the basic time management strategy in depth-first searches, but has proved surprisingly beneficial as far as move ordering is concerned in alpha-beta and its enhancements. 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.

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 transposition table, 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] : 

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's Chess 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...

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

  1. ↑ Iterative deepening （反復深化法）
  2. ↑ 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)
  3. ↑ Richard Korf (1985). Depth-first Iterative-Deepening: An Optimal Admissible Tree Search. CiteSeerX
  4. ↑ Tsan-sheng Hsu (2010). Depth-First Iterative-Deepening: An Optimal Admissible Tree Search by R. E. Korf, slides as pdf
  5. ↑ David Slate, Larry Atkin (1977). CHESS 4.5 - The Northwestern University Chess Program. Chess Skill in Man and Machine, reprinted (1988) in Computer Chess Compendium
  6. ↑ Hans Berliner (1983). Search. Artificial Intelligence Syllabus, Department of Computer Science, Carnegie Mellon University
  7. ↑ Patrick Winston (1984). Artificial Intelligence. Addison-Wesley, Reading, MA
  8. ↑ 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.
  9. ↑ Tony Marsland (1992). Computer Chess and Search. Encyclopedia of Artificial Intelligence (2nd ed.) John Wiley & Sons, Inc. pdf preprint
  10. ↑ John J. Scott (1969). A chess-playing program. Machine Intelligence 4
  11. ↑ James Gillogly (1972). The Technology Chess Program. Artificial Intelligence, Vol. 3, pp. 145-163. ISSN 0004-3702. Reprinted (1988) in Computer Chess Compendium
  12. ↑ Re: "Iterative Deeping" reference wanted by Ira Baxter, AIList Digest, December 06, 1988
  13. ↑ quoted by Hans Berliner, Gordon Goetsch (1985). A Study of Search Methods : The Effect of Constraint Satisfaction and Adventurousness. pdf
  14. ↑ Paper is mentioned by Richard Korf at Judea Pearl Symposium, 2010

Up one Level

Retrieved from "https://www.chessprogramming.org/index.php?title=Iterative_Deepening&oldid=14825"