By writing an evaluation function that works on non-leaf game states, we can stop the recursion early. But in a perfect world, we’d still want to reach the leaves of the tree. In order to traverse farther down the tree without dramatically increasing the runtime, we can implement a technique called alpha-beta pruning.
The core idea behind alpha-beta pruning is to ignore parts of the tree that we know will be dead ends. For example, consider the gif on this page. When determining the “value” of the node labeled E, we can stop looking at possible moves as soon as it discovers the
We know that B will only consider values less than or equal to
5, and E will only consider values greater than or equal to
8. We know that node B will never care about E’s value and we can stop looking through E’s moves.
Similarly, we can prune a large section from the right half of the tree. There comes a point where node A will only consider values greater than or equal to
5 and node C will only consider values
3 and below. We can stop looking at all of the C’s children because we know they will never be relevant.
In the next lesson, we’ll implement alpha-beta pruning, but for now, take the time to study the gif on this page to understand how alpha-beta pruning works conceptually.