Mini-Max Algorithm in Artificial Intelligence (AI)

In this page we will learn about Mini-Max Algorithm in Artificial Intelligence, Mini-Max Algorithm, Pseudo code for MinMax Algorithm, Working of Min-Max Algorithm, Properties of Mini-Max algorithm, Limitation of the minimax Algorithm.

---

Mini-Max Algorithm in Artificial Intelligence

• In decision-making and game theory, the mini-max algorithm is a recursive or backtracking method. It suggests the best move for the player, provided that the opponent is likewise playing well.
• In AI, the Min-Max algorithm is mostly employed for game play. Chess, checkers, tic-tac-toe, go, and other two-player games are examples. This Algorithm calculates the current state's minimax choice.
• The game is played by two players, one named MAX and the other named MIN, in this algorithm.
• Both players FIGHT it, since the opponent player receives the smallest benefit while they receive the greatest profit.
• Both players in the game are adversaries, with MAX selecting the maximum value and MIN selecting the minimum value.
• For the exploration of the entire game tree, the minimax method uses a depth-first search strategy.
• For the exploration of the entire game tree, the minimax method uses a depth-first search strategy.
• The minimax algorithm descends all the way to the tree's terminal node, then recursively backtracks the tree.

Pseudo-code for MinMax Algorithm:

 
 function minimax(node, depth, maximizingPlayer) is  
   if depth == 0 or node is a terminal node then  
   return static evaluation of node  
    
   if MaximizingPlayer then      // for Maximizer Player  
   maxEva =- infinity            
    for each child of node do  
    eva= minimax(child, depth - 1, false)  
   maxEva= max(maxEva,eva)        //gives Maximum of the values  
   return maxEva  
    
   else                         // for Minimizer player  
    minEva =+ infinity   
    for each child of node do  
    eva= minimax(child, depth - 1, true)  
    minEva = min(minEva, eva)         //gives minimum of the values  
    return minEva  

Initial call:

minimax(node, 3, true)

Working of Min-Max Algorithm:

• A simple example can be used to explain how the minimax algorithm works. We've included an example of a game-tree below, which represents a two-player game.
• There are two players in this scenario, one named Maximizer and the other named Minimizer.
• Maximizer will strive for the highest possible score, while Minimizer will strive for the lowest possible score.
• Because this algorithm uses DFS, we must go all the way through the leaves to reach the terminal nodes in this game-tree.
• The terminal values are given at the terminal node, so we'll compare them and retrace the tree till we reach the original state. The essential phases in solving the two-player game tree are as follows:

Step 1: The method constructs the whole game-tree and applies the utility function to obtain utility values for the terminal states in the first step. Let's assume A is the tree's initial state in the diagram below. Assume that the maximizer takes the first turn with a worst-case initial value of -infinity, and the minimizer takes the second turn with a worst-case initial value of +infinity.

Step 2: Next, we'll locate the Maximizer's utilities value, which is -, and compare each value in the terminal state to the Maximizer's initial value to determine the upper nodes' values. It will select the best option from all of them.

• For node D   max(-1,- -∞) => max(-1,4)= 4
• For Node E    max(2, -∞) => max(2, 6)= 6
• For Node F    max(-3, -∞) => max(-3,-5) = -3
• For node G    max(0, -∞) = max(0, 7) = 7

Step 3: Now it's the minimizer's time, thus it'll compare all nodes' values with + and determine the 3rd layer node values.

• For node B = min(4,6) = 4
• For node C = min (-3, 7) = -3

In the next step, algorithm traverse the next successor of Node B which is node E, and the values of α = -∞, and β = 3 will also be passed.

Step 4: Now it's Maximizer's turn, and it'll choose the maximum value of all nodes and locate the root node's maximum value. There are only four layers in this game tree, so we can go to the root node right away, but there will be more layers in real games.
For node A max(4, -3)= 4

That was the complete workflow of the minimax two player game.

---

Properties of Mini-Max algorithm:

• Complete –The Min-Max algorithm is finished. In the finite search tree, it will undoubtedly locate a solution (if one exists).
• Optimal- If both opponents are playing optimally, the Min-Max algorithm is optimal.
• Time complexity- Because it executes DFS for the game-tree, the time complexity of the Min-Max algorithm is O(b^m), where b is the game-branching tree's factor and m is the tree's maximum depth.
• Space Complexity- Mini-max method has a space complexity that is similar to DFS, which is O(bm).

Limitation of the minimax Algorithm:

The biggest disadvantage of the minimax algorithm is that it becomes extremely slow while playing complex games like chess or go. This style of game contains a lot of branching, and the player has a lot of options to choose from. The minimax algorithm's drawback can be alleviated by using alpha-beta pruning , which we will explore in the next section. the depth to which the tree can grow.