We’re now ready to dive in and write our minimax() function. The result of this function will be the “value” of the best possible move. In other words, if the function returns a 1, that means a move exists that guarantees that "X" will win. If the function returns a -1, that means that there’s nothing that "X" can do to prevent "O" from winning. If the function returns a 0, then the best "X" can do is force a tie (assuming "O" doesn’t make a mistake).
Our minimax() function has two parameters. The first is the game state that we’re interested in finding the best move. When the minimax() function first gets called, this parameter is the current state of the game. We’re asking “what is the best move for the current player right now?”
The second parameter is a boolean named is_maximizing representing whose turn it is. If is_maximizing is True, then we know we’re working with the maximizing player. This means when we’re picking the “best” move from the list of moves, we’ll pick the move with the highest value. If is_maximizing is False, then we’re the minimizing player and want to pick the minimum value.
Let’s start writing our minimax() function.
Instructions
We’ve started the minimax() function for you and included the base case we wrote a few exercises ago.
We now need to define what should happen if the node isn’t a leaf.
We’ll want to set up some variables that are different depending on whether is_maximizing is True or False.
Below the base case, write an if statement to check if is_maximizing is True.
Inside the if statement, create a variable named best_value. Since we’re working with the maximizing player right now, this is the variable that will keep track of the highest possible value from all of the potential moves.
Right now, we haven’t looked at any moves, so we should start best_value at something lower than the lowest possible value — -float("Inf").
Write an else statement. Inside this else statement we’ll be setting up variables for the minimizing player. In this case, best_value should start at float("Inf").
Return best_value after the else statement.
We now want to loop through all of the possible moves of input_board before the return statement. We’re looking to find the best possible move.
Remember, you can get all of the possible moves by calling available_moves() using input_board as a parameter.
After the else statement, but before you return best_value, loop through all of the possible moves and print each move.
Let’s call our function to see these print statements. Outside of your function definition, call minimax() using the parameters x_winning (the board we’re using) and True (we’re calling it as the maximizing player).
Delete the print statements for move. Rather than just printing the move in this for loop, let’s create a copy of the game board and make the move!
Inside the for loop, create a deepcopy of input_board named new_board.
Apply the move to new_board by calling the select_space() function. select_space() takes three parameters.
- The board you want to use (
new_board) - The space you’re selecting (the
movefrom the for loop) - The symbol you’re filling the space in with. This is different depending on whether we’re the maximizing or minimizing player. In your
ifandelsestatements, create a variable namedsymbol.symbolshould be"X"if we’re the maximizing player and"O"if we’re the minimizing player. Usesymbolas the third parameter ofselect_space().
To help us check if you accurately made the move, return new_board outside the for loop (instead of returning best_move). We’ll fix that return statement soon!