HW1 Autograder is borked - fixes in progress

Keep an eye on campuswire!


A* is only optimal if the heuristic is consistent

Admissibility alone is insufficient

Consider this graph

Game Playing

Adversarial Search

How do we model the opponent?

As an aggregate economy ?

As part of a nondeterministic environment?

As explicitly adversarial agents






Perfect information

Chess in the 1960s

How do you approach game playing?

Analysis of features

If-Then Rules/Decision Trees

Brute Force

Look ahead, and evaluate

Consider 2-players in a zero-sum game

Opposing objectives

Player A is the Maximizer and moves first

Player B is the Minimizer and follows Player A

Consider 2-players in a zero-sum game

Recall search-trees

Starting with MAX, we can expand the entire game tree

The leaves are terminal states with 1 winner, or draw states


MAX chooses the move that maximizes the minimum payoff

MIN chooses the move that minimizes the maximum payoff

Assumes both players play optimally


Start at bottom, evaluate utility at all leaves

Back up the tree, alternating between MAX and MIN

Once we hit root, we get optimal play sequence

Problems with


Expensive - computes $b^d$ leaves

Wastes computation on obviously bad moves

Recall Uniform Cost Search

Key Idea: Branch and Bound

Alpha Beta Pruning

Alpha Beta Pruning

Idea: Don't compute the entire tree

Compute only what is necessary

Don't compute obviously bad moves

Alpha Beta Pruning

How much less work do we need to do?

Optimal case: $S = 2b^{d/2}$

Average case: pretty close!

More on branching factors

Varies widely between and within games

We can get stuck at some level $d$

Guarantee solution from previous level

Heuristic Alpha Beta Pruning

Use an evaluation function instead of utilities

Especially useful when we can't expand the whole tree