Alpha-beta pruning - Python教程

- [Instructor] We still have that billions of years problem. So a first attempt to solve it is called alpha-beta pruning. It's based on the observation that, when analyzing a min node or max node, some options can't possibly be the min or max value we are looking for. So these options can be safely left unchecked. Now, remember that an option in the minimax tree is a sub-tree that can be pruned off. So our hope with this pruning is to get rid of a lot of unnecessary work. However, the task still seems uphill. Do you think we'll be able to shrink 300 times 10 to the 15 years down to something reasonable like 10 years? We'll see how well alpha-beta pruning actually does a little later. For now, let me show you how it works. Consider the same example we used for minimax. I will guide you through the whole process again, but this time we'll follow the alpha-beta search algorithm. Now, for the left sub-tree, Action A, we'll follow the whole process, and then we'll fast forward a bit for the sub-trees of actions B and C. So, first, we analyze the left branches until we reach a terminal node. So now that you know how minimax works, notice how the min node at Level 2 gets a partial result. So far, the maximum value it has seen is 1. This value is not final. The next value is minus 2, which is less than 1, so it doesn't update the partial max value. And the next is 9, which updates the max value in Level 2. Now we are done with all three moves. So the max value of 9 is finalized at Level 2. This value is in turn affecting the partial result of the min node in Level 1. The next max node in Level 2 examines the values, 0, which is the highest so far, then 4, which now becomes the highest so far, and, finally, 3. So 4 is the final max value. Updating the min value at Level 1. The right-most move is where the pruning starts to happen. First, we get a value of 5, which becomes the highest so far. At this point, this max node at Level 2 is aware of the best value its parent node at Level 1 has seen. This best min value is called beta and its value is 4. So think about this. We are currently evaluating a max node, so its value can only get higher than 5, but our parent node will pick the minimum value among our sibling nodes, and it already has 4 as a candidate. Therefore, there's no point in looking further at this max node. This is where we prune off some branches. Right now, we have skipped two nodes to analyze. This finalizes the value of the max node at Level 2. So the min value for Move A at Level 1 is finalized at 4. The same happens at the top level. 4 becomes the maximum value it has seen so far. This number is known as alpha. Now let's fast forward some steps in the middle sub-tree. At this point, I've propagated the max value of minus 1 from Level 2 into the partial min value at Level 1. But, look, it's time for some pruning again. Notice that the top max node has seen a max value of 4 so far. So anything less than this alpha of 4 is reason enough to stop checking at the min node in Level 1. The reason is that checking more values will only reduce the min value in Level 1. So we are sure it's not going to be chosen by the top level as a replacement for alpha. So we might as well stop now. Notice that we've pruned off two sub-trees. That's eight nodes off our to-do list. That finalizes the min value of minus 1 for Move B at Level 1. Now let's fast forward again in the sub-tree for Move C. Once again, we have a tentative value of 8 at Level 1. So we may prune off options that change this value to anything less than alpha, our best max value so far, which is still 4. The middle move produces 2, which is less than 8, thus modifying the min value at Level 1. But, wait, this value of 2 is also less than 4, so we are done checking options at Level 1. We've pruned off yet another sub-tree with four nodes. This again finalizes all of our values, and we can safely choose Option A. Now let me remove the pruned-off nodes so you can appreciate how the tree has slimmed down.