Scribd
Upload
57 views8 pages

Min - Max Algorithm

The Min-Max algorithm is a recursive decision-making strategy used in game theory, particularly in two-player games like chess and tic-tac-toe. It involves a maximizing player and a minimizing player, where the maximizer aims to maximize their score while the minimizer aims to minimize it, using depth-first search to explore the game tree. The algorithm evaluates terminal nodes and backtracks to determine the optimal move for the maximizing player based on the assumption that the opponent plays optimally.

Uploaded by

nkaintura388
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
57 views8 pages

Min - Max Algorithm

The Min-Max algorithm is a recursive decision-making strategy used in game theory, particularly in two-player games like chess and tic-tac-toe. It involves a maximizing player and a minimizing player, where the maximizer aims to maximize their score while the minimizer aims to minimize it, using depth-first search to explore the game tree. The algorithm evaluates terminal nodes and backtracks to determine the optimal move for the maximizing player based on the assumption that the opponent plays optimally.

Uploaded by

nkaintura388
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

MIN – MAX

ALGORITHM
Min – Max
Algorithm
• It is a recursive or backtracking algorithm that
can be used for decision making or in game
theory
• In game theory it provides optimal move for a
player
• Uses recursion to search through the game tree
• Mostly used in chess, tic – tac – toe etc.
• In this algorithm two players plays the game:
One is called as Max and other is called as Min
• Both player fight as the opponent players gets
the minimum benefit
• In this gaming strategy the Max will selects
the Maximized value where as the Min will
selects the Minimized value.

• The minmax algorithm performs a depth –


first search algorithm for the exploration of
the complete game tree

• The minmax algorithm proceeds all the way


down to the terminal node of the tree, then
backtrack the tree as the recursion.
function minimax(node, depth, maximizingPlayer) is
if depth ==0 or node is a terminal node then
return static evaluation of node

Pseudocode for if MaximizingPlayer then


maxEva= -infinity
// for Maximizer Player

Min-Max
for each child of node do
eva= minimax(child, depth-1, false)
maxEva= max(maxEva,eva) //

Algorithm gives Maximum of the values


return maxEva

else // for Minimizer player


minEva= +infinity
for each child of node do
eva= minimax(child, depth-1, true)
minEva= min(minEva, eva) //
gives minimum of the values
return minEva
Working of Min Max
Algorithm
• The working of the Min Max Algorithm can be
understood by using an example
• There are two players in this one is called as
Maximiser and another is called as Minimiser
• Maximiser tries to score maximum score
• Minimiser tries to score minimum score
• Algorithm uses DFS, thus we have to traverse
through leaves to reach the terminal nodes
• At terminal nodes the specified values are
compared
• Example:
• Consider a game which has 4 final states and paths to reach final state are from root
to 4 leaves of a perfect binary tree as shown below.
• Assume you are the maximizing player and you get the first chance to move, i.e.,
you are at the root and your opponent at next level.
• Which move you would make as a maximizing player considering that your
opponent also plays optimally?
• Since this is a backtracking based algorithm, it tries all
possible moves, then backtracks and makes a decision.

 Maximizer goes LEFT:


 It is now the minimizers turn.
 The minimizer now has a choice between 3 and 5.
 Being the minimizer it will definitely choose the
least among both, that is 3

 Maximizer goes RIGHT:


 It is now the minimizers turn.
 The minimizer now has a choice between 2 and 9.
 He will choose 2 as it is the least among the two
values.

• Being the maximizer you would choose the larger value that
is 3. Hence the optimal move for the maximizer is to go
LEFT and the optimal value is 3
• Now the game tree looks like below :

• The above tree shows two possible scores when maximizer makes left
and right moves.
• Note: Even though there is a value of 9 on the right subtree, the minimizer
will never pick that. We must always assume that our opponent plays
optimally.

You might also like