Alpha-beta pruning
Alpha is MAX’s best option on the path to root (starts out at negative infinity) Beta is MIN’s best option on the path to root (starts out at positive infinity)
In the max_value function, if we find a value of a successor that’s higher than the minimizer’s best path to root (the global minimum value so far), then we can break the function right there, because the rest doesn’t matter. We know that this current max_value isn’t going to be chosen by the minimizer, because it’s worse than something that it’s already seen. For each successor, we go through and update the max_value to be returned (max of itself (which starts out at -Infinity) and the value of the successor) and the alpha itself, which is the max of itself and the current max_value.
Things are exactly mirrored in the min_value case.
uid: 202006212052 tags: #algorithms