# Announcements

## HW1 Autograder is borked - fixes in progress

## Keep an eye on campuswire!

# CORRECTION

## 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

## THE ENVIRONMENT

### Multi-agent

### Competitive

### Zero-sum

### Turn-based

### Perfect information

## 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

# Minimax

## MAX chooses the move that maximizes the minimum payoff

## MIN chooses the move that minimizes the maximum payoff

## Assumes both players play optimally

# Minimax

## 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

# Minimax

## Expensive - computes $b^d$ leaves

## Wastes computation on obviously bad moves

# Recall Uniform Cost Search

## Key Idea: Branch and Bound

# 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