What a second rational player changes about an optimization — everything.
Concepts 10 min Intermediate April 13, 2026
Your search agent (like the A* algorithm from the previous article) found the optimal path through the maze. But what happens when someone on the other side is actively rearranging the walls? The moment a second intelligent agent enters the picture — one with goals that directly oppose yours — everything changes.
This chapter shows why the jump from a single agent to a multi-agent system is not simply "more of the same" but a fundamental paradigm shift. Game theory provides the mathematical toolkit for this transformation — and it is the foundation upon which all adversarial AI algorithms are built.
From Solo to Duel — Multi-Agent Systems
In the previous articles, your agent always worked against a static environment: a maze, a road network, a puzzle. The environment had no goals of its own. Now that changes fundamentally.
Multi-Agent System
AnalogyDefinition
Driving alone on an empty highway is a single-agent problem — you optimize your route against the static road network. Playing chess is an adversarial two-agent problem — your opponent actively works to block your plans and set traps. Rush-hour traffic is a complex multi-agent system where thousands of drivers with mixed interests (some cooperative, some competitive) interact simultaneously.
Example
In chess, the opponent's moves are fully visible (complete information). In real traffic, you cannot see every driver's intentions (incomplete information). The analogy correctly captures this gradation but simplifies the fact that traffic involves thousands of agents, not just two.
Analogy:
Driving alone on an empty highway is a single-agent problem — you optimize your route against the static road network. Playing chess is an adversarial two-agent problem — your opponent actively works to block your plans and set traps. Rush-hour traffic is a complex multi-agent system where thousands of drivers with mixed interests (some cooperative, some competitive) interact simultaneously.
Example
In chess, the opponent's moves are fully visible (complete information). In real traffic, you cannot see every driver's intentions (incomplete information). The analogy correctly captures this gradation but simplifies the fact that traffic involves thousands of agents, not just two.
Definition:
A multi-agent system consists of multiple agents acting in a shared environment whose actions mutually influence each other. The central classification runs along two axes: cooperative vs. competitive (do the agents share goals or work against each other?) and complete vs. incomplete information (can every agent see the full state, like in chess, or are parts hidden, like in poker?).
Single Agent (e.g. A* in a maze)
Static environment. No counter-moves. The optimal path remains stable. Pure optimization.
Multi-Agent (e.g. chess game)
Dynamic environment. The opponent responds intelligently. Every move changes the situation. Strategic thinking required.
5,478
Legal positions in Tic-Tac-Toe: A computer solves the game in milliseconds
~10⁴⁴
Legal positions in chess: Exhaustive analysis impossible — heuristics required
Tic-Tac-Toe has only 9 squares yet 5,478 legal game positions. Because this state space is tiny by computational standards, a computer can exhaustively analyze every possible game in milliseconds and compute a mathematically perfect strategy (the game is "solved"). Chess, by contrast, has approximately 10⁴⁴ legal positions — exhaustive analysis is impossible, which is why chess engines need heuristic strategies.
2017 Breakthroughs
AlphaZero Masters Three Games
The birth of a universal game AI through pure self-learning. In December 2017, DeepMind presented AlphaZero — a system that mastered three completely different strategy games without any prior knowledge: chess, shogi, and Go. The tabula rasa approach meant: no opening databases, no human strategies, only the rules of the game as a starting point. Within 24 hours, AlphaZero achieved superhuman performance — in chess after just 4 hours, in shogi after 2 hours. In the 100-game match against Stockfish, it won 28 games, lost none, and drew 72. Its distinctiveness lay in efficient search behavior: while Stockfish evaluates 60 million positions per second, AlphaZero analyzes only 60,000 — but far more purposefully through its deep neural network. This performance impressively demonstrated the generalizability and domain-independence of pure reinforcement learning.
Misconception: An opponent just makes the search tree bigger
It is not about size. The fundamental NATURE of the problem changes. In single-agent search, the environment is passive. In adversarial search, the "environment" actively works against you. You cannot simply find the best path — you must find the best path assuming the opponent plays optimally against you. This is a qualitative shift, not a quantitative one.
Zero-Sum Games — The Fixed Pie
Now that you understand the paradigm shift, we need a mathematical model for pure competition. The zero-sum game is that model: what one player gains, the other loses — exactly.
Zero-Sum Game
AnalogyDefinition
Imagine one cake on a table shared between two people. Whatever you take, I lose. The cake never grows. If you get 70%, I get 30%. The total is always 100%. That is a zero-sum game. But in real economics, the "cake" can grow — two businesses partnering might create a bigger cake for both (positive-sum game).
Example
A real cake can be enjoyed differently by different people (you prefer the frosting, I prefer the sponge) — utility is subjective. In the mathematical model, payoffs are assumed to be objective numerical values on a common scale. This simplification is what makes the math tractable.
Analogy:
Imagine one cake on a table shared between two people. Whatever you take, I lose. The cake never grows. If you get 70%, I get 30%. The total is always 100%. That is a zero-sum game. But in real economics, the "cake" can grow — two businesses partnering might create a bigger cake for both (positive-sum game).
Example
A real cake can be enjoyed differently by different people (you prefer the frosting, I prefer the sponge) — utility is subjective. In the mathematical model, payoffs are assumed to be objective numerical values on a common scale. This simplification is what makes the math tractable.
Definition:
A zero-sum game is a mathematical model of pure competition where one player's gain exactly equals the other player's loss — the sum of all payoffs is always zero. This is formalized through payoff matrices that list all possible strategy combinations and their numerical outcomes. Chess is the canonical example: White wins (+1) means Black loses (-1); a draw gives both 0.
Payoff Matrix: Rock-Paper-Scissors
Consider the 3×3 payoff matrix from Player 1's perspective:
Spieler / Player
Rock
Paper
Scissors
Rock
0
−1
+1
Paper
+1
0
−1
Scissors
−1
+1
0
Each cell shows Player 1's payoff. Player 2 receives the negative value (zero-sum). Reading the matrix: Rock beats Scissors (+1), loses to Paper (-1). Key insight: the optimal strategy is to play each option with exactly 1/3 probability (mixed strategy). Any deviation — even slightly favoring Rock — is exploitable by an observant opponent.
Why Determinism Fails
If you play a non-uniform strategy in Rock-Paper-Scissors — say 34% Rock, 33% Paper, 33% Scissors — an observant opponent can detect the pattern and play Paper more often. Any deviation from 1/3 per option gives the opponent exploitable information. That is why the optimal strategy is strictly uniform: maximum unpredictability.
Misconception: Every competitive situation is zero-sum
Most real-world competition is NOT zero-sum. Business competition often expands markets (positive-sum). International trade creates mutual benefits. Even in some games, cooperation can improve outcomes for all players (see Nash Equilibrium and the Prisoner's Dilemma). The zero-sum assumption is a deliberate simplification for mathematical tractability, not a universal law.
Nash Equilibrium — When Nobody Can Do Better
You now know zero-sum games and payoff matrices. But how do you find a "good" strategy? John Nash provided the answer in 1950: the equilibrium where no player can unilaterally improve.
Nash Equilibrium
AnalogyDefinition
Two restaurants sit side by side on the same street. Each sets its lunch price. Over time, both have optimized their prices so that any unilateral change would make them worse off. Raising the price loses customers to the neighbor; lowering it cuts margins below viability. They have reached a Nash equilibrium. Neither restaurant is thrilled with the outcome, but neither can unilaterally improve it.
Example
Real restaurants can differentiate (cuisine type, ambiance, service), creating a multi-dimensional competition that the simple pricing model does not capture. Also, real businesses can communicate and collude (illegal in many jurisdictions), which the Nash framework assumes away.
Analogy:
Two restaurants sit side by side on the same street. Each sets its lunch price. Over time, both have optimized their prices so that any unilateral change would make them worse off. Raising the price loses customers to the neighbor; lowering it cuts margins below viability. They have reached a Nash equilibrium. Neither restaurant is thrilled with the outcome, but neither can unilaterally improve it.
Example
Real restaurants can differentiate (cuisine type, ambiance, service), creating a multi-dimensional competition that the simple pricing model does not capture. Also, real businesses can communicate and collude (illegal in many jurisdictions), which the Nash framework assumes away.
Definition:
A Nash equilibrium is a strategy profile (one strategy per player) where no individual player can improve their payoff by unilaterally changing their strategy — assuming all other players keep their strategies unchanged. John Nash proved in 1950 that every finite game has at least one Nash equilibrium (possibly in mixed strategies). The crucial subtlety: a Nash equilibrium is STABLE (nobody wants to deviate) but not necessarily OPTIMAL (there might exist outcomes that are better for everyone, but they are not stable).
The Prisoner's Dilemma — Stability Without Optimality
The most famous game in game theory. Two suspects are interrogated separately. Each can either Cooperate (stay silent) or Defect (betray the other). Note: Here the payoffs are measured in years of imprisonment — less is better, unlike Rock-Paper-Scissors.
1
Setup Two suspects, interrogated separately. Each has two options: Cooperate (stay silent) or Defect (betray the other).
2
Payoffs Both cooperate: 1 year each. One defects, the other cooperates: defector goes free, cooperator gets 6 years. Both defect: 3 years each.
3
Dominant Strategy No matter what the other does: Defecting is always better. If the other cooperates? Defecting gives 0 instead of 1 year. If the other defects? Defecting gives 3 instead of 6 years.
4
The Paradox The Nash equilibrium is (Defect, Defect) with 3 years each — even though (Cooperate, Cooperate) with 1 year each would be better for BOTH. Stability is not optimality.
Spieler / Player
Cooperate
Defect
Cooperate
1 / 1 years
6 / 0 years
Defect
0 / 6 years
3 / 3 years
The Nash equilibrium of the Prisoner's Dilemma is (Defect, Defect) because Defecting is the dominant strategy for both players: regardless of what the other does, Defecting is always the better choice. Yet mutual cooperation (1 year instead of 3) would benefit both. The equilibrium is stable but collectively suboptimal — a key result of game theory.
Misconception: Nash equilibrium is the best outcome
The Prisoner's Dilemma proves exactly the opposite. The Nash equilibrium (mutual betrayal, 3 years each) is WORSE for both players than mutual cooperation (1 year each). A Nash equilibrium guarantees stability (nobody can improve alone), not optimality (best possible result). This distinction is fundamental for AI agent design: agents that blindly optimize individually can produce collectively worse outcomes.
Historical Context: The Founders of Game Theory
Mathematical game theory was founded in 1944 by John von Neumann and Oskar Morgenstern in their work "Theory of Games and Economic Behavior." They formalized zero-sum games and proved the Minimax theorem. Six years later, in 1950, mathematician John Nash decisively expanded the field in his PhD dissertation at Princeton University: he proved that every finite game — not just zero-sum games — has at least one equilibrium. For this contribution, Nash received the 1994 Nobel Prize in Economics (shared with John Harsanyi and Reinhard Selten). Game theory is now a cornerstone of AI research: from the MinMax algorithm (next article) to multi-agent reinforcement learning to automated auction systems.
Interactive: How Likely Is the Opponent to Cooperate?
In the Prisoner's Dilemma, everything depends on whether the other player cooperates. But what if you can observe signals? A cooperative opponent often sends positive signals — but a deceptive opponent can also appear friendly. Bayes' theorem shows how to update your estimate of the opponent's true intent. Adjust the values and observe how your assessment changes.
Scenario: Medical Test
A disease affects a certain proportion of the population. A test detects the disease with a certain hit rate, but also produces false-positive results in healthy people. How likely is the disease really when the test comes back positive?
Input Values
%
%
%
Examples:
Bayes' Calculation
P(B)= P(B|A) × P(A) + P(B|¬A) × P(¬A)
P(B)= 0.9500 × 0.0100 + 0.0500 × 0.9900 = 0.0590
P(A|B)= P(B|A) × P(A) / P(B)
P(A|B)= 0.9500 × 0.0100 / 0.0590 = 0.1610
Result
16.1%
P(A|B) — Probability of disease given a positive test
Before (Prior)
1%
After (Posterior)
16.1%
Bayes factor: The test has increased by a factor of 16.1 the probability (from 1% to 16.1%).
The Bayes Paradox
Although the test has 95% sensitivity, the probability given a positive result is only 16.1%. This is due to the low base rate (1%): Among 1,000 tested people, there are 5 false alarms but only 1 true hits. The false positives overwhelm the real cases.
Visualized: 1,000 People Tested
1
Sick & tested positive
(True Positive)
0
Sick & tested negative
(False Negative)
5
Healthy & tested positive
(False Positive)
94
Healthy & tested negative
(True Negative)
Of 6 positive tests, only 1 are actually sick. This gives P(A|B) = 1/6 = 16.1%.
Key Takeaways
A second intelligent agent transforms optimization into strategic reasoning — you must anticipate the opponent's response to every move you make.
In a zero-sum game, gains and losses always sum to zero (the "fixed pie"). Payoff matrices make all possible outcomes visible and analyzable.
A Nash equilibrium is a stable state where no player can improve by unilaterally changing strategy — but stability does not guarantee optimality (the Prisoner's Dilemma proves it).
Check Your Understanding
Explain the key difference between a single-agent pathfinding problem and an adversarial two-player game from the perspective of the search algorithm.
Construct a simple 2×2 payoff matrix for a zero-sum game of your choice and verify that each cell's payoffs sum to zero.
The Prisoner's Dilemma shows that the Nash equilibrium is not the best collective outcome. Why can't the two prisoners simply agree to cooperate?
Quiz: Game Theory
Question 1 / 4
Not completed
A robot navigates a warehouse alone, avoiding static obstacles. A second robot is introduced that competes for the same pickup locations. What fundamentally changes about the first robot's planning problem?
1. A robot navigates a warehouse alone, avoiding static obstacles. A second robot is introduced that competes for the same pickup locations. What fundamentally changes about the first robot's planning problem?
☐ A) The warehouse gets physically larger
☐ B) The robot must now anticipate an intelligent adversary's moves, not just navigate static obstacles
☐ C) The robot needs more battery power
☐ D) The obstacles start moving randomly
2. Two street vendors sell identical ice cream on a beach. Vendor A's profit is always the negative of Vendor B's profit (all customers choose one vendor). Is this a zero-sum game?
☐ A) No — both vendors could raise prices together
☐ B) Yes — one vendor's gain is exactly the other's loss
☐ C) No — the total number of ice cream buyers can change
☐ D) Yes — because they sell the same product
3. In the Prisoner's Dilemma, both players choosing "Defect" is the Nash equilibrium. Why is this outcome paradoxical?
☐ A) Because Defect is not a valid strategy
☐ B) Because both players would be better off if they both chose Cooperate, but neither can trust the other to do so
☐ C) Because it results in both players going free
☐ D) Because Nash equilibria only exist in zero-sum games
4. In Rock-Paper-Scissors, Player A plays Rock 50% of the time, Paper 25%, Scissors 25%. How should Player B respond?
☐ A) Play each option with equal probability (33.3% each)
☐ B) Play Paper more often to exploit Player A's Rock bias
☐ C) Always play Rock to match Player A
☐ D) Play randomly — the strategy doesn't matter in RPS