Differences

This shows you the differences between two versions of the page.

--- chess:programming:iterative_deepening [2021/10/12 12:15] – created peter
+++ chess:programming:iterative_deepening [2022/01/06 19:06] (current) – peter
@@ Line 7: / Line 7: @@
     * 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.