Key Concepts
Review core concepts you need to learn to master this subject
Minimax algorithm state value
Minimax algorithm problem specification
Minimax algorithm assumption
Minimax algorithm game representation
Minimax algorithm state evaluation
Minimax algorithm size restriction
Minimax algorithm with alpha-beta pruning
Alpha-beta pruning variables
Minimax algorithm state value
Minimax algorithm state value
When writing the minimax algorithm, each game involves two players and game states can be evaluated as a value. One of the players is called the maximizer, because he or she wants to maximize the value of the game and the remaining player is called the minimizer.
Minimax algorithm problem specification
Minimax algorithm problem specification
Given a game state, the minimax algorithm finds the decision that maximizes the minimum gain. In other words, if you assume your opponent will make decisions that minimize your gain, the algorithm finds the move that will maximize it based on the options your opponent gives you. It is assumed that the game is being played by turns and that the opponent is playing optimally, this is: at each turn a player must make a move, and this move is the best the player can make in that situation.
Minimax algorithm assumption
Minimax algorithm assumption
When running the minimax algorithm, it is assumed that your opponent is playing optimally. This assumption is a worst case scenario, given that if your opponent is not playing optimally the problem is reduced to a simpler one.
Minimax algorithm game representation
Minimax algorithm game representation
When writing the minimax algorithm, a game is modeled as a tree. Different elements of the game (as the current state and all possible moves) are represented as different parts of the tree. This visual representation of the game is a great aid in order to implement the minimax algorithm.
Minimax algorithm state evaluation
Minimax algorithm state evaluation
When running the minimax algorithm, a game state can be evaluated even if it is not a leaf. This game state evaluation is particularly important in some games such as chess, where we have a long sequence of states before reaching a leaf.
Minimax algorithm size restriction
Minimax algorithm size restriction
The size of the game tree is a very important restriction in a minimax algorithm, given that it is not possible to visit all states in a reasonable time. If the maximum depth you can consider is reduced, the optimality of your solution is affected. When the size of the game tree is very large, several heuristics can be applied to find a good solution of the minimax algorithm.
Minimax algorithm with alpha-beta pruning
Minimax algorithm with alpha-beta pruning
When implementing alpha-beta pruning in the minimax algorithm, its execution time is drastically decreased. For a given unit of time, a minimax algorithm with alpha-beta pruning can go down twice as far as a minimax algorithm without this pruning technique.
Alpha-beta pruning variables
Alpha-beta pruning variables
When using alpha-beta pruning in a minimax algorithm, it is needed to track the value of two different variables (alpha and beta) in order to decide when to prune a part of the tree. At the beginning of the game, alpha is equal to negative infinity and beta is equal to positive infinity. These values are updated as the game progresses.
- 1Have you ever played a game against someone and felt like they were always two steps ahead? No matter what clever move you tried, they had somehow envisioned it and had the perfect counterattack. T…
- 2For the rest of this exercise, we’re going to be writing the minimax algorithm to be used on a game of Tic-Tac-Toe. We’ve imported a Tic-Tac-Toe game engine in the file tic_tac_toe.py. Before start…
- 3An essential step in the minimax function is evaluating the strength of a leaf. If the game gets to a certain leaf, we want to know if that was a better outcome for player “X” or for player “O”. …
- 4We now know that we can evaluate the leaves of a game tree, but how does that help us? How are we going to use those values to find the best possible move for a game state that isn’t a leaf? Let’s…
- 5One of the central ideas behind the minimax algorithm is the idea of exploring future hypothetical board states. Essentially, we’re saying if we were to make this move, what would happen. As a re…
- 6We’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 mov…
- 7Nice work! We’re halfway through writing our minimax() function — it’s time to make the recursive call. We have our variable called best_value . We’ve made a hypothetical board where we’ve m…
- 8Right 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 &m…
- 9Amazing! Our minimax() function is now returning a list of [value, move]. move gives you the number you should pick to play an optimal game of Tic-Tac-Toe for any given game state. This line of co…
- 10Nice work! You implemented the minimax algorithm to create an unbeatable Tic Tac Toe AI! Here are some major takeaways from this lesson. * A game can be represented as a tree. The current state of …
- 1In our first lesson on the minimax algorithm, we wrote a program that could play the perfect game of Tic-Tac-Toe. Our AI looked at all possible future moves and chose the one that would be most ben…
- 2The first strategy we’ll use to handle these enormous trees is stopping the recursion early. There’s no need to go all the way to the leaves! We’ll just look a few moves ahead. Being able to stop …
- 3By adding the depth parameter to our function, we’ve prevented it from spending days trying to reach the end of the tree. But we still have a problem: our evaluation function doesn’t know what to d…
- 4By writing an evaluation function that works on non-leaf game states, we can stop the recursion early. But in a perfect world, we’d still want to reach the leaves of the tree. In order to traverse …
- 5Alpha-beta pruning is accomplished by keeping track of two variables for each node — alpha and beta. alpha keeps track of the minimum score the maximizing player can possibly get. It starts a…
- 6Great work! We’ve now edited our minimax() function to work with games that are more complicated than Tic Tac Toe. The core of the algorithm is identical, but we’ve added two major improvements: * …
What you'll create
Portfolio projects that showcase your new skills
How you'll master it
Stress-test your knowledge with quizzes that help commit syntax to memory