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_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 —
Let’s edit our minimax function to keep track of which move leads to the best possible value!
Instead of returning just the value, we’re going to return a list that looks like
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
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)
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
Call your function on
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.