AIMA Chapter 5 — Adversarial Search and Games.

Games are one of AI’s favorite laboratories because they are clean. There are rules. There are turns. There is winning and losing. There are strong human benchmarks. And yet games are brutally hard because intelligence is now adversarial: every move you make changes what the other player can do, and every move they make is chosen specifically to hurt you. Chapter 5 is about that transition from search in a passive world to search against an opponent.

01 Why games are such a classic AI playground

Game playing was attractive to AI researchers from the beginning because games are structured battles of decision making. They are rich enough to be nontrivial but clean enough to formalise. A move is legal or illegal. A state is winning, losing, drawn, or uncertain. The environment is often discrete and symbolic, which makes it easier to model than the messy physical world.

That makes games excellent for testing ideas about reasoning. If you build an algorithm that can search ahead, evaluate alternatives, and choose rationally under opposition, you have captured something central about intelligent decision making. This is why chess, checkers, Go, tic-tac-toe, and later real-time games became recurring milestones in AI history.

Games also give a clear scoreboard. In many real-world tasks, “better” is fuzzy. In games, better is usually not fuzzy at all. You win, lose, or draw. That crisp feedback makes algorithms easier to compare and improve.

But the chapter is not about all games equally. Before minimax makes sense, we have to narrow the class of games we are talking about.

02 What makes game search different from ordinary search

In regular path-finding search, the world does not fight back. When you choose an action, the successor state depends on the rules of the environment, not on an enemy actively choosing the worst possible reply. The search problem is, in a sense, one-sided.

In adversarial games, the world includes another intelligent agent. If you examine a move and think, “Great, after this I can win,” you are missing half the picture. The opponent also gets a move, and they are not required to cooperate with your plan. So you cannot evaluate a move by its best possible continuation for you. You must evaluate it by the continuation that a hostile rational opponent would force.

This is why a simple fixed plan is insufficient. In path search you can say, “Take left, then right, then go straight.” In a game you need a strategy: a rule for what to do in every possible situation that might arise after the opponent responds. The future is branching not just because of your options but because of theirs.

That is the conceptual jump from Chapter 3 and 4 into Chapter 5. Search is still present, but the tree now alternates between choices you control and choices you do not.

03 Game categories and what this chapter actually covers

Not all games are alike. A good first classification uses several axes.

This chapter focuses on the cleanest subclass: deterministic, perfect-information, zero-sum, two-player games. That includes classics like chess, Go, and tic-tac-toe. “Perfect information” means both players fully observe the current state. “Deterministic” means the next state is determined by the current state and chosen action, not by dice or hidden randomness. “Zero-sum” means what MAX gains, MIN loses.

Why this restriction? Because minimax logic is cleanest there. Once you add chance, hidden information, or more than two agents, the reasoning changes. Those extensions are important, but Chapter 5 starts with the pure version so that the core ideas are crystal clear.

04 Formal game definition: the six parts you should know cold

AIMA gives a formal game definition using six components. This is the game analogue of a search problem definition.

1. S0 — the initial state.
2. PLAYER(s) — whose turn it is in state s.
3. ACTIONS(s) — the legal moves available in state s.
4. RESULT(s,a) — the successor state that results from applying action a in state s.
5. TERMINAL-TEST(s) — whether the game is over in state s.
6. UTILITY(s,p) — the final payoff for player p when the game ends in state s.

That last component is especially important. Utility converts a terminal position into a number. In a simple zero-sum game we may use +1 for a win, 0 for a draw, and -1 for a loss from MAX’s perspective. In richer games we can use larger scales if needed, but the key is that utility defines what “good” means.

Once you have these six parts, every deterministic perfect-information game fits the same formal template. That is why one algorithmic family can apply to tic-tac-toe and chess even though the games feel utterly different in complexity.

05 Game trees, MAX and MIN levels, and why strategy beats a fixed plan

The game tree starts at the initial state and alternates between players. Levels where MAX moves are called MAX nodes. Levels where MIN moves are called MIN nodes. Leaves are terminal positions labeled with utilities.

If the tree were tiny, the problem would be easy: just look all the way to the leaves, compute the best outcome assuming both players are rational, and choose the corresponding action at the root. That is exactly the minimax idea. The difficulty is that real game trees are enormous.

Chess is often estimated to have around 10^40 reachable states and an astronomically large game tree. Go is even wilder, often quoted around 10^170 states or game histories depending on the counting convention. The exact number matters less than the moral: you cannot enumerate the whole game tree except for trivial games.

Still, strategy matters more than plan. If you say, “I will play move A, then B, then C,” you have ignored the possibility that the opponent blocks your idea after move A. A true strategy is a complete mapping from every possible reachable state to the move you would play there. In other words, a strategy tells you what to do no matter how the opponent responds.

06 Minimax: maximise the minimum you can guarantee

Now the heart of the chapter. MAX wants high utility. MIN wants low utility. If both are perfectly rational and know the game, how should MAX move?

The answer is minimax. MAX chooses the action whose worst-case outcome is best. That sounds abstract until you hear it in plain English: “Assume the opponent will reply in the most painful possible way. Which move still leaves me in the best guaranteed position?”

This is why the name minimax makes sense. MIN tries to minimise utility for MAX. Knowing that, MAX chooses the action that maximises the value after MIN has minimised it.

The minimax value of a state is defined recursively. For terminal states, it is just the utility. For MAX states, it is the maximum minimax value among successors. For MIN states, it is the minimum minimax value among successors.

This recursive definition is so important that it is worth reading slowly. At a MAX node, you ask “what is the best future value I can secure?” At a MIN node, you ask “what is the smallest value the opponent can force on me?” That alternation backs values up from leaves to root.

07 A full worked minimax example

Let us build a small four-ply example. Suppose the root is a MAX node with three actions leading to MIN nodes A, B, and C.

• A has terminal children with utilities 3, 12, and 8.
• B has terminal children with utilities 2, 4, and 6.
• C has terminal children with utilities 14, 5, and 2.

Because A, B, and C are MIN nodes, each one chooses the smallest utility among its children:

• Value(A) = min(3, 12, 8) = 3
• Value(B) = min(2, 4, 6) = 2
• Value(C) = min(14, 5, 2) = 2

Now the root is a MAX node, so it chooses the largest among these backed-up values:

So MAX chooses action A. Why not the branch containing the leaf 14? Because MIN would never allow MAX to receive 14 there. At node C, MIN would steer the game to the child with utility 2. Minimax is about what the opponent can force, not what you hope they will accidentally permit.

The algorithm itself is just a depth-first search over the game tree that backs up values on the way up. If the branching factor is b and the search depth is m, the time complexity is O(b^m) because in the worst case the whole tree is explored. Space with depth-first traversal is about O(bm).

Minimax is optimal under the assumption that the opponent also plays optimally. If the opponent makes mistakes, that only helps MAX. The algorithm is conservative in exactly the right sense.

08 Why full minimax is impossible in real games

For tiny games like tic-tac-toe, full minimax is feasible. You can search the whole tree to terminal positions and play perfectly. That is why tic-tac-toe is solved and always ends in a draw with optimal play.

But in chess or Go, terminal search is hopeless except in tiny endgames. The depth is too large, and the branching factor is too large. Even if you could search millions of nodes per second, the combinatorial explosion destroys you.

So practical game-playing systems almost never run pure terminal-state minimax except in small subtrees. They run depth-limited minimax: search only down to depth d, then estimate the value of the frontier positions instead of reaching true game outcomes.

This is the same philosophical move we saw in heuristic path search. When exact future knowledge is impossible, we substitute a cheap estimate and hope it is informative enough.

09 Depth-limited minimax, cutoff tests, and evaluation functions

Depth-limited minimax adds two new ingredients:

• CUTOFF-TEST(s, depth): should we stop expanding here?
• EVAL(s): if we stop here and the state is non-terminal, what utility estimate should we use?

The cutoff test is usually true when we reach a depth limit d or encounter a terminal state earlier. The evaluation function is then used to assign a numerical value to that non-terminal frontier node.

This is an extremely important practical idea. Because real game trees are too deep, the quality of the evaluation function often matters as much as, or more than, small improvements in raw search depth.

Simple evaluation

In chess, a primitive evaluation might be material difference:

If MAX is up a rook and a pawn, the score should be positive. If MAX is down a queen, the score should be strongly negative.

Weighted feature evaluation

A more realistic evaluation is a weighted sum of features: material, king safety, mobility, center control, pawn structure, piece activity, and so on. For example, rooks may be worth 5, bishops 3, knights 3, pawns 1, queens 9, with extra feature bonuses and penalties layered on top.

The point is not that any one feature is perfect. The point is that the evaluation function compresses long-term strategic knowledge into a number the search can use quickly.

For example, a chess engine may delay losing a queen by one move so that the actual capture lies beyond depth d. The evaluation at the cutoff looks acceptable, but only because the disaster is just offstage. This is why stronger engines often combine depth limits with selective extensions such as quiescence search.

There is a classic practical trade-off here: a mediocre evaluation with deeper search versus a brilliant evaluation with shallow search. In many real systems, a stronger evaluation wins at moderate search depths because it makes every backed-up leaf value more meaningful.

10 Alpha-beta pruning: same minimax answer, less pointless work

Minimax wastes effort because it evaluates many branches that cannot possibly affect the final decision. Alpha-beta pruning fixes that without changing the answer.

The idea introduces two bounds:

• alpha: the best value MAX has found so far along the current path. Start with negative infinity.
• beta: the best value MIN has found so far along the current path. Start with positive infinity.

At a MAX node, values can only go up as MAX considers children. At a MIN node, values can only go down as MIN considers children. If you ever discover that a node cannot improve the decision already guaranteed elsewhere, you stop exploring its remaining children.

The standard pruning rules are:

• At a MIN node, if the current value becomes less than or equal to alpha, prune the rest. MAX would never allow the game to enter a branch that bad when it already has a better option elsewhere.
• At a MAX node, if the current value becomes greater than or equal to beta, prune the rest. MIN would never choose a path that generous to MAX when MIN already has a better defense elsewhere.

The compact cutoff condition is beta \le alpha. Once that inequality holds, the remaining children of the node cannot matter.

11 A worked alpha-beta trace, step by step

Consider a root MAX node with three MIN children: A, B, C. Each MIN node has three MAX children, and each of those eventually leads to terminal utilities. We traverse left to right. The exact numbers are chosen to show pruning.

Branch A: Suppose MIN node A has children whose backed-up MAX values turn out to be 3, 5, and 6. Since A is a MIN node, its final value is 3. At the root, MAX now has alpha = 3.

Branch B: At MIN node B, we explore the first child and discover its MAX value is 2. Since B is MIN, its current best is now 2, so beta = 2 at node B. But the root already has alpha = 3 from branch A. Because beta = 2 is less than or equal to alpha = 3, the rest of B can be pruned. MAX would never choose B anyway, because MIN can force B down to at most 2, which is already worse than the guaranteed 3 from A.

Branch C: Suppose the first explored child gives 14, so at C the current MIN bound is 14 and no pruning happens yet. The second child gives 5, lowering C’s current value to 5. Still no cutoff because 5 is greater than root alpha 3. The third child gives 2, so C’s value becomes 2. At that moment, if more children remained, they would be pruned because 2 is less than or equal to 3.

So the root still chooses A with value 3, exactly as plain minimax would. The difference is that large portions of B and maybe C were skipped because they could not change the answer.

You can now see why alpha-beta feels like “thinking smartly” rather than “thinking less.” It uses partial knowledge of what is already achievable to stop analyzing branches whose final verdict is predetermined.

12 Complexity of alpha-beta and why move ordering is everything

In the worst ordering, alpha-beta prunes almost nothing, so the time is still about O(b^d). But in the best case, with perfect move ordering, the effective complexity becomes roughly O(b^{d/2}). That is an enormous win: it is like doubling the search depth for the same amount of work.

With random ordering, a common rough rule of thumb is around O(b^{3d/4}). The exact constants depend on the tree, but the message is clear: ordering the promising moves first is not a small optimisation. It is the optimization.

That is why engines use move-ordering heuristics such as killer moves—moves that caused cutoffs in similar positions before. Another common trick is iterative deepening: search to depth 1, then 2, then 3, and so on. This sounds wasteful, but the shallower searches identify promising moves that can be tried first at deeper levels, dramatically improving alpha-beta pruning.

Transposition tables also help move ordering. If a state has been seen before, the previously good move can be tried first. In game search, such implementation details are often the difference between a toy engine and a dangerous one.

13 Transposition tables, quiescence search, opening books, endgame tables

Once you accept that full-tree search is impossible, you start collecting every trick that avoids wasting search effort.

Transposition tables

A transposition happens when the same board position is reached through different move orders. Chess is full of them. A transposition table caches a mapping from state to evaluated value and often also stores depth, bound type, and best move. If the same position appears again, the engine reuses work instead of recomputing it.

Quiescence search

To fight the horizon effect, engines often extend search in tactically unstable positions. If captures, checks, or other forcing moves are available, the engine keeps searching until the position becomes quieter. That is quiescence search: do not trust an evaluation on a noisy tactical frontier.

Opening books and endgame tables

Opening books store strong moves for the early phase, often learned from expert play or computed analysis. Endgame tablebases store exact outcomes for small numbers of pieces, turning late-game positions into solved lookup problems. Together, they let engines avoid spending search time on regions that are already well understood.

This engineering stack is the background for famous systems like Deep Blue. Its 1997 victory over Kasparov was not “just brute force” in the dismissive sense. It was heuristic minimax, alpha-beta pruning, strong evaluation, heavy move ordering, and hardware acceleration working together at scale.

14 Heuristic minimax in the real world

When people say a classical game engine uses minimax, what they usually mean is a package of techniques: depth-limited search, evaluation functions, alpha-beta pruning, iterative deepening, transposition tables, quiescence search, and lots of move-ordering tricks.

That is why the phrase heuristic minimax is useful. The engine is still solving a minimax problem, but only approximately because it cannot see the full game to the end. The intelligence lies in how it estimates and prioritizes.

A mediocre evaluation and sloppy move ordering can make deep search feel blind. A strong evaluation and sharp ordering can make a moderate depth terrifying. In practice, the strongest engines marry both: search power and positional understanding.

One memorable line from this chapter is that alpha-beta makes the best use of a minimax tree. That is the right summary. Minimax defines the ideal decision criterion. Alpha-beta makes that criterion computationally survivable.

15 Why Monte Carlo Tree Search became such a big deal

For chess, strong hand-crafted evaluation functions were possible because the game has crisp local features: piece values, king safety, pawn structure, mobility, and so on. Go is much harder. The board is huge, the branching factor is massive, and local tactical value is difficult to reduce to a simple weighted feature list.

This is where Monte Carlo Tree Search, or MCTS, changed the story. Instead of relying entirely on a carefully designed static evaluation function, MCTS asks a different question: “From this position, if I keep playing games out, how often do I win?”

In its simplest form, MCTS evaluates a position by repeated simulated games, called rollouts or playouts. If a move leads to many wins across simulations, that move looks promising. The method is statistical rather than purely deductive.

This was especially attractive for Go because writing a strong handcrafted evaluation was notoriously difficult. MCTS let engines get surprisingly strong by using search plus sampling rather than search plus rigid evaluation formulas alone.

16 The four phases of MCTS

MCTS repeats four phases over and over.

1. Selection: starting at the root, repeatedly choose a child according to a tree policy until you reach a node with unexplored children or a terminal state.
2. Expansion: if the node is non-terminal and has unexplored legal moves, add one new child for one such move.
3. Simulation (rollout): from the new child, play a simulated game to the end, often using random or lightly biased moves.
4. Backpropagation: propagate the simulation result back up the path, updating visit counts and win statistics.

Notice what is elegant here: the tree grows asymmetrically. It does not expand all branches to equal depth. It spends most effort on branches that statistical evidence suggests are promising, while still occasionally exploring uncertain ones.

17 UCB1: the exploration-exploitation balancing act

The core selection rule in standard MCTS is often UCB1, which scores child i by

Here:

• w_i = number of wins or total reward observed through child i
• n_i = number of visits to child i
• N = total visits to the parent
• c = exploration constant, often around \sqrt{2}

The first term, w_i/n_i, is exploitation. It prefers moves that have done well before. The second term, c\sqrt{\ln N / n_i}, is exploration. It boosts under-visited children so they are not ignored forever.

This formula is a compact expression of a deep dilemma in AI. If you only exploit, you may lock onto a move that looks good from limited evidence while missing an even better option. If you only explore, you waste time rechecking everything instead of cashing in on what you already know. UCB1 balances both.

As visits grow, the exploration bonus for heavily visited nodes shrinks. So the algorithm naturally shifts from broad curiosity early on to sharper preference later on.

18 Does MCTS actually converge to the right answer?

In theory, yes. Given enough rollouts and a suitable selection policy, MCTS converges to the minimax-optimal decision. The issue is not correctness in the limit; the issue is what happens with finite compute. In practice we care about the quality of the move after thousands or millions of simulations, not after infinite time.

That is why rollout policy quality matters, selection balance matters, and domain knowledge matters. Crude random rollouts can still work surprisingly well, but stronger systems bias the simulations or replace them with learned value estimates. Every improvement tries to make finite-time behavior better.

MCTS is therefore not “anti-minimax.” It is another route toward good game decisions, especially useful where branch factors are huge and evaluation is difficult. In the infinite-data limit it approaches rational choice; in the finite-data regime it is an engineering art.

19 AlphaGo and AlphaZero: when deep learning meets search

AlphaGo’s 2016 win over Lee Sedol was historically important because it showed that Go, long considered resistant to classical evaluation-function methods, could be conquered by combining MCTS with deep neural networks.

Two neural ideas were central:

• Policy network: suggest promising moves, guiding selection and expansion so the search does not waste effort uniformly.
• Value network: estimate the probability of winning from a position, reducing the need for long random rollouts.

MCTS remained the search backbone, but the networks made that backbone far more informed. Instead of exploring blindly or relying on random playouts alone, AlphaGo used learned intuition plus search.

AlphaZero pushed the idea further. No human opening books, no handcrafted domain strategy tables in the old sense—just self-play, neural networks, and search. It learned superhuman play in chess, Go, and shogi by repeatedly playing against itself and refining policy and value estimates.

20 A quick comparison table you can revise from

Students often remember isolated formulas but forget when each idea is the natural choice. This table is meant to fix that by lining up the chapter’s tools in one glance.

Method	What it assumes	What it uses	Why it is good	What can go wrong
Full minimax	Terminal search is feasible	Exact utilities	Provably optimal against perfect play	Explodes in large games
Depth-limited minimax	Cutoff is necessary	Evaluation function	Works in big trees	Depends heavily on eval quality
Alpha-beta	Same as minimax	Bounds alpha and beta	Same answer with fewer nodes	Poor ordering kills pruning
Heuristic minimax engine	Real-time practical play	Eval + ordering + cache	Very strong in structured games	Horizon effect and engineering complexity
MCTS	Sampling is informative	Rollouts + visit stats	Great when evaluation is hard	Noisy if simulations are weak

21 Minimax vs alpha-beta vs MCTS: when each mental model wins

It helps to compare the methods instead of treating them as unrelated historical chapters.

Alpha-beta is strongest when you can order moves well and write a meaningful evaluation function. MCTS shines when handcrafted evaluation is weak but simulation is informative. Modern deep systems blur the line by letting learned models serve as evaluation and move-ordering tools inside search.

So the real lesson is not “alpha-beta good, MCTS new.” The real lesson is that adversarial search is a toolkit, and the best tool depends on what kind of structure the game gives you.

22 Common mistakes students make in this chapter

If you keep those mistakes in mind, the chapter becomes much easier to reason about in exams and implementations alike.

23 What Chapter 5 is really teaching

At the surface level, Chapter 5 teaches minimax, alpha-beta, and MCTS. At the deeper level, it teaches something broader: rational decision making under opposition requires thinking in contingencies, not just direct actions.

You are no longer searching for a route in a passive world. You are searching for a move under the assumption that someone else is searching too. That symmetry is what makes game AI conceptually beautiful. Every node in the tree is a prediction about another intelligence responding to yours.

And once the trees become too large, the chapter teaches a second lesson: exact rationality is often computationally impossible, so intelligence becomes a matter of smart approximation. Cutoffs, evaluation functions, pruning, caching, rollouts, and learned priors are all ways of keeping the spirit of rational play while surviving the size of real search spaces.

• Games differ from ordinary search because an opponent acts between your moves and actively tries to lower your outcome.
• The core setting in this chapter is deterministic, perfect-information, zero-sum, two-player games.
• A full strategy maps every reachable state to an action; it is not just one fixed line of play.
• Minimax backs up utilities assuming MAX maximises and MIN minimises.
• Depth-limited minimax needs a cutoff test and an evaluation function because real game trees are too large.
• Alpha-beta returns the same answer as minimax while pruning branches that cannot affect the decision.
• Move ordering is the lifeblood of alpha-beta efficiency.
• Transposition tables, quiescence search, opening books, and endgame tables are practical power-ups around heuristic minimax.
• MCTS uses repeated simulation plus UCB1 to balance exploration and exploitation.
• AlphaGo and AlphaZero showed that the strongest game AI often comes from combining search with learned guidance.

24 References and extra reads

If you want to go beyond exam prep, this chapter has a beautiful reading path. Start with the textbook, then jump to classic engine ideas, then to the modern neural era.

• Russell, Norvig. Artificial Intelligence: A Modern Approach, 4th ed. Chapter 5 for the formal minimax and alpha-beta foundation.
• Knuth and Moore. Classic analysis of alpha-beta pruning, especially useful for understanding why move ordering changes everything.
• Game-engine programming notes. Read practical writeups on transposition tables, iterative deepening, and quiescence search to see how real engines package the theory.
• Browne et al. Survey paper on Monte Carlo Tree Search, a strong bridge from textbook understanding to research-level depth.
• Silver et al. AlphaGo and AlphaZero papers for the modern story of neural guidance plus search.

25 Chapter 5 cheatsheet

26 Quick FAQ before you move on

Why is minimax called “maximise the minimum”?

Because MAX assumes MIN will choose the reply that minimises MAX’s utility. So MAX selects the move whose resulting minimum outcome is as large as possible.

Does alpha-beta ever change the move minimax would choose?

No. When implemented correctly, alpha-beta returns exactly the same decision and value as minimax. It only skips branches proven irrelevant.

Why not always use MCTS instead of alpha-beta?

Because alpha-beta is incredibly strong when evaluation functions are meaningful and move ordering is good. MCTS shines in different regimes, especially where handcrafted evaluation is hard and simulation is informative.

What is the practical meaning of the exploration constant c in UCB1?

It controls how adventurous the search is. Larger c means more curiosity about under-visited moves; smaller c means more trust in moves that already have high win rates.