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

**1.**

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.

**2.**

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!

**3.**

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!

**4.**

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.

**5.**

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.

**6.**

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")`

.