Introduction to Minimax Algorithm
Minimax is a type of backtracking algorithm. The Minimax algorithm finds an optimal move to make decisions in game theory. Minimax algorithm takes into consideration that the opponent is also playing optimally, which makes it useful for two-player games such as checker, chess, Tic-tac-toe, go and many others.
In general, when two human beings play, they must make the decision at each move with all the possible moves, and then chose anyone which he thinks is the best move. The same is with the Minimax algorithm too, but here the decision, to make a move is taken using a backtracking approach. To do this it selects two players one is the min and the other is max, the goal of min player is to pick the minimum value and on the other hand, the goal of max is to pick the maximum value.
What is Minimax Algorithm?
Minimax algorithm is a decision-making algorithm, used in game theory. It considers two players min and max, min always picks up a minimum value score from game and max always picks up maximum value score. The value for each game move is decided based on some heuristics.
Minimax algorithm uses some terminology which is stated below:
- Game Tree: Tree for the game moves, it shows all the possible moves available to the player at a particular state. The player makes an optimum decision and makes a move.
To quantify game moves we can use the following components:
- Initial State: The state at which the game starts.
- Successor Function: The function is used to define all the available moves for the player at the current state.
- Terminal State: This is the last state of the game which decides the winner of the game and the game gets over.
- Utility Function: It is the most important function in this algorithm. It is that a heuristic approach is used to assign values for each outcome from the game. The values are assigned based on the rules of the game. The values assigned come from terminal leaves if it’s a winning move the high value will be assigned to that move and if it’s a losing move, the low value will be assigned to that move.
Working of Minimax Algorithm
As we know what Minimax algorithm time is now to understand how it works. We will take a simple example and then will solve it using the Minimax algorithm:
Step1: Let us take a 4-level tree generated by an algorithm, for our example (as shown below). Level zero is Root node or initial state and is represented as RN, other respective levels with L1, L2, and L3. L1N1 represents Level 1 and Node 1, In the same way, all others are represented also.
4.5 (3,155 ratings)
View Course
Level 3 nodes are called terminal nodes. The utility function generates values for terminal nodes. The values for terminal nodes let us consider are the following:
- L3N1 = -2
- L3N2 = 3
- L3N3 = 1
- L3N4 = 5
- L3N5 = -4
- L3N6 = -6
- L3N7 = 0
- L3N8 = 6
Generally, the goal is to score more points so the Initial state is kept as maximizer, further it depends on goal but generally it is to maximize. So we take Initial as a max player.
Once we are done with a tree node and the goal of the move, the algorithm makes the decision.
Step 2: Initially for maximizer, the worst-case scenario is having -∞, or if it is minimizer than it will be +∞. The next task is to choose the best possible move by comparing options. At the terminal node for maximizer, the initial value is -∞.
To get the maximum from level 3 or terminal level to level 2 maximizer will compare the value of each node with -∞.
- For L2N1 : max(-2, -∞) => max(-2, 4) = 4
- For L2N2 : max( 1, -∞) => max( 1, 5) = 5
- For L2N3 : max(-4, -∞) => max(-4,-6) =-4
- For L2N4 : max(0, -∞) => max( 0, 6) = 4
Step 3: Now its minimizers turn, so a comparison of all nodes is done with +∞.
- For L1N1 : min( 4, ∞) => min( 4, 5) = 4
- For L1N2 : min(-4, ∞) => min(-4, 4) =-4
Step 4: Now its maximizers turn again, so out of available nodes it will choose the maximum value.
- For RN : max( 4,-∞) => max( 4, -4) = 4
So, at last, the value at the root node comes out to be 4. The decision has been taken and the next move will be played and again the same procedure will be taken into account.
Limitation of Minimax Algorithm
- Minimax algorithm compares with each data in the terminal nodes, for example in L2N3 the maximum value is -4 between -4, -∞ and -6. But after assigning -4, it will cross-check with -6 and answer will be -4. which makes it slow. Our example just has two nodes but in the case of Tic-tac-toe, we have 8,7,6… moves respectively at each node. And checking at each node with each value is time-consuming.
- The complexity of increases for some high-level games such as chess and go, which has a number of pieces to move and a number of places to move it to. Which makes it very complex. And somehow if we create trees, it results in the very large branched tree.
This can be improved using Alpha-Beta Pruning. In short Alpha-Beta pruning is a kind of search algorithm whose goal is to decrease the number of nodes that needs to be evaluated, hence making the minimax algorithm work better and execute faster.
Conclusion
Minimax is a decision-making algorithm that is used in game theory. This algorithm is for two-player games and it considers, both the players are playing optimally. The algorithm constructs trees and follows a backward approach. The approach is been discussed in the above article with an example, and we have discussed limitations associated with it and how can we improve the algorithm.
Recommended Articles
This is a guide to the Minimax Algorithm. Here we discuss what is Minimax Algorithm, along with the working and, limitations of it. You can also go through our other related articles to learn more –
