Consider the graph below for an understanding on how IDS work.
Now my question is:
why do IDS start at the root every iteration, why not start at the previously searched depth in the context of minmax?
What is the intuition behind it?
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
Normally in minimax (or any form of depth-first search really), we do not store nodes in memory for the parts we have already searched. The tree is only implicit, it's not stored anywhere explicitly. We typically implement these algorithms in a recursive memory. As soon as we've finished searching a certain of the tree, none of the data for that subtree is retained in memory.
If you wanted to be able to continue the search from where you left off, you'd have to change this and actually store everything you've searched explicitly in memory. This can very quickly cause us to actually run out of memory and crash.
Intuitively, at first it certainly makes sense what you suggest in terms of computation time, i.e. it would avoid re-doing work we've already done (if it were practical in terms of memory usage). However, if you analyse exactly how much you would save, it turns out not to be much at all. Due to the exponential growth of the size of the search tree as depth increases, it is usually the case that the computation effort for the next level ($d + 1$) is much bigger than the computation effort already done for all previous depth levels ($1, 2, 3, \dots, d$) put together. So, while in theory we're wasting some time re-doing work we've already done, in practice it actually rarely hurts.
In the specific context of minimax with alpha-beta pruning, we get an additional benefit when re-doing the work. We get to make use of the estimated scores from our previous iteration to re-order the branches at the root, and with alpha-beta prunings this can actually make our search more efficient!
answered Sep 25, 2022 at 10:53
$\begingroup$
$\endgroup$
I could be mistaken since I don't know the source of the image you have provided, but that image appears to be showing how the tree is built, not how it is searched. Even so, when a balanced tree of the sort you have illustrated is searched, it will start with the root node, though in a search the maximum number of nodes traversed will be minimized and all operations (like min or max) will be performed in $O(h)$ where $h$ is the height of the tree.
