Blog # 43 : Minimax (Minmax) Search

Minimax (sometimes minmax) is a decision rule used in decision theory, game theory, statistics and philosophy for minimizing the possible loss for a worst case (maximum loss) scenario. Alternatively, it can be thought of as maximizing the minimum gain (maximin). Originally formulated for two-player zero-sum game theory, covering both the cases where players take alternate moves and those where they make simultaneous moves, it has also been extended to more complex games and to general decision making in the presence of uncertainty.

For more please refer Minimax

Code:

#include<iostream>
#include<cstdlib>
#include<vector>
using namespace std;

vector <int> vec;

int large(int a,int b)
{
 if(a>b)
  return a;
 else
  return b;
}

int small(int a,int b)
{
 if(a>b)
  return b;
 else 
  return a;
}

void max_min(int p,int q,int *max,int *min)
{
 if(p==q)
 {
  *max=vec[p];
  *min=vec[q];
 }
 
 else if(p==(q-1))
 {
  if(vec[p]>vec[q])
  {
   *max=vec[p];
   *min=vec[q];
  }
  else
  {
   *max=vec[q];
   *min=vec[p];
  }
 }
 
 else
 {
  int m=(p+q)/2;
  int max1,max2,min1,min2;
  
  max_min(p,m,&max1,&min1);
  max_min(m+1,q,&max2,&min2);
  *max=large(max1,max2);
  *min=small(min1,min2);
 }
}

int main()
{
 int a,n=0;
 int min=0,max=0;
 
 cout<<"enter the elements (enter -1 to quit) :  ";
 while(1)
 {
  cin>>a;
  if(a==-1)
   break;
  else
  {
   vec.push_back(a);
   n++;
  }
 }
 max_min(0,n-1,&max,&min);
 
 cout<<"MAX = "<<max<<"\t"<<"MIN = "<<min<<endl;
 
 return 0;
}