Minimax Algorithm
Introduction
The Minimax Algorithm is a decision-making algorithm used in Artificial Intelligence
(AI) for two-player competitive games such as Chess, Tic-Tac-Toe, Checkers, and Go.
It is an adversarial search algorithm that assumes:
One player (MAX) tries to maximize the score.
The other player (MIN) tries to minimize the score.
Both players play optimally.
The algorithm helps determine the best move by exploring all possible future game states.
Basic Idea
The Minimax algorithm works on the principle:
"Choose the move that maximizes your minimum guaranteed payoff."
MAX player selects the move with the highest value.
MIN player selects the move with the lowest value.
Thus, each player assumes the opponent will always make the best possible move.
Game Tree Representation
Consider the following game tree:
MAX
/ \
MIN MIN
/ \ / \
3 5 2 9
Step 1: Evaluate MIN Nodes
Left MIN node:
min (3 ,5)=3
Right MIN node:
min (2 , 9)=2
The tree becomes:
MAX
/ \
3 2
Step 2: Evaluate MAX Node
max (3 , 2)=3
Therefore, the best value for MAX is 3.
Mathematical Representation
For a MAX node:
V (n)=max s ∈Successors (n ) V ( s)
For a MIN node:
V (n)=min s ∈ Successors (n) V (s)
Working of Minimax Algorithm
Step 1
Generate the complete game tree.
Step 2
Expand all possible moves until terminal states are reached.
Step 3
Assign utility values to terminal nodes.
Example:
Result Utility
Win +1
Draw 0
Result Utility
Loss -1
Step 4
Propagate values upward through the tree.
Step 5
MAX chooses the maximum value.
Step 6
MIN chooses the minimum value.
Step 7
Continue until the root node is evaluated.
Pseudocode
function MINIMAX(node, depth, maximizingPlayer)
if node is terminal
return utility(node)
if maximizingPlayer
bestValue = -∞
for each child of node
value = MINIMAX(child, depth-1, FALSE)
bestValue = max(bestValue, value)
return bestValue
else
bestValue = +∞
for each child of node
value = MINIMAX(child, depth-1, TRUE)
bestValue = min(bestValue, value)
return bestValue
Example
Consider:
MAX
/ \
MIN MIN
/ \ / \
4 6 2 8
MIN Level
Left MIN:
min (4 ,6)=4
Right MIN:
min (2 ,8)=2
Tree becomes:
MAX
/ \
4 2
MAX Level
max (4 , 2)=4
Therefore, MAX selects the left branch and obtains value 4.
Advantages
1. Simple and easy to understand.
2. Guarantees the optimal move.
3. Effective for deterministic games.
4. Forms the basis for advanced game-playing techniques.
Disadvantages
1. High computational complexity.
2. Requires exploring many game states.
3. Large memory consumption.
4. Not efficient for games with huge search spaces.
Time Complexity
If:
b = branching factor
d = depth of game tree
Then:
d
Time Complexity=O(b )
This becomes very large for complex games like Chess.
Alpha-Beta Pruning
To improve Minimax efficiency, Alpha-Beta Pruning is used.
It:
Eliminates branches that cannot affect the final decision.
Reduces the number of nodes evaluated.
Produces the same result as Minimax.
Allows deeper searches in less time.
Applications of Minimax
Tic-Tac-Toe
Chess programs
Checkers
Connect Four
Othello/Reversi
Strategic decision-making systems
Multi-agent AI environments
Conclusion
The Minimax Algorithm is the fundamental adversarial search algorithm used in AI game
playing. It recursively evaluates all possible moves, assuming both players act optimally. The
algorithm helps the MAX player choose the move that maximizes its outcome while
minimizing potential losses caused by the opponent. Its main limitation is computational cost,
which is often reduced using Alpha-Beta Pruning.