Scribd
Upload
6 views12 pages

Minimax Algorithm Search

The Mini-Max Algorithm is a recursive decision-making method used in two-player games, where one player (MAX) aims for the highest score while the other (MIN) seeks to minimize it. It employs a Depth-First Search strategy to explore the game tree, ensuring optimal decisions if both players play optimally, though it can be slow and memory-intensive for complex games. Common applications include chess, tic-tac-toe, and checkers.

Uploaded by

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

Minimax Algorithm Search

The Mini-Max Algorithm is a recursive decision-making method used in two-player games, where one player (MAX) aims for the highest score while the other (MIN) seeks to minimize it. It employs a Depth-First Search strategy to explore the game tree, ensuring optimal decisions if both players play optimally, though it can be slow and memory-intensive for complex games. Common applications include chess, tic-tac-toe, and checkers.

Uploaded by

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

Mini-Max Algorithm

in Artificial
Intelligence
INTRODUCTION

Backtracking Algorithm: Mini-max is a recursive or


backtracking algorithm used for decision-making and
game theory.
Two-Player Games: It is designed for games where
two players (MAX and MIN) compete against each
other.
Goal: Both players try to play optimally; the Maximizer
aims for the highest score, while the Minimizer tries to
keep the Maximizer’s score as low as possible.
 Search Type: It uses a Depth-First Search (DFS)
strategy to explore the game tree.
Steps of Working of the Algorithm

The complete game tree is generated.


Values are assigned to all terminal nodes.
DFS is applied to reach leaf nodes.
MIN player selects the minimum value.
MAX player selects the maximum value.
 The final decision is taken at the root node.
EXAMPLE
Properties
 Complete- Min-Max algorithm is Complete. It will
definitely find a solution (if exist), in the finite search
tree.
 Optimal- Min-Max algorithm is optimal if both
opponents are playing optimally.
 Time complexity- As it performs DFS for the game-
tree, so the time complexity of Min-Max algorithm
is O(bm), where b is branching factor of the game-tree,
and m is the maximum depth of the tree.
 Space Complexity- Space complexity of Mini-max
algorithm is also similar to DFS which is O(bm).
Advantages

 Always selects the best possible move


 Provides optimal decision making
 Easy to understand logically
 Useful in two-player strategic games.
Disadvantages

Becomes slow for complex games.


Has high time complexity.
Requires large memory for deep trees.
 Not suitable for real-time applications.
Applications of Mini-max
Algorithm
The Mini-Max algorithm is commonly used in:
Chess
Tic-Tac-Toe
Checkers
Connect Four
 Game playing Artificial Intelligence systems
Conclusio
n
 The Mini-Max Algorithm is a fundamental
AI search technique used in game playing
systems. It guarantees optimal decisions,
but its efficiency can be improved using
optimization techniques.

You might also like