CS 188 Artificial Intelligence Fall 2009 Lecture 6 Adversarial Search 9 15 2009 Dan Klein UC Berkeley Many slides over the course adapted from either Stuart Russell or Andrew Moore 1 Announcements Written 1 has been up Search and CSPs Project 2 will be up soon Multi Agent Pacman Other annoucements None yet 2 1 Today Finish up Search and CSPs Start on Adversarial Search 3 Tree Structured CSPs Theorem if the constraint graph has no loops the CSP can be solved in O n d2 time Compare to general CSPs where worst case time is O dn This property also applies to probabilistic reasoning later an important example of the relation between syntactic restrictions and the complexity of reasoning 4 2 Tree Structured CSPs Choose a variable as root order variables from root to leaves such that every node s parent precedes it in the ordering For i n 2 apply RemoveInconsistent Parent Xi Xi For i 1 n assign Xi consistently with Parent Xi Runtime O n d2 why 5 Tree Structured CSPs Why does this work Claim After each node is processed leftward all nodes to the right can be assigned in any way consistent with their parent Proof Induction on position Why doesn t this algorithm work with loops Note we ll see this basic idea again with Bayes nets 6 3 Nearly Tree Structured CSPs Conditioning instantiate a variable prune its neighbors domains Cutset conditioning instantiate in all ways a set of variables such that the remaining constraint graph is a tree Cutset size c gives runtime O dc n c d2 very fast for small c 7 Tree Decompositions Create a tree structured graph of overlapping subproblems each is a mega variable Solve each subproblem to enforce local constraints Solve the CSP over subproblem mega variables using our efficient tree structured CSP algorithm M1 SA NT r SA g Q b NT b SA g Q r Q NSW SA shared vars Q M4 Agree on WA r SA g NT b WA b SA r NT g NT shared vars SA shared vars NT M3 Agree on Agree on WA M2 NSW Q SA Agree M1 M2 WA g SA g NT g NT g SA g Q g 8 4 Iterative Algorithms for CSPs Local search methods typically work with complete states i e all variables assigned To apply to CSPs Start with some assignment with unsatisfied constraints Operators reassign variable values No fringe Live on the edge Variable selection randomly select any conflicted variable Value selection by min conflicts heuristic Choose value that violates the fewest constraints I e hill climb with h n total number of violated constraints 9 Example 4 Queens States 4 queens in 4 columns 44 256 states Operators move queen in column Goal test no attacks Evaluation c n number of attacks DEMO 10 5 Performance of Min Conflicts Given random initial state can solve n queens in almost constant time for arbitrary n with high probability e g n 10 000 000 The same appears to be true for any randomly generated CSP except in a narrow range of the ratio 11 Hill Climbing Simple general idea Start wherever Always choose the best neighbor If no neighbors have better scores than current quit Why can this be a terrible idea Complete Optimal What s good about it 12 6 Hill Climbing Diagram Random restarts Random sideways steps 13 Simulated Annealing Idea Escape local maxima by allowing downhill moves But make them rarer as time goes on 14 7 Summary CSPs are a special kind of search problem States defined by values of a fixed set of variables Goal test defined by constraints on variable values Backtracking depth first search with incremental constraint checks Ordering variable and value choice heuristics help significantly Filtering forward checking arc consistency prevent assignments that guarantee later failure Structure Disconnected and tree structured CSPs are efficient Iterative improvement min conflicts is usually effective in practice 15 Game 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 undisclosed methods for extending some lines of search up to 40 ply Current programs are even better if less historic Othello Human champions refuse to compete against computers which are too good Go Human champions are beginning to be challenged by machines though the best humans still beat the best machines In go b 300 so most programs use pattern knowledge bases to suggest plausible moves along with aggressive pruning Pacman unknown 16 8 GamesCrafters http gamescrafters berkeley edu 17 Adversarial Search DEMO mystery pacman 18 9 Game Playing Many different kinds of games Axes 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 state 19 Deterministic 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 A 20 10 Deterministic 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 cube 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 the max value Note that we don t have path sums as before utilities at end After search can pick move that leads to best node lose win lose 21 Deterministic Two Player E g tic tac toe chess checkers Zero sum games max One player maximizes result The other minimizes result min Minimax search A state space search tree Players alternate Each layer or ply consists of a round of moves Choose move to position with highest minimax value best achievable utility against best play 8 2 5 6 Slightly different from the book definition 22 11 Tic tac toe Game Tree 23 Minimax Example 24 12 Minimax Search 25 Minimax Properties Optimal against a perfect player Otherwise max Time complexity O bm min Space complexity O bm For chess b 35 m 100 10 Exact solution is completely infeasible But do we need to explore the whole tree 10 9 100 DEMO minVsExp 26 13 Resource Limits Cannot search to leaves 4 Depth limited search Instead search a limited depth of tree Replace
View Full Document
Unlocking...