So far, weโve looked at search problems where the environment simply follows the rulesโthereโs no opponent actively working against you. But what happens when your AI has to face an adversary? This is the domain of adversarial search, and itโs the foundation of game-playing AI.
In adversarial search, the AI agent faces an opponent with opposing goals. The AI must account for the actions of an adversary who is trying to win. This is the kind of search used in game-playing AI, where the AI must plan its moves while assuming the opponent will do everything possible to defeat it.
Imagine playing chess against a friend whoโs just as good as you. Before making a move, you think not just about what the board looks like now, but what your opponent could do in response, and what you could do after that, and so on. You choose the move that gives you the best result assuming your opponent will make the strongest possible counter-move. Thatโs adversarial search in a nutshell!
The fundamental algorithm for adversarial search is Minimax. In games with two players, the AI evaluates all possible moves to guarantee optimal play. The algorithm assumes that both players play optimally: one player tries to maximize the outcome, while the other tries to minimize it.
Think of it like playing chess against a friend whoโs just as good as you. Before making a move, you consider not just what the board looks like now, but what your opponent could do in response, and what you could do after that, and so on. You choose the move that gives you the best result assuming your opponent will make the strongest possible counter-move.
This allows the AI to look ahead and choose moves that lead to winning positions while assuming the opponent will choose the move that is worst for the AI.
The challenge in adversarial search is the size of the state space. For example, chess has an incredibly large state space, making it impossible to explore completely. Games like Tic-Tac-Toe, however, have a small enough state space to explore in its entirety.
Letโs revisit Tic-Tac-Toe from Sectionย 3.2. Using the minimax algorithm, the AI can examine all possible moves, evaluate each board position, and choose the move that maximizes its chances of winningโeven against an optimal opponent. Because Tic-Tac-Toe has a relatively small state space, the AI can search the entire game tree and play perfectly.
Key insight: With Tic-Tac-Toe, there are only 9 possible first moves, then 8 possible responses, then 7, and so on. The total number of possible games is about 255,168โsmall enough for a computer to examine all of them.
For larger games, the naive Minimax algorithm is too slow. Alpha-Beta Pruning is an optimization that dramatically speeds up Minimax by ignoring branches that cannot possibly affect the final decision.
Imagine youโre looking for the best route to a destination. Youโve already found a route that takes 3 hours. While exploring another route, you realize itโs already taken 3 hours and youโre still far from the destination. You can stop exploring that route immediatelyโitโs already worse than what youโve found!
Result: Alpha-beta pruning can reduce the search time by about half in the best case. This makes it possible to search twice as deep in the same amount of time!
Subsection3.5.4Why Larger Games Still Need Heuristics
Even with alpha-beta pruning, games like chess (โ10^47 states) remain too large to search completely. This is why game-playing AI systems also use heuristics to evaluate board positions without searching all the way to the end.
Instead of searching all the way to a win or loss, the AI searches to a limited depth and then uses an evaluation function to estimate how favorable the current position is. For example, a chess AI might evaluate a position by:
A good chess player doesnโt need to see every possible move until checkmate. Instead, they evaluate a position using their experience and knowledge: "My pieces are well-developed, I control the center, and my king is safe." An AI evaluation function does the same thingโit uses a heuristic to estimate how good a position is without exploring every possible future move.
This is how systems like Deep Blue (the chess AI that beat world champion Garry Kasparov) and AlphaGo (the Go AI that beat world champion Lee Sedol) achieved world-class performanceโthey combined deep search with sophisticated evaluation heuristics.
Adversarial search is everywhereโfrom the chess AI on your phone to the NPC enemies in your favorite video game. The key insight is that when you face an opponent, you need to plan not just for what you want to do, but for what your opponent will do in response. Minimax and alpha-beta pruning give AI systems the ability to think several steps ahead, anticipating and countering an opponentโs best moves.
