Mini-Max Algorithm in

Artificial Intelligence
•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 is called MAX and
other is called MIN.
•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.
 Minimax algorithm
▪ Minimax is a decision rule algorithm, which is
represented as a game-tree.
▪ It has applications in decision theory, game theory ,
statistics and philosophy.
▪ Minimax is applied in two player games. The one is the
min and the other is the max player.
▪ By agreement the root of the game-tree represents the
max player.
▪ It is assumed that each player aims to do the best move
for himself and therefore the worst move for his
opponent in order to win the game.

4
 IMPORTANT POINTS
• BACKTRACKING ALGORITHM

• BEST MOVE STRATEGY

•MAX WILL TRY TO MAXIMIZE ITS UTILITY(BEST

MOVE)

•MIN WILL TRY TO MINIMZE UTILITY (WORST

MOVE)
 Minimax algorithm

Max 3

Min 3 2 2

Utilit
y

3 8 12 2 4 6 14 5 2 9
 Minimax algorithm
Max

Min

Max

Utility
4 3 6 2 2 1 9 5 3 1 7 5
7
 Minimax algorithm
Max

Min

Max 4

Utilit
y 4 36 2 2 1 9 5 3 1 7 5
8
 Minimax algorithm
Max

Min

Max 4 6

Utilit
y 4 36 2 2 1 9 5 3 1 7 5
9
 Minimax algorithm
Max

Min 4

Max 4 6

Utilit
y 4 36 2 2 1 9 5 3 1 7 5
10
 Minimax algorithm
Max

Min 4

Max 4 6 2

Utilit
y 4 36 2 2 1 9 5 3 1 7 5
11
 Minimax algorithm
Max

Min 4

Max 4 6 2 9

Utilit
y 4 36 2 2 1 9 5 3 1 7 5
12
 Minimax algorithm
Max

Min 4 2

Max 4 6 2 9

Utilit
y 4 36 2 2 1 9 5 3 1 7 5
13
 Minimax algorithm
Max

Min 4 2

Max 4 6 2 9 3

Utilit
y 4 36 2 2 1 9 5 3 1 7 5
14
 Minimax algorithm
Max

Min 4 2

Max 4 6 2 9 3 7

Utilit
y 4 36 2 2 1 9 5 3 1 7 5
15
 Minimax algorithm
Max

Min 4 2 3

Max 4 6 2 9 3 7

Utilit
y 4 36 2 2 1 9 5 3 1 7 5
16
 Minimax algorithm
4
Max

Min 4 2 3

Max 4 6 2 9 3 7

Utilit
y 4 36 2 2 1 9 5 3 1 7 5
17
 Minimax Algorithm
function MINIMAX-DECISION(state) returns an action
inputs: state, current state in game
vMAX-VALUE(state)
return the action in SUCCESSORS(state) with value v
function MAX-VALUE(state) returns a utility value
if TERMINAL-TEST(state) then return UTILITY(state)
v∞
for a,s in SUCCESSORS(state) do
v  MAX(v,MIN-VALUE(s))
return v
function MIN-VALUE(state) returns a utility value
if TERMINAL-TEST(state) then return UTILITY(state)
v∞
for a,s in SUCCESSORS(state) do
v  MIN(v,MAX-VALUE(s)) 21
return v
 Properties of minimax

Complete?Yes (if tree is finite)

Optimal? Yes (against an optimal opponent) Time
complexity? O(bm)
Space complexity? O(bm) (depth-first exploration,for
algorithm that generates all successors at once or
O(m) for an algorithm that generates suuccesors one
at atime )
For chess, b ≈ 35, m ≈100 for "reasonable" games
→ exact solution completely infeasible

19
Minimax advantages:
-Returns an optimal action, assuming perfect
opponent play.
Minimax is the simplest possible (reasonable) game
search algorithm.
-Tic-Tac-Toe player, chances are you either looked this
up on Wikipedia, or
invented it in the process.)
Minimax disadvantages: It's completely infeasible in
practice.
! When the search tree is too large, we need to limit
the search depth and
apply an evaluation function to the cut-off states.
20