Make Your Minimax Player Unbeatable

00:00 Make an Undefeatable Minimax Computer Player. The minimax algorithm calculates the score associated with a particular move. To find the best move in a given game state, you can sort all possible moves by score and take the one with the highest value.

00:17 By doing that, you’ll use AI to create an unbeatable tic-tac-toe player with Python. Go ahead and define the function seen on-screen in the tic-tac-toe library’s minimax module.

00:45 The find_best_move() function takes a game state and returns either the best move for the current player or None to indicate that no more moves are possible.

00:57 Note the use of a partial function to freeze the value of the maximizer argument, which doesn’t change across minimax() invocations.

01:06 This lets you use the bound_minimax() function, which expects exactly one argument, as the ordering key Python’s functools.partial() is a factory that produces a new function with fewer parameters by pre-populating one or more of the original function’s arguments with concrete values.

01:25 Unlike manually defining such a wrapper function when writing code, the factory can do this dynamically at runtime and offers a much more concise syntax.

01:36 Next, add a new computer player in the tic-tac-toe library’s players module. This player will use the find_best_move() helper function that you just created.

02:12 This computer player will always try to find the best move. However, to make the game less predictable and reduce the amount of computation, you can let it pick the first move randomly before running the expensive minimax algorithm.

02:25 You’ve already implemented the logic for choosing a random move in RandomComputerPlayer. So now it would help to extract that common logic into a reusable component.

02:36 Go ahead and modify the code of both the random and minimax computer players.

03:11 You call the .make_random_move() method on the game state in both classes. You need to define this new method to choose one of the possible moves using Python’s random module.

03:23 Head over to the models module and define the .get_random_move() method in the GameState class as seen. First, import the random module and then create the method within the class body.

04:03 The final step is to use the new computer player in your front end. Open the args module in the console front end project.

04:22 First, the imports are tidied up and MinimaxComputerPlayer is imported.

04:33 You add the new player type to the mappings of names, and finally use the MinimaxComputerPlayer as the default opponent of the human player.

04:48 You now have three kinds of players to choose from. You can take your console front end for the ultimate test drive by selecting different players to try their chances against each other.

04:59 For example, you can pick two minimax computer players.

05:12 In this case, you should expect the game to always end in a tie since both players use the optimal strategy. One thing you may notice when requesting at least one MinimaxComputerPlayer is poor performance, especially at the beginning of the game.

05:27 That’s because building the entire game tree, even for a game as relatively basic as tic-tac-toe, is costly. So in the future, you may want to check out a few performance optimization possibilities on your own, but next you’ll take a look back at what you’ve learned in this course.