Chapter 7: Game Playing and Adversarial Search

7.1 Adversarial Search Basics

Games with perfect information where players alternate moves:

• Initial state
• Players (MAX and MIN)
• Actions/legal moves
• Terminal test
• Utility function (win/lose/draw values)

7.2 Minimax Algorithm

Optimal strategy for deterministic, perfect-information games:

1. MAX player chooses move to maximize utility
2. MIN player chooses move to minimize utility
3. Alternate recursively until terminal state

Time complexity: O(b^d)

7.3 Alpha-Beta Pruning

Optimization of minimax that eliminates unnecessary branches:

• α = best value MAX can guarantee
• β = best value MIN can guarantee
• Prune when α ≥ β

Can reduce time complexity to O(b^d/2)

7.4 Evaluation Functions

Heuristics to estimate utility of non-terminal states:

• Chess: Material value, piece mobility, king safety
• Checkers: Piece count, king count, board control
• Should correlate with actual winning chances

7.5 Frequently Asked Exam Questions

1. Explain minimax with a game tree example.
2. How does alpha-beta pruning improve minimax?
3. Design an evaluation function for tic-tac-toe.
4. Compare perfect vs imperfect information games.
5. Why is minimax unsuitable for games like poker?