Learn
Minimax
Which Move?

Right now our `minimax()` function is returning the value of the best possible move. So if our final answer is a `1`, we know that `"X"` should be able to win the game. But that doesn’t really help us — we know that `"X"` should win, but we aren’t keeping track of what move will cause that!

To do this, we need to make two changes to our algorithm. We first need to set up a variable to keep track of the best move (let’s call it `best_move`). Whenever the algorithm finds a new `best_value`, `best_move` variable should be updated to be whatever move resulted in that value.

Second, we want the algorithm to return `best_move` at the very end. But in order for the recursion to work, the algorithm is dependent on returning `best_value`. To fix this, we’ll now return a list of two numbers — `[best_value, best_move]`.

Let’s edit our minimax function to keep track of which move leads to the best possible value!

### Instructions

1.

Instead of returning just the value, we’re going to return a list that looks like `[best_value, best_move]`.

We haven’t kept track of the best move yet, so for now, let’s change both of our return statements to be `[best_value, ""]`. This includes the base case! The base case should return `[evaluate_board(input_board), ""]`

We also need to make sure when we’re setting `hypothetical_value`, we’re setting it equal to the value — not the entire list. The recursive call should now look like this.

``minimax(new_board, not is_maximizing)[0]``
2.

Let’s now keep track of which move was best.

Right after the base case, create a variable named `best_move`. Set it equal to the empty string (`""`)

For both the maximizing case and the minimizing case, if we’ve found a new `best_value`, we should also update `best_move`. Inside those two if statements, set `best_move` equal to your variable from your for loop (ours is named `move`). We’re now remembering which move goes with the best possible value.

Change your last return statement. Instead of returning `[best_value, ""]`, return `[best_value, best_move]`.

3.

Call your function on `x_winning`, and `o_winning` as the maximizing player. Print the results. What does the return value tell you now?

You can also try it on `new_game`. This might take a few seconds.