6 Adversarial Search

Game playing state-of-the-art

checkers: 1950, first computer player, 1994, first computer champion: Chinook ended a 40-year reign of champion Marion Tinsley using a complete 8-piece endgame, 2007, checkers was solved
Chess: In 1997, Deep Blue defeated Garry Kasparov in 6 game match. Deep Blue examined 200M positions per second and used very sophisticated evaluation and undisclosed methods to extend some lines of search up to 40 ply. Current programs are even better, if less historic
Go: 2016 AlphaGo defeated the human champion. uses Monte Carlo tree search, a learned evaluation function
Pac-man???

Behavior from computation

non-deterministic behaviour
What would the model do if a certain "X" thing happened in the world

Types of game

many different kinds of games
axes
deterministic or stochastic
one, two or more players
zero sum?
perfect information
Want algorithms for calculating a strategy (policy) that recommends a move from each state.

policy \(\pi(\text{state}) = \text{action}\)

Deterministic games

many possible formations, one is
states \(S\) (start at \(s_0\))
players: \(P\{1, N\}\) usually take turns
actions: \(A\) (may depend on player/state)

Zero-sum game

agents have opposite utilities (values on outcomes)
Let's think of a single value that one maximizes and the other minimizes
adversarial, pure competition

General Games

agents have independent utilities (values on outcomes)
cooperation, indifference, etc.

Adversarial search

for the zero-sum case

COMPARISON

Single agent trees

For example, Pac-Man can only go left and right, and there's a series of actions I can take until I reach all the pips

The tree of possible futures that can project out from any state in the problem.

The value of the state is the best achievable outcome (utility) from that state

Non-terminal states \(V(s) = \max(V(s')) \text{ s.t. } s' \in \text{children}(s)\)

              max
             (8)
            /   \
          (8)   (3)
         /  \   /  \
        8    2 3    1

Adversarial Game trees

The root node may be my node, but the children of that node are not under my control; their children are decided by my adversary, though I know the moves they can make.

Each node can be scored by expanding out the tree to the terminal states

the numbers

                 MAX = 3
               /    |    \
            MIN=3  MIN=2  MIN=2
            /  \   /  \   /  \
           3   17 2   8  2   14

Minimax values

In a minimax tree, the terminal states have values
Some terminal states are good for me, and some of them are bad for me
The agent that gets to choose their best node will pick not what u want; they are maximizing their utility
so they will minimize your utility
instead of the max at every part of the node where

Adversarial search: Minimax

deterministic, zero-sum games
tic tac toe, chess, checkers
One player maximizes the result
other player minimizes the result
minimax search
a state space search tree
players alternate turns
Compute each node's minimax value: the best achievable utility against a rational (optimal) adversary

                    ▲ 3                 MAX picks the largest child
                /   |   \
             ▼      ▼      ▼            MIN picks the smallest child
            /|\    /|\    /|\
          3 12 8  2 4 6  14 5 2         terminal utilities

Minimax implementation:

Calculate the value from the state

def value(state):
    if state is terminal: return utility(state)
    if next agent is MAX:  return max_value(state)
    if next agent is MIN:  return min_value(state)

def max_value(state):
    v = -∞
    for successor in successors(state):
        v = max(v, value(successor))
    return v

def min_value(state):
    v = +∞
    for successor in successors(state):
        v = min(v, value(successor))
    return v

Minimax example

simulate all the children, so now we can start the computation

How efficient is minimax?

just like (exhaustive) DFS
time \(O(b^m)\)
space: \(O(b^m)\)

GAME TREE PRUNING

How to truncate the tree

Let's go back to the minimax example

the min nodes, the smallest nodes

alpha beta pruning

general config (min version)
we computing the min value at some node \(N\)
we looping over \(n\)'s children
\(n\)'s estimate of the childrens min is dropping
who cares about \(n\)'s value? MAX
let \(a\) be the best value that MAX can get at any choice point along the path from the root
if \(n\) becomes worse than \(a\), MAX will avoid it so we can stop considering \(n\)'s other children (it's alr bad enough that it won't be played)
Max is symmetric

AB pruning properties

this pruning has no effect on minimax value computed for the root
values of intermediate nodes might be wrong

resource limits

problem: in realistic games we cannot search to leaves
solution: depth limited search
instead search only to a limited depth
replace terminal utilities with an eval function for non-terminal positions
examples
suppose we have 100s and we can explore 100k node per sec
we can check 1M nodes per move
ab pruning reaches about depth 8
guarantee optimal play is gone
more plies make a big difference
use anytime to

Why pacman starves

danger of replanning with adversarial agents
he knows his score will go up by eating now
he know his score will go up after eating the dot later
there are no point scoring opportunities

Evaluation functions

Score non-terminals in depth limited search
ideal function: returns the actual minimax value of the position
In practice, approximate, eg. a weighted linear difference between the number of black and white pieces, etc.

evaluation for pac man

Depth matters

evaluation function are always imperfect
the deeper the tree the function is buried the less the quality of the eval matters
an important example of the tradeoff between complexity of features and consumption of resources