# Game

Disponível somente no TrabalhosFeitos
• Páginas : 15 (3650 palavras )
• Publicado : 13 de março de 2013

Amostra do texto
Introduction to Game Theory
4. Game Tree Search

Dana Nau
University of Maryland

Nau: Game Theory

1

Finite perfect-information zero-sum games
Finite: ﬁnitely 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’llconsider 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 (brieﬂy)

Nau: Game Theory

3

A brief history
1846 (Babbage): machine to play tic-tac-toe
1928 (von Neumann): minimax theorem
1944 (vonNeumann & Morgenstern): backward-induction algorithm
(produces perfect play)
1950 (Shannon): minimax algorithm (ﬁnite 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): ﬁrst complete chess program, on an IBM 704 vacuumtubecomputer, could examine about 350 positions/minute

Nau: Game Theory

4

A brief history, continued
1967 (Greenblatt): ﬁrst 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):Deep Blue won 6-game chess match against
world chess champion Gary Kasparov
2007 (Schaeffer et al, 2007): Checkers solved: with perfect play,
it’s a draw. This took 1014 calculations over 18 years

Nau: Game Theory

5

Quick review
Recall that
♦ A strategy tells what an agent will do in every possible situation
♦ Strategies may be pure (deterministic) or mixed (probabilistic)
Supposeagents 1 and 2 use strategies s and t to play a two-person zero-sum
game G. Then
• Agent 1’s expected utility is u1(s, t)
From now on, we’ll just call this u(s, t)
• Since G is zero-sum, u2(s, t) = −u(s, t)
We’ll call agent 1 Max, and agent 2 Min
Max wants to maximize u and Min wants to minimize it

Nau: Game Theory

6

The Minimax Theorem (von Neumann, 1928)
♦ A restatement of theMinimax Theorem
that refers directly to the agents’ minimax strategies:
Theorem. Let G be a two-person ﬁnite zero-sum game. Then there are
strategies s∗ and t∗, and a number u∗, called G’s minimax value, such that
• If Min uses t∗, Max’s expected utility is ≤ u∗, i.e., maxs u(s, t∗) = u∗
• If Max uses s∗, Max’s expected utility is ≥ u∗, i.e., mint u(s∗, t) = u∗
Corollary 1: u(s∗, t∗) = u∗.Corollary 2: If G is a perfect-information game,
then there are pure strategies s∗ and t∗ that satisfy the theorem.

Nau: Game Theory

7

Game trees
MAX (X)

X

X

X

MIN (O)

X

X

X
X

XO

X

O

MAX (X)

XOX
MIN (O)

...

TERMINAL
Utility

XO
X

...

X
O

...

X

...

XO
X

X

Root node = the initial state

...

XOX
OX
O

XOXOOX
XXO

XOX
X
XOO

−1

0

Children of a node = the states an
agent can move to

...

...

Terminal node = a state where the
game ends

+1

Nau: Game Theory

8

Strategies on game trees
MAX (X)

X

X

X

MIN (O)

X

X

X
X

XO

X

XOX

XO
X

O

MAX (X)

MIN (O)

...

...

X
O

...

XO
X

...

...

...

X

X

To...