1CS 188: Artificial IntelligenceFall 2008Lecture 6: Adversarial SearchLecture 6: Adversarial Search9/16/2008Dan Klein – UC BerkeleyMany slides over the course adapted from either Stuart Russell or Andrew Moore12Announcements Project 2 is up (Multi-Agent Pacman) Other annoucements:No more Friday project deadlines (makes it hard to No more Friday project deadlines (makes it hard to use slip days) After this week, we’ll use section and drop box for written assignments rather than lecture Sanity checker issues – informal poll Looking for partners? Workload balanced for pairs23Local Search Queue-based algorithms keep fallback options (backtracking)Local search: improve what you have until Local search: improve what you have until you can’t make it better Generally much more efficient (but incomplete)34Hill Climbing Simple, general idea: Start wherever Always choose the best neighborIf no neighbors have better scores than If no neighbors have better scores than current, quit Why can this be a terrible idea? Complete? Optimal? What’s good about it?45Hill Climbing Diagram Random restarts? Random sideways steps?56Simulated Annealing Idea: Escape local maxima by allowing downhill moves But make them rarer as time goes on67Simulated Annealing Theoretical guarantee: Stationary distribution: If T decreased slowly enough,will converge to optimal state! Is this an interesting guarantee? Sounds like magic, but reality is reality: The more downhill steps you need to escape, the less likely you are to every make them all in a row People think hard about ridge operators which let you jump around the space in better ways78Beam Search Like hill-climbing search, but keep K states at all times: Variables: beam size, encourage diversity? The best choice in MANY practical settings Complete? Optimal? Why do we still need optimal methods?Greedy Search Beam Search89Genetic Algorithms Genetic algorithms use a natural selection metaphor Like beam search (selection), but also have pairwise crossover operators, with optional mutation Probably the most misunderstood, misapplied (and even maligned) technique around!910Example: N-Queens Why does crossover make sense here? When wouldn’t it make sense? What would mutation be? What would a good fitness function be?1011Adversarial Search[DEMO: mystery pacman]1112Game Playing State-of-the-Art Checkers: Chinook ended 40-year-reign of human world champion Marion Tinsley in 1994. Used an endgame database defining perfect play for all positions involving 8 or fewer pieces on the board, a total of 443,748,401,247 positions. Checkers is now solved! Chess: Deep Blue defeated human world champion Gary Kasparov in a six-game match in 1997. Deep Blue examined 200 million positions per second, used very sophisticated evaluation and positions per second, used very sophisticated evaluation and undisclosed methods for extending some lines of search up to 40 ply. Othello: human champions refuse to compete against computers, which are too good. Go: human champions refuse to compete against computers, which are too bad. In go, b > 300, so most programs use pattern knowledge bases to suggest plausible moves. Pacman: unknown1213GamesCraftershttp://gamescrafters.berkeley.edu/1314Game Playing Many different kinds of games! Axes:Deterministic or stochastic?Deterministic or stochastic? One, two or more players? Perfect information (can you see the state)? Want algorithms for calculating a strategy (policy) which recommends a move in each state1415Deterministic Games Many possible formalizations, one is: States: S (start at s0) Players: P={1...N} (usually take turns) Actions: A (may depend on player / state) Transition Function: SxA → S Terminal Test: S → {t,f} Terminal Utilities: SxP → R Solution for a player is a policy: S → A1516Deterministic Single-Player? Deterministic, single player, perfect information: Know the rules Know what actions do Know when you win E.g. Freecell, 8-Puzzle, Rubik’s cubecube … it’s just search! Slight reinterpretation: Each node stores a value: the best outcome it can reach This is the maximal outcome of its children Note that we don’t have path sums as before (utilities at end) After search, can pick move that leads to best nodewin loselose1617Deterministic Two-Player E.g. tic-tac-toe, chess, checkers Minimax search A state-space search tree Players alternatemaxmin Each layer, or ply, consists of a round of moves Choose move to position with highest minimax value = best achievable utility against best play Zero-sum games One player maximizes result The other minimizes result8 2 5 6min1718Tic-tac-toe Game Tree1819Minimax Example1920Minimax Search2021Minimax Properties Optimal against a perfect player. Otherwise? Time complexity? O(bm)maxmin Space complexity? O(bm) For chess, b ≈ 35, m ≈ 100 Exact solution is completely infeasible But, do we need to explore the whole tree?10 10 9 100min[DEMO: minVsExp]2122Resource Limits Cannot search to leaves Depth-limited search Instead, search a limited depth of tree Replace terminal utilities with an evalfunction for non-terminal positions-1 -2 4 94min minmax-2 4 Guarantee of optimal play is gone More plies makes a BIG difference [DEMO: limitedDepth] Example: Suppose we have 100 seconds, can explore 10K nodes / sec So can check 1M nodes per move α-β reaches about depth 8 – decent chess program? ? ? ?2223Evaluation Functions Function which scores non-terminals Ideal function: returns the utility of the position In practice: typically weighted linear sum of features: e.g. f1(s) = (num white queens – num black queens), etc.2324Evaluation for Pacman[DEMO: thrashing, smart ghosts]2425Iterative DeepeningIterative deepening uses DFS as a subroutine:1. Do a DFS which only searches for paths of length 1 or less. (DFS gives up on any path of length 2)2. If “1” failed, do a DFS which only searches paths of length 2 or less.…b3. If “2” failed, do a DFS which only searches paths of length 3 or less.….and so on.This works for single-agent search as well!Why do we want to do this for multiplayer games?2526α-β Pruning Example2727α-β Pruning General configuration
View Full Document
Unlocking...