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

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.