Game

Introduction to Game Theory
4. Game Tree Search

Dana Nau
University of Maryland

Nau: Game Theory

1

Finite perfect-information zero-sum games
Finite: finitely many agents, actions, states
Perfect information: every agent knows the current state, all of the actions, and what they do
No simultaneous actions – agents move one-at-a-time
Constant-sum: regardless of how the game ends, Σ{agents’ utilities} = k .
For every such game, there’s an equivalent game in which (k = 0).
Thus constant-sum games usually are called zero-sum games
Examples:
Deterministic: chess, checkers, go, othello (reversi), connect-four, qubic, mancala (awari, kalah), 9 men’s morris (merelles, morels, mill)
Stochastic: backgammon, monopoly, yahtzee, parcheesi, roulette, craps
For now, we’ll consider just the deterministic games
Nau: Game Theory

2

Outline
♦ A brief history of work on this topic
♦ The minimax theorem
♦ Game trees
♦ The minimax algorithm
♦ α-β pruning
♦ Resource limits and approximate evaluation
♦ Games of chance (briefly)

Nau: Game Theory

3

A brief history
1846 (Babbage): machine to play tic-tac-toe
1928 (von Neumann): minimax theorem
1944 (von Neumann & Morgenstern): backward-induction algorithm
(produces perfect play)
1950 (Shannon): minimax algorithm (finite horizon, approximate evaluation) 1951 (Turing): program (on paper) for playing chess
1952–7 (Samuel): checkers program, capable of beating its creator
1956 (McCarthy): pruning to allow deeper search
1957 (Bernstein): first complete chess program, on an IBM 704 vacuumtube computer, could examine about 350 positions/minute

Nau: Game Theory

4

A brief history, continued
1967 (Greenblatt): first program to compete in human chess tournaments:
3 wins, 3 draws, 12 losses
1992 (Schaeffer): Chinook won the 1992 US Open checkers tournament
1994 (Schaeffer): Chinook became world checkers champion;
Tinsley (human champion) withdrew for health reasons
1997 (Hsu et al):