Scribd
Upload
15 views2 pages

Minimax Algorithm Explained for Games

The Minimax Algorithm is a decision-making strategy used in two-player games where one player (Max) aims to maximize their score while the other (Min) seeks to minimize it. The algorithm builds a game tree to evaluate all possible moves, assigning scores to end states and backpropagating these scores to determine the optimal move for Max. It is effective for small games like Tic-Tac-Toe, but for larger games, Alpha-Beta Pruning is recommended to enhance efficiency.

Uploaded by

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

Minimax Algorithm Explained for Games

The Minimax Algorithm is a decision-making strategy used in two-player games where one player (Max) aims to maximize their score while the other (Min) seeks to minimize it. The algorithm builds a game tree to evaluate all possible moves, assigning scores to end states and backpropagating these scores to determine the optimal move for Max. It is effective for small games like Tic-Tac-Toe, but for larger games, Alpha-Beta Pruning is recommended to enhance efficiency.

Uploaded by

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

Minimax Algorithm - Detailed Note

1. Definition
The Minimax Algorithm is a decision-making algorithm used in two-player turn-based games.

Key Idea:
- One player (Max) tries to maximize their score.
- The other player (Min) tries to minimize Max's score.
- The algorithm explores all possible future moves and chooses the best move.

2. Working Principle
- Build a game tree from the current state.
- Each node represents a possible game state.
- Leaf nodes represent end game states (win, lose, draw).
- Assign scores: Win +1, Lose -1, Draw 0
- Max nodes choose maximum score; Min nodes choose minimum score.
- Root node value gives the best move for Max.

3. Example: Tic-Tac-Toe
Max = X, Min = O, X's turn
Build Game Tree:
X
/| O O O
/\/\/ X XX XX X

Assign Scores:
- X wins +1, X loses -1, Draw 0
Backpropagate scores:
- Min nodes -> min score, Max nodes -> max score
Choose Optimal Move: Max selects move leading to highest score

4. Pseudocode
function minimax(node, depth, isMax):
if terminal node:
return score(node)
if isMax:
best = -inf
for child in node:
best = max(best, minimax(child, depth+1, false))
return best
else:
best = +inf
for child in node:
best = min(best, minimax(child, depth+1, true))
return best

5. Key Points
- Explores all possible moves.
- Works for small games; for large games use Alpha-Beta Pruning.
- Helps bots play optimally.

6. Last Coin Standing Example


Coins left: 4, Player can take 1,2,3 coins
Max (Bot) tries to avoid last coin

Bot Move | Coins Left | Evaluation


Take 1 | 3 | Opponent can force loss
Take 2 | 2 | Safe option
Take 3 | 1 | Leads to loss

Conclusion: Minimax helps bots make optimal decisions by evaluating all moves.

You might also like