EDUCBA

EDUCBA

MENUMENU
  • Free Tutorials
  • Free Courses
  • Certification Courses
  • 360+ Courses All in One Bundle
  • Login

Minimax Algorithm

Home » Data Science » Data Science Tutorials » Artificial Intelligence Tutorial » Minimax Algorithm

Minimax Algorithm

Introduction to Minimax Algorithm

Minimax is a type of backtracking algorithm. The Minimax algorithm finds an optimal move to make decisions in game theory. Minimax algorithm takes into consideration that the opponent is also playing optimally, which makes it useful for two-player games such as checker, chess, Tic-tac-toe, go and many others.

In general, when two human beings play, they must make the decision at each move with all the possible moves, and then chose anyone which he thinks is the best move. The same is with the Minimax algorithm too, but here the decision, to make a move is taken using a backtracking approach. To do this it selects two players one is the min, and the other is max, the goal of min player is to pick the minimum value, and on the other hand, the goal of max is to pick the maximum value.

Start Your Free Data Science Course

Hadoop, Data Science, Statistics & others

What is the Minimax Algorithm?

It is a decision-making algorithm used in game theory. It considers two players min and max, and min always picks up a minimum value score from game and max always picks up maximum value score. The value for each game move is decided based on some heuristics.

It uses some terminology which is stated below:

  • Game Tree: Tree for the game moves, it shows all the possible moves available to the player at a particular state. The player makes an optimum decision and makes a move.

To quantify game moves, we can use the following components:

  • Initial State: The state at which the game starts.
  • Successor Function: The function is used to define all the available moves for the player at the current state.
  • Terminal State: This is the last state of the game which decides the winner of the game and the game gets over.
  • Utility Function: It is the most important function in this algorithm. It is that a heuristic approach is used to assign values for each outcome from the game. The values are assigned based on the rules of the game. The values assigned come from terminal leaves if it’s a winning move the high value will be assigned to that move and if it’s a losing move, the low value will be assigned to that move.

Working of Minimax Algorithm

As we know what Minimax algorithm time is now to understand how it works. We will take a simple example and then will solve it using the Minimax algorithm:

Step1: Let us take a 4-level tree generated by an algorithm, for our example (as shown below). Level zero is Root node or initial state and is represented as RN, other respective levels with L1, L2, and L3. L1N1 represents Level 1 and Node 1; In the same way, all others are also represented.

Popular Course in this category
Artificial Intelligence Training (3 Courses, 2 Project)3 Online Courses | 2 Hands-on Project | 32+ Hours | Verifiable Certificate of Completion | Lifetime Access
4.5 (5,087 ratings)
Course Price

View Course

Related Courses
All in One Data Science Bundle (360+ Courses, 50+ projects)Machine Learning Training (17 Courses, 27+ Projects)

Minimax Algorithm - 1

Level 3 nodes are called terminal nodes. The utility function generates values for terminal nodes.  The values for terminal nodes let us consider the following:

  • L3N1 = -2
  • L3N2 = 3
  • L3N3 = 1
  • L3N4 = 5
  • L3N5 = -4
  • L3N6 = -6
  • L3N7 = 0
  • L3N8 = 6

Generally, the goal is to score more points, so the Initial state is kept as maximizer, further it depends on goal but generally, it is to maximize. So we take Initial as a max player.

Once we are done with a tree node and the goal of the move, the algorithm makes the decision.

Step 2: Initially for maximizer, the worst-case scenario is having -∞, or if it is minimizer than it will be +∞. The next task is to choose the best possible move by comparing options. At the terminal node for maximizer, the initial value is -∞.

To get the maximum from level 3 or terminal level to level 2 maximizer will compare the value of each node with -∞.

  • For L2N1 : max(-2, -∞) => max(-2, 4) = 4
  • For L2N2 : max( 1, -∞) => max( 1, 5) = 5
  • For L2N3 : max(-4, -∞) => max(-4,-6) =-4
  • For L2N4 : max(0, -∞) => max( 0, 6) = 4

Step 3: Now its minimizers turn, so a comparison of all nodes is done with +∞.

  • For L1N1 : min( 4, ∞) => min( 4, 5) = 4
  • For L1N2 : min(-4, ∞) => min(-4, 4) =-4

Step 4: Now, its maximizers turn again, so out of available nodes, it will choose the maximum value.

  • For RN : max( 4,-∞) => max( 4, -4) = 4

So, at last, the value at the root node comes out to be 4. The decision has been taken, and the next move will be played and again, the same procedure will be taken into account.

Limitation of Minimax Algorithm

Few limitations which are given below.

  • It compares with each data in the terminal nodes, for example, in L2N3, the maximum value is -4 between -4, -∞ and -6. But after assigning -4, it will cross-check with -6 and answer will be -4, which makes it slow. Our example just has two nodes, but in the case of Tic-tac-toe, we have 8,7,6… moves respectively at each node. And checking at each node with each value is time-consuming.
  • The complexity of increases for some high-level games such as chess and go, which has a number of pieces to move and a number of places to move it to. Which makes it very complex. And somehow if we create trees, it results in the very large branched tree.

This can be improved using Alpha-Beta Pruning. In short Alpha-Beta pruning is a kind of search algorithm whose goal is to decrease the number of nodes that needs to be evaluated, hence making it work better and execute faster.

Conclusion

Minimax is a decision-making algorithm that is used in game theory. This algorithm is for two-player games, and it considers, both the players are playing optimally. The algorithm constructs trees and follows a backward approach. The approach has been discussed in the above article with an example, and we have discussed limitations associated with it and how can we improve the algorithm.

Recommended Articles

This is a guide to the Minimax Algorithm. Here we discuss what is the Minimax Algorithm, along with working and some limitations of it. You can also go through our other related articles to learn more –

  1. KNN Algorithm
  2. Symmetric Algorithms
  3. Hierarchical Clustering Algorithm
  4. Sorting Algorithms in Java

Artificial Intelligence Training (3 Courses, 2 Project)

3 Online Courses

2 Hands-on Project

32+ Hours

Verifiable Certificate of Completion

Lifetime Access

Learn More

0 Shares
Share
Tweet
Share
Primary Sidebar
Artificial Intelligence Tutorial
  • Basics
    • Introduction to Artificial Intelligence
    • What is Artificial Intelligence
    • Careers in Artificial Intelligence
    • Future of Artificial Intelligence
    • Uses of Artificial Intelligence
    • Artificial Intelligence Ethics
    • Types of Artificial Intelligence
    • Artificial Intelligence Tools & Applications
    • Artificial Intelligence Applications
    • Advantages of Artificial Intelligence
    • Artificial Intelligence Tools
    • Benefits of Artificial Intelligence
    • Artificial Intelligence Companies
    • Artificial Intelligence Techniques
    • Artificial Intelligence Software
    • How Artificial Intelligence Works
    • Importance of Artificial Intelligence
    • Subsets of Artificial Intelligence
    • Artificial Intelligence Problems
    • Artificial Intelligence Technology
    • Application of Neural Network
    • Applications of NLP
    • Global Positioning Systems
    • Production System in AI
    • Agents in Artificial Intelligence
    • Intelligent Agent in AI
    • Artificial Intelligence Algorithm
    • Search Algorithms in AI
    • Informed Search
    • Bidirectional Search
    • Adversarial Search
    • Uninformed Search
    • Uniform Cost Search
    • Hill Climbing in Artificial Intelligence
    • Propositional Logic in AI
    • Minimax Algorithm
    • Applications of Fuzzy Logic
    • Fuzzy Logic System
    • Implementation of Neural Networks
    • Turing Test in AI
    • Recurrent Neural Networks (RNN)
    • Spiking Neural Network
    • Feedforward Neural Networks
    • Probabilistic Neural Network
    • Overfitting Neural Network
    • Means-Ends Analysis
    • DNN Neural Network
    • Principal Component Analysis
    • Artificial Intelligence Interview
  • Pattern Recognition
    • Pattern Recognition
    • Pattern Recognition Algorithms
    • Forensic Tools
    • PRTools
    • Pattern Recognition Applications

Related Courses

Artificial Intelligence Training Courses

All One Data Science Training Courses

Machine Learning Course

Footer
About Us
  • Blog
  • Who is EDUCBA?
  • Sign Up
  • Corporate Training
  • Certificate from Top Institutions
  • Contact Us
  • Verifiable Certificate
  • Reviews
  • Terms and Conditions
  • Privacy Policy
  •  
Apps
  • iPhone & iPad
  • Android
Resources
  • Free Courses
  • Database Management
  • Machine Learning
  • All Tutorials
Certification Courses
  • All Courses
  • Data Science Course - All in One Bundle
  • Machine Learning Course
  • Hadoop Certification Training
  • Cloud Computing Training Course
  • R Programming Course
  • AWS Training Course
  • SAS Training Course

© 2020 - EDUCBA. ALL RIGHTS RESERVED. THE CERTIFICATION NAMES ARE THE TRADEMARKS OF THEIR RESPECTIVE OWNERS.

EDUCBA
Free Data Science Course

Hadoop, Data Science, Statistics & others

*Please provide your correct email id. Login details for this Free course will be emailed to you
Book Your One Instructor : One Learner Free Class

Let’s Get Started

This website or its third-party tools use cookies, which are necessary to its functioning and required to achieve the purposes illustrated in the cookie policy. By closing this banner, scrolling this page, clicking a link or continuing to browse otherwise, you agree to our Privacy Policy

EDUCBA

*Please provide your correct email id. Login details for this Free course will be emailed to you
EDUCBA Login

Forgot Password?

EDUCBA
Free Data Science Course

Hadoop, Data Science, Statistics & others

*Please provide your correct email id. Login details for this Free course will be emailed to you