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
.
a = max(b, 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")
.