MinMax Algorithm

Firdausia Fatima
Last Updated: May 13, 2022

Introduction

Often, programmers adopt a "recursive leap of faith strategy," which means one can assume the answer to subproblems while solving a complex one. At first, this seems doubtful to the point of being suspect.

But as sir, Samuel Taylor said, “The willing suspension of disbelief for the moment, which constitutes poetic faith”, is needed during recursion. You’ve to trust your solution will give answers to subproblems. This view is often called the holistic view. 

The MinMax Algorithm, which we'll talk about today, is a backtracking strategy used in game theory to discover the player's best move. This algorithm is used in two players games like tic-tac-toe, chess, etc.

Basic Idea

In the MinMax algorithm, we have two players Maximizer and Minimizer. The job of Maximizer is to maximize the outcome, while Minimizer has to minimize the outcome. MinMax algorithm allows one to look ahead in the possible future states before deciding what moves one should make in the current state.

The solution can typically be visualized as a tree. Each node represents a state in the game and has a statistical value associated with it, which tells how good the state is for one side without making any other move.

Example: In a tic-tac-toe game, statistical value can be the number of 'X' or '0' to place to make a pair of three.

At each state(Node), one of the two players Maximizer or Minimizer needs to make a move to maximize or minimize the outcome. 

Example

For the sake of simplicity, consider a game with four end states and two possible moves at each level. Maximizer has to make a move first, so he's on the tree's root, and Minimizer gets the next level. Each final state has a statistical value. And when its minimizers turn, it will choose the smaller value while the Maximizer will choose the greater value. And they both play optimally.

 

Let’s see how it backtracks to find the most optimal move.

At the root of the tree, its Maximizers turn.

  1. Let's say it chooses LEFT.

             * Now it's the Minimizer's turn.

             1.Traversing the children, Minimizer chose the minimum value. So it chooses -4. 

             * Now it backtracks.

 2.   It chooses RIGHT. 

             * Now it’s the Minimizer’s turn. we are

             1.Traversing the children minimizer chooses 3

             * Now it backtracks.

Comparing both values -4 and 3, Maximizer chose 3 as the maximum value.

Now that we've understood the concept, let's try to code it.

Program

#include <iostream>
using namespace std;
// Function of minmax() algorithm will return the maximum value the Maximizer can get when both players play optimally.
int minmax(bool maximizer, int finalStates[], int l, int r)
{
   // If we are on the leaf of the tree. Return the statistical value.
   if (l == r)
   {
       return finalStates[l];
   }
   // Find the middle of the states.
   int mid = (l + r) / 2;
   // If it's Maximizers turn, we have to find the maximum value.
   if (maximizer)
   {
       return max(minmax(false, finalStates, l, mid), minmax(false, finalStates, mid + 1, r));
   }
   // If it's Minimizers turn, Minimum value is returned.
   return min(minmax(true, finalStates, l, mid), minmax(true, finalStates, mid + 1, r));
}
int main()
{
   int n;
   cout << "Enter the number of final states N, where (N = 2 ^ x): ";
   cin >> n;
   cout << "Enter the final states: \n";
   int finalStates[n];
   for (int i = 0; i < n; i++)
   {
       cin >> finalStates[i];
   }
   int ans = minmax(true, finalStates, 0, n - 1);
   cout << "Best the Maximizer can get: " << ans << endl;
   return 0;
}

Input

Enter the number of final states N, where( N=2^x ): 8
Enter the final states :
-2 3 5 12 9 8 -7 -3

Output

Best the Maximizer can get : 3

 

General Idea

The above example discussed is a special case of the Minmax Algorithm. However, in general,

  1. We can have hundreds of states of the game.
  2. Players have multiple choices of moves.
  3. The statistical value of a final state is calculated by a special function called Evaluation Function, which is unique for each game.

MinMax algorithm can be optimized with alpha-beta pruning.

Let’s try to express the general idea in code. We are not going to write the evaluation function.

Program

#include <bits/stdc++.h>
using namespace std;
/* Function of minmax algorithm will tell the best move to choose from.
DEPTH = the depth you need to search into.
STATEID = tells what state are we on.
TREE = a graph where all states are mapped to all possible states.
MAXIMIZER = whether its maximizer's turn.
*/
int minmax(int depth, int stateUd, unordered_map<int,vector<int>> tree, bool maximizer)
{
   // Return the statistical value of this state.
   if (depth == 0)
   {
       // Function which calculates statistical value. This is EVALUATION FUNCTION and is unique for all games.
       return calculateStatisticalValue(stateId);
   }
   // If it's Maximizers turn, we have to find the maximum value.
   if (Maximizer)
   {
       int mx = INT_MIN;
       // We loop through all the next state and find the maximum value.
       for (auto nextStateId : tree[stateId])
       {
           mx = max(mx, minmax(depth - 1, nextStateId, tree, false));
       }
       return mx;
   }
   // If it's Minimizers turn, the Minimum value is returned.
   int mn = INT_MAX;
   // We loop through all the next state and find the minimum value.
   for (auto nextStateId : tree[stateId])
   {
       mn = min(mn, minmax(depth - 1, nextStateId, tree, true));
   }
   return mn;
}
int main()
{
   // TAKE INPUT
   minmax(depth, startState, tree, true);
   return 0;
}

Key Takeaways

I hope you had fun reading the article. Refer to this to find how the MinMax algorithm can be optimized using alpha-beta pruning. Head over to CodeStudio to read other such exciting blogs. 

Recently Coding Ninjas has released a specially designed test series for acing Interviews- CodeStudio Test Series.

Was this article helpful ?
0 upvotes