Adversarial Search

So far, we studied problems where an intelligent agent works alone. In many real-world scenarios, however, the agent must make decisions while competing against another intelligent agent.

Such problems are called adversarial problems, and the techniques used to solve them fall under adversarial search.

What Is Adversarial Search?

Adversarial search is used when:

• There are two or more agents
• Each agent has opposing goals
• One agent’s gain is another agent’s loss

The most common examples of adversarial problems are games such as chess, tic-tac-toe, checkers, and Go.

Real-World Connection

Adversarial decision-making is not limited to games.

• Stock trading: Buyers and sellers compete
• Cybersecurity: Defenders vs attackers
• Negotiation systems: Conflicting interests
• Competitive pricing: Companies reacting to rivals

In all these cases, an intelligent agent must consider what the opponent might do next.

The Idea Behind Game Trees

Adversarial problems are represented using a game tree.

• Nodes represent game states
• Edges represent possible moves
• Leaf nodes represent final outcomes

Each player reaches a turn alternately and chooses the best possible move for themselves.

The Minimax Principle

The core idea of adversarial search is the Minimax algorithm.

Minimax assumes:

• The agent (MAX) tries to maximize the score
• The opponent (MIN) tries to minimize the score
• Both players play optimally

The agent chooses the move that leads to the best possible outcome assuming the opponent will respond in the worst possible way.

Simple Minimax Example (Concept)

Imagine a game where possible outcomes are scored as:

• +1 → Win for the agent
• 0 → Draw
• -1 → Loss for the agent

The agent evaluates all possibilities and selects the move that maximizes its minimum guaranteed score.

Implementing a Simple Minimax Algorithm

Below is a simplified Python implementation of the Minimax algorithm.

def minimax(depth, is_maximizing):
    if depth == 0:
        return 1
    if depth == 1:
        return -1
    if depth == 2:
        return 0

    if is_maximizing:
        best = -float("inf")
        for _ in range(2):
            value = minimax(depth - 1, False)
            best = max(best, value)
        return best
    else:
        best = float("inf")
        for _ in range(2):
            value = minimax(depth - 1, True)
            best = min(best, value)
        return best

print(minimax(3, True))
  

Code Explanation

This code simulates a very small game tree.

• The depth represents how far the game continues
• MAX tries to maximize the score
• MIN tries to minimize the score
• Each recursive call evaluates future outcomes

The algorithm propagates values upward to decide the best move at the root.

Output Explanation

The output value 0 indicates that, assuming optimal play by both sides, the game results in a draw.

This demonstrates how Minimax considers the opponent’s best response before making a decision.

Why Minimax Works

Minimax works because it models rational opponents. The agent does not assume mistakes; it prepares for the worst-case scenario.

This makes adversarial search reliable in competitive environments.

Limitations of Minimax

Although powerful, Minimax has limitations:

• Exponential growth of the game tree
• High computational cost
• Not scalable without optimizations

To overcome these issues, techniques such as Alpha-Beta Pruning are used, which we will study next.

Practice Questions

Quick Quiz