Create Your AI Player

00:00 Equip the Computer With Artificial Intelligence. This chapter of the course will involve creating another computer player, one equipped with basic artificial intelligence.

00:11 Specifically, it will use the minimax algorithm under the surface to make the most optimal move in every possible situation in any turn-based zero-sum game, such as tic-tac-toe.

00:23 Mastering the details of the minimax algorithm isn’t your focus in this course, but if you’d like to learn more about it, then check out this course which uses a more straightforward game of nim.

00:33 As an example, before implementing the algorithm, you have to invent a way of assessing the game score, which will become the deciding factor behind choosing the best move.

00:45 You’ll do that by introducing an absolute scale of numeric values indicating how well both players are doing.

00:53 For simplicity, you’ll consider static evaluation of a finished game. There are three possible outcomes of the game, which you can assign arbitrary numeric values to, as seen on-screen.

01:04 The protagonist player whose score you’ll evaluate is known as the maximizing player because they try to maximize the game’s overall score. Therefore, greater value should correspond to better outcomes as viewed from their perspective.

01:18 The minimizing player, on the other hand, is their opponent who tries to lower the score as much as possible. After all, when they win, your player loses.

01:27 While a tie can be equally good or bad for both players, once you determine the maximizing and minimizing players, the scale remains absolute, meaning you don’t need to flip the sign when evaluating your opponent’s moves.

01:42 You can express this numeric scale in Python by adding the method seen on-screen to your GameState model in the tic-tac-toe library.

02:22 Because this is a static evaluation, you can only determine the score when the game is over. Otherwise, you raise an UnknownGameScore exception, which you must add to the exceptions module in the library.

02:48 Knowing the score of a finished game isn’t that helpful when you want to make an informed decision about choosing a move up front, but it’s the first step towards finding the best possible sequence of moves leading up to winning—or tying the game, in the worst-case scenario.

03:04 Next, you’ll use the minimax algorithm to calculate the score in any game state. When you have several moves to choose from, you want to pick one that will increase your expected score.

03:16 At the same time, you want to avoid moves that could potentially shift the score in favor of your opponent. The minimax algorithm can help with that by using the min() and max() functions to minimize your opponent’s maximum gain while maximizing your minimum payoff.

03:32 If that sounds complicated, then have a look at the graphical visualization of tic-tac-toe gameplay seen on-screen. When you imagine all possible game states as a game tree, choosing the best move boils down to searching for the most optimal path in such a weighted graph.

03:49 Starting from the current node, the Minimax algorithm propagates the scores evaluated statically for the leaf nodes, which correspond to finished games, by bubbling them up in the game tree.

04:01 Either the minimum or the maximum score gets propagated at each step, depending on whose turn it is. The minimax algorithm starts by recursively exploring the tree to look ahead and find all the possible game outcomes.

04:15 Once those are found, it computes their scores and backtracks to the starting node. If it’s the maximizing player’s turn that leads to the next position, then the algorithm picks the maximum score at that level.

04:27 Otherwise, it picks the minimum score, assuming the opponent will never make mistakes. In the game on-screen, the leftmost branch results in an immediate win for the maximizing player, so the connecting edge has the highest weight.

04:42 Choosing the middle branch could also lead to a victory, but the minimax algorithm pessimistically indicates the worst-case scenario, which is a tie. Finally, the branch on the right almost certainly represents a losing move.

04:58 Create a new minimax module in the tic-tac-toe library and implement the algorithm using the Python expression seen on-screen.

05:14 The minimax() function returns the score associated with the move passed as an argument for the indicated maximizing player.

05:24 If the game has finished, then you calculate the score by performing the static evaluation of the grid.

05:35 Otherwise, you choose either the maximum or the minimum score, which you’ll find with recursion for all possible moves at the current position.

05:55 The placement of the minimax module in the project’s directory tree is somewhat subjective because it would work equally well when defined elsewhere.

06:03 However, you could argue that it logically belongs to the game’s logic layer since it only depends on the domain model.

06:11 As long as you made an editable install of the tic-tac-toe library in your virtual environment, you’ll be able to test your new function straight away in a REPL session.

07:12 The computed scores correspond to the edge weights in the game you saw previously. Finding the best move is only a matter of choosing the one with the highest resulting score.

07:22 Note that there can sometimes be multiple alternative paths to a winning outcome in the game tree.

07:29 In the next section, you’ll create another concrete computer player which will leverage the minimax algorithm, and then you’ll use it in your console front end.