Mini-Max Algorithm
Ms. Richa Singh
CSE(AI)
1
CONTENTS
❑ Basic
❑ Goal
❑ Algorithm
❑ Example 1
❑ Example 2
❑ Example 3
❑ Properties
❑ Limitation
2
BASIC
Mini-max algorithm is a recursive or backtracking
algorithm which is used in decision-making and
game theory. It provides an optimal move for the
player assuming that opponent is also playing
optimally.
Mini-Max algorithm uses recursion to search through
the game-tree.
Min-Max algorithm is mostly used for game playing
in AI. Such as Chess, Checkers, tic-tac-toe, go, and
various tow-players game. This Algorithm computes
the minimax decision for the current state.
In this algorithm two players play the game, one is3
called MAX and other is called MIN.
CONTI…
Both the players fight it as the opponent player gets
the minimum benefit while they get the maximum
benefit.
Both Players of the game are opponent of each other,
where MAX will select the maximized value and MIN
will select the minimized value.
The minimax algorithm performs a depth-first search
algorithm for the exploration of the complete game
tree.
The minimax algorithm proceeds all the way down to
the terminal node of the tree, then backtrack the tree
as the recursion. 4
GOAL
The goal is to find the best move for the player.
To do so, player can just choose the node with best
evaluation score.
To make the process smarter, player can also look
ahead and evaluate potential opponent's moves.
5
ALGORITHM
Generally defined steps of the algorithm:
Step 1: Construct the complete game tree
Step 2: Evaluate scores for leaves using the evaluation
function
Step 3: Back-up scores from leaves to root, considering
the player type:
For max player, select the child with the maximum
score
For min player, select the child with the minimum
score
Step 4: At the root node, choose the node with max
value and perform the corresponding move 6
EXAMPLE 1
Considera 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 your7
opponent also plays optimally?
CONTI…
8
CONTI…
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.
9
CONTI…
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.
10
CONTI…
11
CONTI…
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. 12
EXAMPLE 2
13
EXAMPLE 3
Below we have taken an example of game-tree
which is representing the two-player game.
Inthis example, there are two players one is
called Maximizer and other is called
Minimizer.
Maximizer will try to get the Maximum
possible score, and Minimizer will try to get
the minimum possible score.
14
CONTI…
This algorithm applies DFS, so in this game-
tree, we have to go all the way through the
leaves to reach the terminal nodes.
Atthe terminal node, the terminal values are
given so we will compare those value and
backtrack the tree until the initial state
occurs. Following are the main steps involved
in solving the two-player game tree:
15
CONTI…
Step-1:
In the first step, the algorithm generates the
entire game-tree and apply the utility
function to get the utility values for the
terminal states.
In the below tree diagram, let's take A is the
initial state of the tree.
Suppose maximizer takes first turn which
has worst-case initial value =- infinity, and
minimizer will take next turn which has 16
worst-case initial value = +infinity.
17
CONTI…
Step 2:
Now, first we find the utilities value for the
Maximizer, its initial value is -∞, so we will compare
each value in terminal state with initial value of
Maximizer and determines the higher nodes values.
It will find the maximum among the all.
For node D max(-1,- -∞) => max(-1,4)= 4
For Node E max(2, -∞) => max(2, 6)= 6
For Node F max(-3, -∞) => max(-3,-5) = -3
For node G max(0, -∞) = max(0, 7) = 7
18
19
CONTI…
Step 3:
In the next step, it's a turn for minimizer, so
it will compare all nodes value with +∞, and
will find the 3rd layer node values.
For node B= min(4,6) = 4
For node C= min (-3, 7) = -3
20
21
CONTI…
Step 4:
Now it's a turn for Maximizer, and it will
again choose the maximum of all nodes value
and find the maximum value for the root
node.
In this game tree, there are only 4 layers,
hence we reach immediately to the root node,
but in real games, there will be more than 4
layers.
For node A max(4, -3)= 4
22
23
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).
24
LIMITATION
The main drawback of the minimax
algorithm is that it gets really slow for
complex games such as Chess, go, etc.
This type of games has a huge branching
factor, and the player has lots of choices to
decide.
This limitation of the minimax algorithm can
be improved from alpha-beta
pruning which we have discussed in the 25
next topic.
THANKS
26