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:
- Multiple agents: Typically two players (you and an opponent), though the concepts extend to more
- Opposing goals: One player's victory is the other's defeat (zero-sum games)
- Alternating moves: Players take turns, each choosing actions that change the state
- 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.