CS 188: Artificial Intelligence Fall 2006AnnouncementsMotion as SearchDecomposition MethodsApproximate DecompositionHierarchical DecompositionSkeletonization MethodsVisibility GraphsSlide 10Probabilistic RoadmapsRoadmap ExamplePotential Field MethodsPotential FieldsAdversarial SearchGame Playing State-of-the-ArtGame PlayingDeterministic Single-Player?Deterministic Two-PlayerTic-tac-toe Game TreeMinimax ExampleMinimax SearchMinimax PropertiesResource LimitsEvaluation FunctionsEvaluation for PacmanIterative Deepening- Pruning Example- Pruning- Pruning Pseudocode- Pruning PropertiesNon-Zero-Sum GamesStochastic Single-PlayerStochastic Two-PlayerSlide 36What’s Next?CS 188: Artificial IntelligenceFall 2006Lecture 7: Adversarial Search9/19/2006Dan Klein – UC BerkeleyMany slides over the course adapted from either Stuart Russell or Andrew MooreAnnouncementsProject 1.2 is up (Single-Agent Pacman)Critical update: make sure you have the most recent version!Reminder: you are allowed to work with a partner!Change to John’s section: M 3-4pm now in 4 EvansMotion as SearchMotion planning as path-finding problemProblem: configuration space is continuous Problem: under-constrained motionProblem: configuration space can be complexWhy are there two paths from 1 to 2?Decomposition MethodsBreak c-space into discrete regionsSolve as a discrete problemApproximate DecompositionBreak c-space into a gridSearch (A*, etc)What can go wrong?If no path found, can subdivide and repeatProblems?Still scales poorlyIncomplete*Wiggly pathsGSHierarchical DecompositionBut:Not optimalNot completeStill hopeless above a small number of dimensions Actually used in practical systemsSkeletonization MethodsDecomposition methods turn configuration space into a gridSkeletonization methods turn it into a set of points, with preset linear paths between themVisibility GraphsShortest paths:No obstacles: straight lineOtherwise: will go from vertex to vertexFairly obvious, but somewhat awkward to proveVisibility methods:All free vertex-to-vertex lines (visibility graph)Search using, e.g. A*Can be done in O(n3) easily, O(n2log(n)) less easilyProblems?Bang, screech!Not robust to control errorsWrong kind of optimality?qstartqgoalqstartVoronoi DecompositionAlgorithm:Compute the Voronoi diagram of the configuration spaceCompute shortest path (line) from start to closest point on Voronoi diagramCompute shortest path (line) from goal to closest point on Voronoi diagram.Compute shortest path from start to goal along Voronoi diagramProblems:Hard over 2D, hard with complex obstaclesCan do weird things:Probabilistic RoadmapsIdea: just pick random points as nodes in a visibility graphThis gives probabilistic roadmapsVery successful in practiceLets you add points where you need themIf insufficient points, incomplete, or weird pathsRoadmap ExamplePotential Field MethodsSo far: implicit preference for short pathsRational agent should balance distance with risk!Idea: introduce cost for being close to an obstacleCan do this with discrete methods (how?)Usually most natural with continuous methodsPotential FieldsCost for:Being far from goalBeing near an obstacleGo downhillWhat could go wrong?Adversarial Search[DEMO 1]Game Playing State-of-the-ArtCheckers: 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.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.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: unknownGame PlayingAxes: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 stateDeterministic Single-Player?Deterministic, single player, perfect information:Know the rulesKnow what actions doKnow when you winE.g. Freecell, 8-Puzzle, Rubik’s cube… it’s just search!Slight reinterpretation:Each node stores the best outcome it can reachThis is the maximal outcome of its childrenNote that we don’t store path sums as beforeAfter search, can pick move that leads to best nodewin loseloseDeterministic Two-PlayerE.g. tic-tac-toe, chess, checkersMinimax searchA state-space search treePlayers alternateEach layer, or ply, consists of a round of movesChoose move to position with highest minimax value = best achievable utility against best playZero-sum gamesOne player maximizes resultThe other minimizes result8 2 5 6maxminTic-tac-toe Game TreeMinimax ExampleMinimax SearchMinimax PropertiesOptimal against a perfect player. Otherwise?Time complexity?O(bm)Space complexity?O(bm)For chess, b 35, m 100Exact solution is completely infeasibleBut, do we need to explore the whole tree?10 10 9 100maxmin[DEMO2: minVsExp]Resource LimitsCannot search to leavesLimited searchInstead, search a limited depth of the treeReplace terminal utilities with an eval function for non-terminal positionsGuarantee of optimal play is goneMore plies makes a BIG difference[DEMO 3: limitedDepth]Example:Suppose we have 100 seconds, can explore 10K nodes / secSo can check 1M nodes per move- reaches about depth 8 – decent chess program? ? ? ?-1 -2 4 94min minmax-2 4Evaluation FunctionsFunction which scores non-terminalsIdeal function: returns the utility of the positionIn practice: typically weighted linear sum of features:e.g. f1(s) = (num white queens – num black queens), etc.Evaluation for Pacman[DEMO4: evalFunction]Iterative 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
View Full Document