5.1 Game Theory
Game theory studies strategic interaction. A game model specifies players, states, legal actions, transitions, and payoffs; outcomes may be cooperative or competitive.
Problem-solving · Chapter 5
Adversarial Search and Games
In competitive settings, an agent must choose while accounting for opponents’ responses. Game search makes those contingencies explicit.
Chapter guide
5.2 Optimal Decisions in Games
Minimax chooses a move maximizing a player's guaranteed utility against an optimal opponent. In two-player zero-sum games, one player's gain is the other's loss.
5.3 Heuristic Alpha–Beta Tree Search
Alpha–beta pruning avoids branches that cannot change the minimax decision. Depth limits and evaluation functions approximate distant outcomes.
5.4 Monte Carlo Tree Search
MCTS grows a search tree through selection, expansion, simulation, and backup, using sampled outcomes to allocate computation.
5.5 Stochastic Games
Chance nodes model random events such as dice. Expectiminimax combines max, min, and probability-weighted expected values.
5.6 Partially Observable Games
When players cannot see the full state, they reason over beliefs and may need to infer opponents’ private information.
5.7 Limitations of Game Search Algorithms
Large branching factors, imperfect models, hidden information, and limited computation constrain search; evaluation and opponent assumptions matter.
Key terms and minimax trace
Utility: numerical outcome from a player’s perspective. Minimax: choose the move with the best value assuming the opponent also chooses optimally. Evaluation function: estimates a position when search cannot reach a terminal outcome. Alpha–beta pruning can skip branches while preserving minimax’s answer; this demo uses plain, unpruned minimax.
The recursive rule is: at an O turn take the maximum child score; at an X turn take the minimum; a win/loss/draw ends the recursion. Scores ±(10 − depth) prefer faster wins and slower losses. Ties follow the first available cell in row-major order. With perfect play, this correctly modeled tic-tac-toe ends in a draw.
Interactive lab
Play Tic-tac-toe vs. minimax
You are X; the computer is O. The computer searches the remaining game tree to choose an optimal move. Try to win, draw, or see why minimax blocks a threat.
Your turn: choose a square.
Perfect play in this small, deterministic, zero-sum game guarantees at least a draw for each side.
Time and memory
Given current board B, with game-tree branching factor b and maximum remaining depth d, plain minimax takes O(bᵈ) time in the worst case; recursion uses O(d) auxiliary space. The mutable m-cell board is input/state memory O(m) (m=9 here), and the fixed DOM board is O(1) UI memory. At most 9 cells remain (d ≤ 9, b ≤ 9), so each move evaluates only the finite tic-tac-toe tree; no transposition table is stored. These bounds assume deterministic, alternating, perfect-information play and a constant-time terminal test (true for this fixed eight-line board).