Adversarial Search

How should you play against an opponent?

Games

Game playing: solving search problems in competitive (usually unpredictable) multi-agent environments.

Simplest games:

Games are interesting because

Simple classification

 Perfect InformationImperfect Information
DeterministicGo, Chess, Othello, Kalah, ...Stratego, ...
Non-deterministicBackgammon, ...Poker, Scrabble, ...

Games as search problems

Game has

Players have to find contigent strategies. An optimal strategy assumes an infallible opponent. Can be found with minimax evaluation.

Minimax Evaluation

Expand the game tree depth first out to a certain number of ply. Evaluate nodes at the fringe, using the utility function if it's a leaf, or a heuristic evaluation function otherwise. (It's okay if there are terminal nodes occuring before the depth limit.) One player (MAX) likes big scores, the other (MIN) likes small scores. Record mins and maxes up the tree as you backtrack.

Minimax gives best results against an optimal opponent.

minimax.png

Alpha Beta Pruning

Keep track of, for each node,

Prune as soon as you see something worse than the current α or β. Works the best if you can order successors by how good they are for you; theoretically this can cut run time from Θ(bm) to Θ(bm/2) doubling the search depth that can be explored in a given duration... but still not good enough to completely solve chess.

Search in Practice

Lots of room for cleverness

Be Careful!

If more than two players,

Other Algorithms

Evaluation Functions

The evaluation function gives an estimate of the utility of a node. A good evaluation function must obviously:

Usually done as a linear weighted combination of features

w1f1(s) + w2f2(s) + ... + wnfn(s)

Examples of features (from Chess)

But in reality

Where do the weights and features come from?

Exercise: Define features and weights for Othello, Kalah, and TicTacToe.

Games of Chance

Game trees have chance nodes. Edges in are moves, edges out are the dice rolls (or equivalent) labeled with the probability of occurrence.

TODO

Exact values do matter, unlike in deterministic games where only the relative ordering of values mattered.

TODO

Games of Imperfect Information

TODO

State of the Art