If a value is less than alpha, we don't prune, but we still don't consider it interesting, because we know there's a better move somewhere else in the tree. However, especially if we are using iterated deepening, it is likely that we have a pretty good idea what the principal variation is going to look like. In this case, we know that it returned the correct value, and we can safely choose the move in the search tree leading to a node with that value. This condition is known as a fail high . This condition is known as a fail low .
Analysis Let's do an analysis of alpha-beta search to see why it's such a useful idea.
We'll see next time what we need to do to make alpha-beta search behave in a way consistent with this analysis. In class I did this analysis only considering shallow cuts, but in these lecture notes I'll include deep cuts as well, because it makes the analysis much simpler. Effectively, alpha-beta search ends up reducing the branching factor to the square root of its original value, and lets one search twice as deeply.