Home » Technical Interview Questions » Algorithm Interview Questions » MiniMax Algorithm

# MiniMax Algorithm

Everyone might be wondering. Argh, another new MINIMAX ALGORITHM.

Why do we need it? Let’s know to play a game of chess or tic-tac-toe we have often wondered if there was an algorithm to win the game.

## Explanation

A lot of times we might have wondered if

• It was possible to decipher the moves of the opponent
• It was possible to play optimally

MiniMax Algorithm brings in just the thing for us!

In a search tree for a two-player game, there can be two kinds of nodes

• MAX Nodes
• These are the nodes representing the move you can make
• Represented as upward-pointing triangles
• The goal of these nodes: Maximizing the value of subtree under the node
• Value of max node: Value of child with the maximum value
• MIN Nodes
• These are the nodes representing the moves your opponent can make
• Represented as downward-pointing triangles
• The Goal of these nodes: Minimizing the value of subtree under the node
• Value of min node: Value of child with the minimum value

A lot of this might not be making sense to you.

Let’s understand that by an example

Assume we have 8 initial states with the values as shown in the figure below

• Initially, we take the max of each one of two nodes
• Ex-From 3 and 15 we find the max
• We put this max value in the max node(Upward pointing triangles)
• Once the max cycle is completed we take the min from the max nodes
• Ex-From 15  and 10 we take 10
• We put this min value in the min node(Downward pointing triangle)
• Keep repeating this until we reach/finalize a value

Backtracking all the possible moves we make a decision choosing the values accordingly and reaching up to the conclusion

Let’s understand it better by a code snippet

## Java Code for Minimax Algorithm

```import java.io.*;
import java.util.*;
public class minimax
{
public static int decide(int cur,int index,boolean max,int weight[],int height)
{
int num=0;
//If we reach a leaf node
if(cur==height)
return weight[index];
//If the node is a max one we find the max from sub-nodes
if(max)
num=Math.max(decide(cur+1,index*2,false,weight,height),decide(cur+1,index*2+1,false,weight,height));
//If it is a min node we minimize the value under the sub-tree
else
num=Math.min(decide(cur+1,index*2,true,weight,height),decide(cur+1,index*2+1,true,weight,height));
return num;
}
public static void main(String args[])
{
int scor[] = {3, 15, 2, 10, 12, 5, 2, 23};
int n= scor.length;
int h= (int)(Math.log(n) / Math.log(2));
int a=decide(0,0,true,scor,h);
System.out.println(a);
}
}```

## C++ Code for Minimax Algorithm

```#include<iostream>
#include<cmath>
using namespace std;
int max(int a,int b)
{
if(a>b)
return a;
else
return b;
}
int min(int a,int b)
{
if(a>b)
return b;
else
return a;
}
/*int log2(int n)
{
if(n==1)
return 0;
else
return(log2(n/2));
}*/
int decide(int cur,int index,bool max_dec,int weight[],int height)
{
int num;
//If we reach a leaf node
if(cur==height)
return weight[index];
//If the node is a max one we find the max from sub-nodes
if(max_dec)
num=max(decide(cur+1,index*2,false,weight,height),decide(cur+1,index*2+1,false,weight,height));
//If it is a min node we minimize the value under the sub-tree
else
num=min(decide(cur+1,index*2,true,weight,height),decide(cur+1,index*2+1,true,weight,height));
return num;
}
int main()
{
int scor[] = {3, 15, 2, 10, 12, 5, 2, 23};
int n= 8;
int h= log2(n);
int a= decide(0,0,true,scor,h);
cout<<a;
return 0;
}```
`12`

## Complexity Analysis

Time complexity=O(h*m)

Where

h=height/depth of the tree generated

m=number of moves at each point

Thus was an introduction to the minimax algorithm and how it works!

References

Check out a few other posts

Breadth First Search (BFS) for a Graph

 Array Interview Questions Graph Interview Questions LinkedList Interview Questions String Interview Questions Tree Interview Questions