Iterative Deepening wird im Rahmen des Minimax-Algorithmus verwendet und hat den Vorteil, dass zu Beginn eines Durchlaufs die Suchtiefe nicht festgesetzt ist. Gerade dann, wenn ein Zeitlimit gegeben ist (wie zum Beispiel bei Wettbewerben), wird das Einsetzen des Minimax-Algorithmus erst sinnvoll möglich. [1]
Iterative Deepening ist beispielsweise auch im Rahmen des A*-Algorithmus einsetzbar.[2]
Die Suchtiefe wird immer um eins erhöht und der Vorgang mit dem Auslaufen des Zeitlimits abgebrochen - dann wird das zuletzt errechnete Ergebnis zurückgegeben.[2:1]
Der Overhead von Iterative Deepening ist recht gering. Der Verzweigungsfaktor ist meist recht hoch und da Ergebnisse aus den Berechnungen der oberen Ebenen bekannt sind, können die meisten Knoten durch den Einsatz der Alpha-Beta Suche ignoriert werden. Somit beschränken sich die meisten Berechnungen auf aktuelle Blattknoten, welche ohne Iterative Deepening sowieso berechnet würden. [1:1]
Papadopoulos, Athanasios, et al. "Exploring optimization strategies in board game abalone for alpha-beta search." 2012 IEEE Conference on Computational Intelligence and Games (CIG). IEEE, 2012 IEEE. ↩︎ ↩︎
Korf, Richard E. "Depth-first iterative-deepening: An optimal admissible tree search." Artificial Intelligence, vol. 27, no. 1, 1985, pp. 97-109. ISSN 0004-3702, ScienceDirect. ↩︎ ↩︎