Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Basic Idea
2.1.
Program
3.
General Idea
3.1.
Program
4.
Frequently Asked Questions
4.1.
What is Recursion?
4.2.
What is memorization?
5.
Conclusion
Last Updated: Mar 27, 2024
Easy

Min-Max Algorithm

Leveraging ChatGPT - GenAI as a Microsoft Data Expert
Speaker
Prerita Agarwal
Data Specialist @
23 Jul, 2024 @ 01:30 PM
DSA Problems

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.

Check out, Backtracking and Recursion

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, the 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.

Illustration Image

 

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

 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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> 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;
}

Must Read Recursion in Data Structure

Frequently Asked Questions

What is Recursion?

Recursion in simple terms can be defined as performing the same procedure again and again with possible different inputs until a certain condition known as the base case is achieved.

What is memorization?

While writing a recursive solution to a program, there may be a chance that the computations for the given sets of inputs have already been performed thus to avoid the same computations again, the answer for the given sets of input are stored in some data structure and they are provided to the recursive call instead of performing the computations again.

Conclusion

In this article, we discussed the Min-Max Algorithm and its implementation in C++. 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 Coding Ninjas Studio to read other such exciting blogs. 

Recommended Readings:


Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, Basics of C++, Basics of Java, Basics of Python, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Thanks for reading.

Live masterclass