====== Chess - Programming - Iterative Deepening ======

**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).
  

----

===== Internal Iterative Deepening =====

If we do not have a hash move to search first, perform a shallow search (say two ply less).

The best move returned from this search is then searched first.

Note that if we do not have a hash move at depth eight, we also will not have a hash move at depth six, four, two and finally zero, where the quiescence search will provide us with a move to start off with - hence **internal iterative deepening**.

The extra searches have a negligible cost compared to the time saved by improving the move ordering.