The min max algorithm in AI, popularly known as the minimax, is a backtracking algorithm used in decision making, game theory and artificial intelligence (AI). It is used to find the optimal move for a player, assuming that the opponent is also playing optimally. Popular two-player computer or online games like Chess, Tic-Tac-Toe, Checkers, Go, etc. use this algorithm.
A backtracking algorithm is used to find a solution to computational problems in such a way that a candidate is incrementally built towards a solution, one step at a time. And the candidate that fails to complete a solution is immediately abandoned.
How does it work?
In the min max algorithm in AI, there are two players, Maximiser and Minimiser. Both these players play the game as one tries to get the highest score possible or the maximum benefit while the opponent tries to get the lowest score or the minimum benefit.
Every game board has an evaluation score assigned to it, so the Maximiser will select the maximised value, and the Minimiser will select the minimised value with counter moves. If the Maximiser has the upper hand, then the board score will be a positive value, and if the Minimiser has the upper hand, then the board score will be a negative value.
This is based on the zero-sum game concept where the total utility score gets divided between the two players. Thus, an increase in one player’s score leads to a decrease in the opponent player’s score, making the total score always zero. So, for one player to win, the other has to lose.
Join the Machine Learning Certification & AI courses online from the World’s top Universities. Earn Masters, Executive PGP, or ACP to fast-track your career.
Breaking down the min max algorithm in AI
The complete game tree is explored with a depth-first search algorithm in the min max algorithm in AI. It proceeds entirely down to the terminal node of the tree and then backtracks through the tree.
FYI: Free nlp course!
The goal is to find the best possible move for a player. This can be done by choosing the node with the best evaluation score. The best choice will be made after evaluating all the potential moves of the opponent. The algorithm looks ahead at all the possible values till the end and makes a decision for the player.
The game tree above is a nested data structure that is used to evaluate the moves. Here the root node is Level 0, which branches out into Level 1 or parent nodes, which further branch out into Level 2 or child nodes. The branching out can continue to many levels, having the potential of infinite levels. Level 0 is like the current state of the board, while Level 1 is all the possible states of boards depending on the next move.
Thus, if Player 2 has made a move, we can assume that the root node is the current state of the board, waiting for Player 1’s move. Level 1 nodes contain all the possible moves for Player 1, and the Level 2 nodes contain all the possible moves for Player 2 based on each possible move of Player 1.
Consider an example where there are four final states and the path to reach these are from the root to the four leaves of a tree. The values of the four leaves are 3, 6 on the left and 4, 7 on the right. It is the Maximiser/Player 1’s turn to make a move. To run through the algorithm, assumptions for each move have to be made.
If the Player 1 chooses to go left, the Minimiser/Player 2 has to choose the least between 3 and 6, and so they would choose 3. Whereas if the Player 1 chooses right, the Player 2 will choose 4, which is the minimum of the two values, 4 and 7. So, Level 1 now has the values 3 and 4.
Since it is the Player 1/Maximiser’s turn, they have to choose the maximum of Level 1 nodes. Thus, they will choose 3. Then the optimal choice is to go left.
The steps for the min max algorithm in AI can be stated as follows:
- Create the entire game tree.
- Evaluate the scores for the leaf nodes based on the evaluation function.
- Backtrack from the leaf to the root nodes:
For Maximizer, choose the node with the maximum score.
For Minimizer, choose the node with the minimum score.
- At the root node, choose the node with the maximum value and select the respective move.
Also Read: Machine Learning Project Ideas
Properties of min max algorithm in AI
- The algorithm is complete, meaning in a finite search tree, a solution will be certainly found.
- It is optimal if both the players are playing optimally.
- Due to Depth-First Search (DFS) for the game tree, the time complexity of the algorithm is O(bm), where b is the branching factor and m is the maximum depth of the tree.
- Like DFS, the space complexity of this algorithm is O(bm).
- A thorough assessment of the search space is performed.
- Decision making in AI is easily possible.
- New and smart machines are developed with this algorithm.
- Because of the huge branching factor, the process of reaching the goal is slower.
- Evaluation and search of all possible nodes and branches degrades the performance and efficiency of the engine.
- Both the players have too many choices to decide from.
- If there is a restriction of time and space, it is not possible to explore the entire tree.
But with Alpha-Beta Pruning, the algorithm can be improved.
This article explains all the aspects of the min-max algorithm in AI. First, an introduction of the theory is provided with examples of where it is used, after which there is a description of how the algorithm works in a game.
The algorithm is broken down to explain how a decision to make an optimal move is taken based on moves and counter moves of the players. The properties of the algorithm are then listed. Lastly, the advantages and disadvantages of the algorithm are provided.
If you’re interested to learn more about machine learning, check out IIIT-B & upGrad’s Executive PG Programme in Machine Learning & AI which is designed for working professionals and offers 450+ hours of rigorous training, 30+ case studies & assignments, IIIT-B Alumni status, 5+ practical hands-on capstone projects & job assistance with top firms.
How does the min-max algorithm work?
There are two participants in the AI min max algorithm: Maximiser and Minimizer. Both of these players compete in the game, with one attempting to achieve the highest score or maximum benefit and the other attempting to achieve the lowest score or minimum benefit. Because each game board includes an assessment score, the Maximiser will choose the highest value, while the Minimizer will choose the lowest value with counter movements. When the Maximiser does have the upper hand, the board score will be positive, but when the Minimizer seems to have the upper hand, the board score will be negative.
What are the properties of min max algorithm in AI?
The algorithm is complete, which means that a solution will almost certainly be discovered in a finite search tree. It is ideal if both players are performing at their best. The temporal complexity of the algorithm for the game tree is O(bm), in which b is the branching factor & m is the maximum depth of the tree, due to Depth-First Search (DFS). This algorithm, like DFS, has a space complexity of O(bm).
What are the limitations of minimax algorithm?
The process of obtaining the goal is slower due to the large branching factor. The engine's performance and efficiency suffer as a result of evaluating and searching all conceivable nodes and branches. Both players have an excessive number of options from which to choose. It is impossible to investigate the complete tree if there is a time and space constraint. The algorithm, however, can be enhanced by Alpha-Beta Pruning.