Learn
Implement Alpha-Beta Pruning

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