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.
Read: Types of AI algorithms
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.
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 PG Diploma 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.