# Min-Max Algorithm

## 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.

## 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.

## 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. 