Scribd
Upload
63 views11 pages

Institute of Engineering and Technology: Topic: Mini-Max Algorithm in AI

The Mini-Max Algorithm is a recursive decision-making tool used in AI for two-player games, aiming to optimize moves for both players, MAX and MIN. It explores the game tree to find the best possible outcomes while facing limitations in complex games due to high computational demands. Alpha-Beta Pruning is suggested as a solution to improve efficiency by eliminating unnecessary calculations.

Uploaded by

alankritsrivastav8
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
63 views11 pages

Institute of Engineering and Technology: Topic: Mini-Max Algorithm in AI

The Mini-Max Algorithm is a recursive decision-making tool used in AI for two-player games, aiming to optimize moves for both players, MAX and MIN. It explores the game tree to find the best possible outcomes while facing limitations in complex games due to high computational demands. Alpha-Beta Pruning is suggested as a solution to improve efficiency by eliminating unnecessary calculations.

Uploaded by

alankritsrivastav8
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 11

INSTITUTE OF ENGINEERING AND TECHNOLOGY

Topic: Mini-Max Algorithm in AI


Subject: Artificial Intelligence

Presented To: Presented By:


Dr. Avadhesh Dixit Mehul Prajapati(22122)
Assistant Professor (CSE) Mohd.Hashir(22123)
CSE(3rd year)
Table of content

1. Introduction to Mini-Max Algorithm


2. Game Players – Max and Min
3. How Mini-Max Algorithm Works
4. Mini-Max Pseudocode
5. Working Example of Mini-Max
Algorithm
6. Properties of Mini-Max Algorithm
7. Limitations of Mini-Max Algorithm
8. Conclusion
Introduction to Mini-Max Algorithm

● Mini-Max is a recursive or backtracking


algorithm used in decision-making and game
theory.
● Provides the optimal move for a player, assuming
the opponent also plays optimally.
● Commonly applied in AI for two-player games like
Chess, Tic-Tac-Toe, and Checkers.
Game Players – Max and Min

● The game involves two players:

MAX: Aims to maximize their score.

MIN: Aims to minimize the opponent's score.

● Each player tries to maximize their own benefit


while minimizing the opponent’s benefit.
How Mini-Max Algorithm Works
● The algorithm explores the entire game
tree using recursion.
● MAX tries to find the highest score at its
turn.
● MIN tries to find the lowest score at its
turn.
● The algorithm continues until it reaches a
terminal node (end of game).
Mini-Max Pseudocode

★ function minimax(node, depth,


maximizingPlayer)
★ if depth == 0 or node is a terminal
node
★ return evaluation of node
● If maximizingPlayer, calculate the maximum
value for all children.
● If minimizingPlayer, calculate the minimum
value for all children
Working Example of Mini-Max Algorithm

● Example of a game tree with terminal node


values.
● Maximizer will attempt to get the highest
possible score.
● Minimizer will attempt to reduce this score.
● At each turn, players select moves to
maximize or minimize the score, respectively.
Mini-Max Algorithm Properties

● Complete: Guarantees a solution in a finite search tree.


● Optimal: Optimal if both players play optimally.
● Time Complexity: O(bm)O(b^m)O(bm), where b =
branching factor, m = depth of the game tree.
● Space Complexity: Same as DFS, O(bm)O(b^m)O(bm).
Limitations of Mini-Max Algorithm
● Slow for complex games like Chess and Go due
to large branching factors.
● Requires a large amount of computation as the
tree depth increases.
● Solution: Alpha-Beta Pruning helps to reduce
unnecessary calculations by cutting off
unneeded branches.
Conclusion

● Mini-Max is a powerful algorithm for


decision-making in two-player games.
● Despite its efficiency, it struggles with complex
games due to computational demands.
● Optimization with Alpha-Beta Pruning enhances its
performance.

You might also like