Artificial Intelligence : Unit - 2 Part - 12 : Game Playing – Adversarial Search

 

UNIT - II

 Minimax Algorithm

---

Part A: Introduction

---

✅ What is the Minimax Algorithm?

The Minimax algorithm is a decision-making algorithm used in two-player games, where one player tries to maximize the score (MAX) and the other tries to minimize the score (MIN).

It assumes:

• The opponent plays optimally
• Both players are rational and aim to win

🧠 Used in adversarial games like Chess, Tic-Tac-Toe, Checkers.

---

Part B: Key Concepts

Term	Description
MAX Player	Tries to choose moves that maximize the score (AI)
MIN Player	Tries to choose moves that minimize the score (opponent)
Game Tree	Tree of all possible moves and states
Terminal State	A game over state (win, lose, or draw)
Utility Value	Numerical value assigned to each terminal state

---

✅ Utility Values (in Minimax)

Outcome	Utility (Score)
Win for MAX	+1
Draw	0
Win for MIN	-1

---

Part C: Working of Minimax Algorithm

---

✅ How it works:

1. Generate the game tree from the current position.
2. Evaluate terminal states using utility values.
3. Backtrack the values:
• MAX nodes choose maximum value from children.
• MIN nodes choose minimum value from children.
4. The root node will have the best value for MAX.

 

---

Part D: Minimax Algorithm – Pseudocode

function minimax(node, depth, isMaximizingPlayer):

    if node is a terminal node or depth == 0:

        return utility(node)

   

    if isMaximizingPlayer:

        bestValue = -∞

        for each child of node:

            val = minimax(child, depth - 1, False)

            bestValue = max(bestValue, val)

        return bestValue

    else:

        bestValue = +∞

        for each child of node:

            val = minimax(child, depth - 1, True)

            bestValue = min(bestValue, val)

        return bestValue

---

Part E: Features of Minimax

Feature	Description
Search Type	Adversarial search
Players	Two – MAX (AI) and MIN (opponent)
Game Type	Zero-sum game (one player’s gain is another’s loss)
Decision Strategy	MAX chooses best move assuming MIN will respond optimally
Optimality	✅ Yes, if the opponent plays optimally

---

✅ Real-World Use Cases

Area	Use Case
Chess AI	Choosing the best move by looking ahead
Tic-Tac-Toe Bots	Making unbeatable strategies
Turn-based Games	Strategy building in turn-by-turn environments

---

Part F: Advantages and Limitations

Advantages	Limitations
✅ Simple and effective for small games	❌ Slow for large games with deep game trees
✅ Finds optimal moves when opponent is rational	❌ Assumes opponent is always playing optimally
✅ Can be optimized with Alpha-Beta Pruning	❌ Time and space complexity is O(b^d) (exponential)

---

Part G: Time & Space Complexity

• Time Complexity: O(b^d)
  b = branching factor, d = depth of tree
• Space Complexity: O(b * d)

---

✅ Improving Minimax: Alpha-Beta Pruning

• Alpha-Beta Pruning is used to cut off unnecessary branches of the game tree.
• It reduces the number of nodes evaluated.
• Makes Minimax faster without affecting accuracy.

---

📝 Summary

• The Minimax algorithm is used in AI for making optimal decisions in 2-player, turn-based games.
• It builds a game tree and assigns utility values to outcomes.
• MAX chooses the best move assuming MIN plays optimally.
• Though powerful, it can be slow for large games and is best when combined with Alpha-Beta Pruning.

"Minimax is like playing a game of chess in your mind — planning your move while guessing the opponent’s best counter."