Create Your AI Player
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.
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: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.
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.
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
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.
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.
Become a Member to join the conversation.