Alpha-beta pruning is accomplished by keeping track of two variables for each node — alpha and beta. alpha keeps track of the minimum score the maximizing player can possibly get. It starts at negative infinity and gets updated as that minimum score increases.
On the other hand, beta represents the maximum score the minimizing player can possibly get. It starts at positive infinity and will decrease as that maximum possible score decreases.
For any node, if alpha is greater than or equal to beta, that means that we can stop looking through that node’s children.
To implement this in our code, we’ll have to include two new parameters in our function — alpha and beta. When we first call minimax() we’ll set alpha to negative infinity and beta to positive infinity.
We also want to make sure we pass alpha and beta into our recursive calls. We’re passing these two values down the tree.
Next, we want to check to see if we should reset alpha and beta. In the maximizing case, we want to reset alpha if the newly found best_value is greater than alpha. In the minimizing case, we want to reset beta if best_value is less than beta.
Finally, after resetting alpha and beta, we want to check to see if we can prune. If alpha is greater than or equal to beta, we can break and stop looking through the other potential moves.
Instructions
Add two new parameters named alpha and beta to your minimax() function as the final two parameters. Inside your minimax() function, when you the recursive call, add alpha and beta as the final two parameters.
After resetting the value of best_value if is_maximizing is True, we want to check to see if we should reset alpha. Set alpha equal to the maximum of alpha and best_value. You can do this quickly by using the max() function. For example, the following line of code would set a equal to the maximum of b and c.
Change both returns statements to include alpha as the last item in the list. For example, the base case return statement should be [evaluate_board(input_board), "", alpha].
Note that this third value in the return statement is not necessary for the algorithm — we need the value of alpha so we can check to see if you did this step correctly!
If we reset the value of best_value and is_maximizing is False, we want to set beta to be the minimum of beta and best_value. You can use the min() function this time.
In both return statements, add beta as the last item in the list. This is once again unnecessary for the algorithm, but we need it to check your code!
At the very end of the for loop, check to see if alpha is greater than or equal to beta. If that is true, break which will cause your program to stop looking through the remaining possible moves of the current game state.
We’re going to call minimax() on board, but before we do let’s see what board looks like. Call print_board using board as a parameter.
Call minimax() on board as the maximizing player and print the result. Set depth equal to 6. alpha should be -float("Inf") and beta should be float("Inf").