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

 

UNIT - II

 Game Playing – Adversarial Search

---

Part A: Introduction

---

What is Game Playing in AI?

Game Playing in AI refers to designing intelligent agents that can play games against an opponent and try to win using logic, planning, and prediction.

Examples:

• Chess
• Tic-Tac-Toe
• Checkers
• Multiplayer board games

---

What is Adversarial Search?

An adversarial search is a search problem where multiple agents compete (e.g., a game between two players) and the goal of one player is to defeat the other.

In normal search, there is only one agent trying to reach the goal.
In adversarial search, the environment is dynamic and hostile because the opponent also tries to win.

---

Part B: Characteristics of Adversarial Games

Feature	Description
Competitive	Two or more players compete (not cooperative)
Turn-based	Players take turns one by one
Zero-sum	One player’s gain = Other player’s loss
Perfect Information	All information is visible to both players (e.g., Chess)
No Chance	No randomness involved (some games like Ludo have chance elements)

---

Part C: Game as a Search Problem

To make AI play a game, we model it as a search problem.

Component	Description
Initial State	The starting board (e.g., starting position in Chess)
Players	MAX (AI player) and MIN (opponent)
Successor Function	Generates next possible legal moves
Terminal Test	Checks if the game is over
Utility Function	Assigns a numeric value (win = +1, lose = -1, draw = 0)

---

Part D: MINIMAX Algorithm

---

What is Minimax?

Minimax is a decision rule used in two-player, turn-based, zero-sum games.
It assumes:

• One player (MAX) tries to maximize the score
• Other player (MIN) tries to minimize the score

---

How It Works:

• Build a game tree of all possible moves
• Evaluate utility values at the terminal states
• Backtrack the values:
• MAX picks the highest value from its children
• MIN picks the lowest value

 

Part E: Algorithm – Minimax (Pseudocode)

function minimax(node, depth, maximizingPlayer):

    if node is terminal or depth == 0:

        return utility(node)

 

    if maximizingPlayer:

        maxEval = -∞

        for each child of node:

            eval = minimax(child, depth-1, false)

            maxEval = max(maxEval, eval)

        return maxEval

    else:

        minEval = +∞

        for each child of node:

            eval = minimax(child, depth-1, true)

            minEval = min(minEval, eval)

        return minEval

---

Part F: Alpha-Beta Pruning

---

✅ What is Alpha-Beta Pruning?

Alpha-Beta Pruning is a technique used to optimize the Minimax algorithm by eliminating branches that do not affect the final decision.

• Alpha: Best value that MAX can guarantee
• Beta: Best value that MIN can guarantee

It avoids unnecessary calculations, making Minimax faster and more efficient.

---

✅ Benefit:

• Reduces number of nodes evaluated from O(b^d) to O(b^(d/2))
  → where b = branching factor, d = depth

---

✅ Applications of Adversarial Search

• Chess engines (e.g., Stockfish)
• AI opponents in games (e.g., Checkers, Tic-Tac-Toe)
• Game bots in mobile and PC games
• Decision-making in strategy simulations

---

Part G: Summary Table

Feature	Minimax Search	Alpha-Beta Pruning
Purpose	Decision-making in 2-player games	Optimizing Minimax
Time Complexity	O(b^d)	O(b^(d/2)) with good pruning
Accuracy	✅ Finds the best move	✅ Same as Minimax
Space Efficient	❌ No (uses full tree)	✅ Yes (skips unneeded branches)
Use in AI	Game playing and strategic reasoning	Speeding up competitive game AI

---

📝 Summary

• Game playing in AI uses adversarial search to model competition between two players.
• The Minimax algorithm is used to decide the best move assuming the opponent plays optimally.
• Alpha-Beta Pruning enhances Minimax by reducing the number of nodes evaluated.
• These methods are essential for creating smart AI game players.

Think of adversarial search like “planning your move and predicting your opponent’s move to always stay ahead!”