CSC384: Intro To Artificial Intelligence Game Tree Search II Midterm: Everything Covered So Far Plus This Lecture Slides

CSC384: Intro to Artificial Intelligence
Game Tree Search II

Midterm: Everything covered so far
plus this lecture slides.
Hojjat Ghaderi [Courtesy of Fahiem Bacchus], University of Toronto, Fall 2006
Depth-first Implementation of
MinMax
utility(N,U) :- terminal(N), utility(N,U).

utility(N,U) :- maxMove(N), children(N,CList),
utilityList(CList,UList),
max(UList,U).
utility(N,U) :- minMove(N), children(N,CList),
utilityList(CList,UList),
min(UList,U).
Depth-first evaluation of game tree

terminal(N) holds if the state (node) is a terminal
node. Similarly for maxMove(N) (Max players move)
and minMove(N) (Min players move).
utility of terminals is specified as part of the input
Depth-first Implementation of
MinMax
utilityList([],[]).
utilityList([N|R],[U|UList])
:- utility(N,U), utilityList(R,UList).
utilityList
simply computes a list of utilities, one for

each node on the list.
The way prolog executes implies that this will
compute utilities using a depth-first post-order
traversal of the game tree.
post-order (visit children before visiting parents).
Depth-first Implementation of MinMax

Notice that the game tree has to have finite
depth for this to work

Advantage of DF implementation: space
efficient
Visualization of DF-MinMax
Once s17 evald, no need to store

tree: s16 only needs its value.
Once s24 value computed, we can
evaluate s16
s0
s1
t3
s13
s2
s6
t14
t4
s7
s10
t5
t8
t9
t11
s16
s17
t15
s18
t12
t19
t20
s24
s21
t25
t22
t23
t26
Pruning
It is not necessary to examine entire tree to
make correct minimax decision

Assume depth-first generation of tree
generating value for only some of ns children

we can prove that well never reach n in a MinMax
strategy.
So we neednt generate or evaluate any further
children of n !
After
Two types of pruning (cuts):

pruning of max nodes (-cuts)
pruning of min nodes (-cuts)
Cutting Max Nodes (Alpha Cuts)

At a Max node
n:
Let be the lowest value of
ns siblings examined so far
(siblings to the left of n that have already been searched)

Let be the highest value of ns children examined so far
(changes as children examined)
s0
max node
s13
s1
s2
s6
T4
10
min node
terminal
=5 only one sibling value known
5
T3
8
s16
T5
5
=8 =10 =10
sequence of values for as s6s
children are explored
Cutting Max Nodes (Alpha Cuts)
If becomes we can stop expanding
the children of n
will never choose to move from ns parent to

n since it would choose one of ns lower valued
siblings first.
min node
Min
=8
14
12
s1
=2 4 9
s2
s3
Cutting Min Nodes (Beta Cuts)

a Min node n:
Let be the lowest value of ns children
examined so far (changes as children examined)
Let be the highest value of ns siblings
examined so far (fixed when evaluating n)
At
s0
max node
s13
s1
=10
s2
=5
s16
min node
terminal
s6
=3
Cutting Min Nodes (Beta Cuts)
If becomes we can stop expanding
the children of n.
will never choose to move from ns parent to

n since it would choose one of ns higher value
siblings first.
Max
alpha = 7
s1
n beta = 9
s2
8 3
s3
10
Alpha-Beta Algorithm
Pseudo-code that associates
a value with each node.
Strategy extracted by
moving to Max node (if you
are player Max) at each
step.
Evaluate(startNode):
/* assume Max moves first */
MaxEval(start, -infnty, +infnty)
MaxEval(node, alpha, beta):

If terminal(node), return U(n)
For each c in childlist(n)
val MinEval(c, alpha, beta)
alpha max(alpha, val)
If alpha beta, return alpha
Return alpha
MinEval(node, alpha, beta):
If terminal(node), return U(n)
For each c in childlist(n)
val MaxEval(c, alpha, beta)
beta min(beta, val)
If alpha beta, return beta
Return beta
11
Rational Opponents
This all assumes that your opponent is
rational
e.g.,
will choose moves that minimize your score
What if your opponent doesnt play
rationally?
will
it affect quality of outcome?
12
Rational Opponents
Storing your strategy is a potential issue:
you must store decisions for each node you can
reach by playing optimally
if your opponent has unique rational choices, this
is a single branch through game tree
if there are ties, opponent could choose any one
of the tied moves: must store strategy for each
subtree
What if your opponent doesnt play
rationally? Will your stored strategy still

work?
13
Practical Matters
All real games are too large to enumerate
tree
e.g.,
chess branching factor is roughly 35

Depth 10 tree: 2,700,000,000,000,000 nodes
Even alpha-beta pruning wont help here!
14
Practical Matters
We must limit depth of search tree
cant expand all the way to terminal nodes
we must make heuristic estimates about the
values of the (nonterminal) states at the leaves
of the tree
evaluation function is an often used term
evaluation functions are often learned
Depth-first expansion almost always used
for game trees because of sheer size of trees
15
Heuristics
Think of a few games and suggest some
heuristics for estimating the goodness of a

position
chess?
checkers?
your
favorite video game?

find the last parking spot?
16
Some Interesting Games

Tesauros TD-Gammon
champion backgammon player which learned
evaluation function; stochastic component (dice)
Checkers (Samuel, 1950s; Chinook 1990s
Schaeffer)
Chess (which you all know about)
Bridge, Poker, etc.
Check out Jonathan Schaeffers Web page:
www.cs.ualberta.ca/~games
theyve
studied lots of games (you can play too)

17
An Aside on Large Search Problems

Issue: inability to expand tree to terminal
nodes is relevant even in standard search

often
we cant expect A* to reach a goal by

expanding full frontier
so we often limit our lookahead, and make moves
before we actually know the true path to the goal
sometimes called online or realtime search
In this case, we use the heuristic function not
just to guide our search, but also to commits

to moves we actually make
in
general, guarantees of optimality are lost, but we

reduce computational/memory expense dramatically
18
Realtime Search Graphically

1. We run A* (or our favorite search algorithm)
until we are forced to make a move or run out
of memory. Note: no leaves are goals yet.
2. We use evaluation function f(n) to decide which
path looks best (lets say it is the red one).
3. We take the first step along the best path
(red), by actually making that move.
4. We restart search at the node we reach by
making that move. (We may actually cache the
results of the relevant part of first search
tree if its hanging around, as it would with A*).
19

CSC384: Intro To Artificial Intelligence Game Tree Search II Midterm: Everything Covered So Far Plus This Lecture Slides

Uploaded by

Copyright:

Available Formats

CSC384: Intro To Artificial Intelligence Game Tree Search II Midterm: Everything Covered So Far Plus This Lecture Slides

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

CSC384: Intro To Artificial Intelligence Game Tree Search II Midterm: Everything Covered So Far Plus This Lecture Slides

Uploaded by

Copyright:

Available Formats

CSC384: Intro to Artificial Intelligence

Game Tree Search II

plus this lecture slides.

Hojjat Ghaderi [Courtesy of Fahiem Bacchus], University of Toronto, Fall 2006

utility(N,U) :- terminal(N), utility(N,U).

Depth-first evaluation of game tree

simply computes a list of utilities, one for

Depth-first Implementation of MinMax

depth for this to work

Hojjat Ghaderi [Courtesy of Fahiem Bacchus], University of Toronto, Fall 2006

Once s17 evald, no need to store

Hojjat Ghaderi [Courtesy of Fahiem Bacchus], University of Toronto, Fall 2006

make correct minimax decision

generating value for only some of ns children

Two types of pruning (cuts):

Hojjat Ghaderi [Courtesy of Fahiem Bacchus], University of Toronto, Fall 2006

Cutting Max Nodes (Alpha Cuts)

Let be the lowest value of

ns siblings examined so far

(siblings to the left of n that have already been searched)

=5 only one sibling value known

Hojjat Ghaderi [Courtesy of Fahiem Bacchus], University of Toronto, Fall 2006

Cutting Max Nodes (Alpha Cuts)

If becomes we can stop expanding

will never choose to move from ns parent to

Hojjat Ghaderi [Courtesy of Fahiem Bacchus], University of Toronto, Fall 2006

Cutting Min Nodes (Beta Cuts)

Hojjat Ghaderi [Courtesy of Fahiem Bacchus], University of Toronto, Fall 2006

Cutting Min Nodes (Beta Cuts)

If becomes we can stop expanding

will never choose to move from ns parent to

Hojjat Ghaderi [Courtesy of Fahiem Bacchus], University of Toronto, Fall 2006

MaxEval(node, alpha, beta):

Hojjat Ghaderi [Courtesy of Fahiem Bacchus], University of Toronto, Fall 2006

will choose moves that minimize your score

What if your opponent doesnt play

it affect quality of outcome?

Hojjat Ghaderi [Courtesy of Fahiem Bacchus], University of Toronto, Fall 2006

What if your opponent doesnt play

rationally? Will your stored strategy still

chess branching factor is roughly 35

Hojjat Ghaderi [Courtesy of Fahiem Bacchus], University of Toronto, Fall 2006

for game trees because of sheer size of trees

Hojjat Ghaderi [Courtesy of Fahiem Bacchus], University of Toronto, Fall 2006

heuristics for estimating the goodness of a

favorite video game?

Hojjat Ghaderi [Courtesy of Fahiem Bacchus], University of Toronto, Fall 2006

Some Interesting Games

studied lots of games (you can play too)

An Aside on Large Search Problems

nodes is relevant even in standard search

we cant expect A* to reach a goal by

In this case, we use the heuristic function not

just to guide our search, but also to commits

general, guarantees of optimality are lost, but we

Realtime Search Graphically

Hojjat Ghaderi [Courtesy of Fahiem Bacchus], University of Toronto, Fall 2006

You might also like