Iterative deepening 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, program has always an option to fall back to the move from the less deep 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.

Intuitively, Iterative deepening seems like a dubious idea because each repetition will repeat uselessly all the work done by previous repetitions.

• But, this useless repetition is not significant because a branching factor b > 1 implies that #nodes at depth k » #nodes at depth k-1 or less.
  • For a problem with branching factor b where the first solution is at depth k, the time complexity of iterative deepening is O(b^k), and its space complexity is O(b*k).