Course contentsShow
← Computer Science
Lesson 2764 of 2,87261. AI and Search AlgorithmsFree lesson

Adversarial Search Overview

Introduction to game-playing problems where multiple agents with opposing goals make alternating moves.

Adversarial Search Overview

What You'll Learn

You'll understand how search problems change when multiple agents compete against each other with opposing goals.


From Solo to Competitive Search

Until now, all the search algorithms you've learned—BFS, DFS, A*, and heuristic search—assumed a single agent working toward a goal in a static or predictable environment. Adversarial search introduces a fundamentally different challenge: an opponent actively trying to stop you from winning.

Think of the difference between solving a maze alone versus playing chess. In a maze, the walls don't move to block you. In chess, your opponent analyzes your strategy and makes the best counter-move to defeat you.

Core Characteristics

In adversarial search problems:

  1. Multiple agents: Typically two players (you and an opponent), though the concepts extend to more
  2. Opposing goals: One player's victory is the other's defeat (zero-sum games)
  3. Alternating moves: Players take turns, each choosing actions that change the state
  4. Uncertainty from opposition: You cannot simply plan a path to victory—you must consider how your opponent will respond to every move you make

The Search Tree Changes

The state space is still a graph, but now you must model both players' possible actions at each state. The search tree alternates between layers representing your moves and your opponent's moves. You're not just searching for a path—you're searching for a strategy that works regardless of what your opponent does.

Practical Examples

Classic adversarial search problems include chess, checkers, Go, tic-tac-toe, and many video games where an AI opponent makes strategic decisions against a human player.


Key Takeaway: Adversarial search extends state-space search to competitive, multi-agent environments where you must plan not just your own actions, but anticipate and counter an intelligent opponent's best responses.