Artificial Intelligence ECS 270
Popular in Course
Popular in Engineering Computer Science
This 138 page Class Notes was uploaded by Ashleigh Dare on Tuesday September 8, 2015. The Class Notes belongs to ECS 270 at University of California - Davis taught by Ian Davidson in Fall. Since its upload, it has received 93 views. For similar materials see /class/187765/ecs-270-university-of-california-davis in Engineering Computer Science at University of California - Davis.
Reviews for Artificial Intelligence
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 09/08/15
Wrapping up Last Lecture Given a set of n data oints and a distance function dXi Xj between a airs of points Partition the data set into a two su sets so that the maximum diameter of the two subsets is minimized 1 Take all pairwise distances and sort them in descending order 2 Take the middle point in the list and set dXi X j alpha 3 Construct a constraint graph by placing an edge between any two points whose distance is in the list and is greater than alpha Each variable has the possible values 12 4 Can we instaniate the variables so all constraints are satisfied Yes then discard all list entries below the middle point No then discard all list entries above and including the middle point 5 Go to 2 with the pruned list unless list contains one element in which case output dXiXj as the minimum maximum diameter Simple Example Two sets of four points on a unit square whose centers are 55 units apart Use Manhattan distances 56 nonzero distances in total How many distances of 1 How many distances of 2 How many distances of 4 How many distances of 5 Simple Example Two sets of four points on a unit square whose centers are 55 units apart Use Manhattan distances 56 nonzero distances in total How many distances of 1 2 per point 8 16 How many distances of 2 1 per point 8 8 How many distances of 4 How many distances of 5 First Step of Algorithm n 28 alpha 433 What does the graph to satisfy look like Can we assign variable values to satisfy all the constraints Second Step of Algorithm n 14 alpha 1 What does the graph to satisfy look like Can we assign variable values to satisfy all the constraints What property of the graph should we look for Third Step of Algorithm n 21 alpha 233 What does the graph to satisfy look like Can we assign variable values to satisfy all the constraints Fourth Step of Algorithm n 18 alpha 2 What does the graph to satisfy look like Can we assign variable values to satisfy all the constraints Fifth Step of Algorithm n 16 alpha 133 What does the graph to satisfy look like Can we assign variable values to satisfy all the constraints SiX Step of Algorithm n 17 alpha 233 What does the graph to satisfy look like Can we assign variable values to satisfy all the constraints List only contains one element so terminate with minimum maximum diameter of 2 Is this right Three Core Parts of AI Course Only search part considers adversarial environment Adversarial Search Outline Game assumptions and creating game trees p161163 Basic minimaX search p163167 Expansion of game assumptions p171173 Evaluation Functions resource limited games of chance three person games Very counterintuitive result Alpha beta pruning p167171 Analysis of alpha beta pruning not in book Techniques used in board playing Aside World champion of Checkers Othello is a machine httpwwwcsualbertacaMchinook Schaffer et39 al Science July 19 h 2007 This paper announces that checkers is now solved Perfect play by both sides leads to a draw In Practice Checkers Chinook ended 40 year reign of human world champion Marion Tinsley in 1994 Use defining perfect play for all positions Chess Deep Blue defeated human world champion Gary Kasparov in a six game match in 1997 Deep Blue searches 200 million positions per second uses very sophisticated evaluation and undisclosed methods for extending some lines of search up to 40 ply Othello human champions refuse to compete against computers who are too good Why Go human champions refuse to compete against computers who are too bad In go I gt 300 so most programs use pattern knowledge bases to suggest plausible moves Games and Search Unpredictable opponent gt solution is a contingency plan Time limits unlikely to find goal must approximate Plan of attack 0 algorithm for perfect play Von Neumann 1944 ofinite horizon approximate evaluation Zuse 1945 Shannon 1950 Samuel 1952 57 0 pruning to reduce costs McCarthy 1956 deterministic chance perm information lmperfem information Games and Search Unpredictable opponent gt solution is a contingency plan Time limits gt unlikely to find goal must approximate Plan of attack 0 algorithm for perfect play Von Neumann 1944 ofinite horizon approximate evaluation Zuse 1945 Shannon 1950 Samuel 1952 57 o pruning to reduce costs McCarthy 1956 deterministic chance perfect information chess checkers backgammon go othello monopoly imperfect information D bridge poker scrabble nuclear war Type of Games We Will Address From a Game Theory Perspective What are some games when there is no turn taking What does this mean 39 ayer is rational Big assumption 00 arge to exhaustively search ie Chess b 35 d 100 Items Required to Build a Game Tree of A Search Initial state Successor function Terminal test So what39s the difference to A Utility function Note MAX player always goes first Consider TicTacToe Informed vs Adversarial Search Previously we covered the differences between the problems these techniques can address Summarize the two aims of the techniques Now lets consider how the data structure searched differs Both have successor functions Informed vs Adversarial Search Differences Informed search can work on a graph but minimax only on a tree Weights are on edges for informed search and nodes for adversarial search Informed search typically solves the shortest path problem but for adversarial this may not be the case instead we do what Optimal Strategy No longer shortest path Rather the minimum maximum utility minimaX Paraphrasing Shakespeare What39s in a name Why Game Trees and Minimax Ignoring the Algorithm What Seems Reasonable Perfect play for deterministic perfect information games Idea choose move to position with highest minimax value best achievable payoff against best play Eg 2 ply game MAX function MiNiMAquEcisioMstutc returns an action are given we MAX VALunstatu return the action in SUCCESSURSUZHE with value 11 function MAX VALUEsmie returns a utility mine if l39EiumNAlr l39Es stute then return UTILiTvsiate m oo for 115 in SUCCESSORSstutE do MAXUM1NVVALUES return it function M1NVALUE5tutz returns a utility mini if TERMINALTEE 1 stutc then return U i39iLiTvstatc or m in SUCCESSORssmlc do w MiNiilAXVALUE5 return 1 CounterIntuitive Result Perfect play for deterministic perfect information games Idea choose move to position with highest minimaz value best achievable payoff against best play Eg 2ply game MAX ln the Nash equilibrium named after who proposed it is a kind of optimal collective strategy in a game involving two or more players where no player has anything to gain by changing only his or her own strategyr Optimal Strategy Max plays A1 Min A1 Even if Min knows what Max is going to play and viceversa neither will change their strategy Solution is an equilibrium in that it maxs Max s payoff and mins Min payoff I39ll Focus on Board Games But this work is applicable to any situation where two players are in an adversarial contest given the assumptions of the game MinimaX Example What type of search variant BFS 0r DFS Write down algorithm as a function MAX MIN Objectives of Algorithm Max39s objective Min39s objective So if we view game playing as search should MaxMin maintain an upper or lower bound on the Nash equilibrium Properties of MinimaX Search Complete Optima Time complexity7 Space complexity Properties of Minimax Search Complete Yes if tree is finite chess has specific rules for this M77 Yes against an optimal opponent Othervvise7 Time complexity7 007 Space complexity 0bm depth first exploration For chess b x 35 m H 11 for quotreasonablequot games exact solution completely infeasible Depth Limited Search lVlINIMAXCUTOFF is identical to lVlINIMAXVALUE except 1 TERMINAL is replaced by CUTOFF 2 UTILITY is replaced by EVAL Evaluation function is just a heuristic not an admissible heuristic Break game state into 111 components Evalm wlclnW2cZn wmcmm Note multiple states have the exact same component values Eval function is some estimate of the the expectation of winsgames from this point as described by the components Linear summation of weighted features assumes independence assumption Cutting of Search Depth is Important Hence The Faster The Better MINIMAXCUTOFF is identical to MINIMAXVALUE except 1 TERMINAL is replaced by CUTOFF 2 UTILITY is replaced by EVAL Does it work in practice b 106 1135 gt m4 4ply lookahead is a hopeless chess player 4 ply z human novice 8ply a typical PC human master l2 ply m Deep Blue Kasparov Evaluation Functions We can t rely on using minimaX to search to the bottom of the tree Need to limit the number of moves to look ahead and then use an evaluation function to return a numerical value for each node at that levelply View the evaluation function as being an approximation to the EXPECTED utility Evaluation function Should order terminal nodes as the true utility would quick strongly correlated with chance of winning Evaluation Functions Black to move White to move White slighin better Blackwinning For chess typically linear weighted sum of feat ire EVAL5 w1f1s w2f2s wnfis eg 7111 9 with f15 number of white queens number of black queens et Example 2D TicTaCToe Depth of tree Number of nodes Evaluation function What are the components How should we score each component Break class in half Each half comes up with an evaluation function for two ply game What Can We Say About the Returned Value by the Algorithm Close Enough is Good Enough MAX M39JN K 1 20 1 1 0 2 0 Behaviour is preserved under any monotonic transformation of EVAL Only the order matters payoff in deterministic games acts as an ordinal utility function Three Player Games A 7 7 77 B 7 7 77 7 7 77 c 7 7 77 7 7 77 7 7 77 7 7 77 A 1 2 3 4 2 1 6 1 2 7 4 1 5 1 1 1 5 2 7 7 1 5 4 5 How do we create game trees that incorporate Chance into two player games Chance as a Bipartisan Third Player In nondeterministic games chance introduced by dice card shuf ing Simplified example with coin flipping MAX CHANCE EXPECTLMINIMAX gives perfect play Just like MINIMAX except we must also handle chance nodes if state is a MAX node then return the highest EXPECTIMINIMAX VALUE of SUCCESSORsstate if state is 3 MIN node then return the lowest EXPECTIMINIMAX VALUE of SUCCESSORsstate if state is a chance node then return average of EXPECTIMINIMAX VALUE of SUCCESSORsstate function MINIMAXDECS0NstntE retums rm action or MAX VALunstutz return the action in SUCCESSOItSstate with value 1 function MAXNALUEUiaie returns a utility value it l nuwmmr l nsmzm then return UTYIJTYUiuie for 115 in Suecnssonsbmm do u MAxuM1NrVALuns return 11 function MINVALUEstate returns a utility value if l39ntanAL TESrstntE then return UTILITY5tat or m in Successonshmm do u MN1rMAX VALUEs return 1 Minimax AlgorithmWhat s Going On Let s draw the tree as constructed by the algorithm Perfect play for deterministic perfect information games Idea choose move to position with highest minimum value best achievable payoff against best play Eg 2 ply game MAX What does this value mean A 3 Alpha Beta Pruning Two interpretations to algorithm or explanation of its behavior Efficient computation Via pruning search space Search space pruning Via rational behavior of players Alpha Beta Pruning Interpretation 1 43622195315475 Role play the algorithm s calculations sic Write down as a function What values can be left out and still get the Nash equilibrium Alpha Beta Pruning Smne branches ill never be played by rational players since the include ub optitnul decisions For either player MAX MIN MAX WIite down as a function Result 1 AX MIN V1 AX nmlL s hm u rc In wr uplorul 5 What is Vital to the success of this approach Write down as a function aB pruning example Interpretation 2 mm M N aB pruning example MAX M H aB pruning example MAX M H aB pruning example MAX M H aB pruning example MAE M N MM M I N aB pruning example Alpha Beta Pruning Algorithm function ALPHAVBETAVSEARCI52ME returns an action inputs state current state in game IH MAX VALIJE5tatE 700 return the aetilm in SU CESSORSsmlc with value u function MAXVVALUELstaZEmr retums a atiltty ualae inputs slate current state in game a the value of the best alternative for MAX along the path to state 1 the value of the best alternative for MIN along the path to state if 391EttMlNAtr391ESTstata then return UTlLll Y5tutE re foo n Suconssottslstate do E 5 m return 1r function MlN VALuEstatea returns a utility value inputs state current state in ame a the value of the best alternative for MAX along the path to state the value of the best alternative for MIN along the path to state if TEtuquALrTEs stata then return UrrLrTystate l 4 00 for as in SUCCESSORS3tatE do 11 IVIIN u MAerALUMamm if 1 S a then retum 39 t M1N u return 11 Same as minimax Except a Maintain alphabeta value for each node b Test for irrational behavior Why are these reasonable tests of irrational behavior Note alpha and beta are never returned by the algorithms Alpha Beta Pruning Why Alpha AND Beta hey include subopumul decisions rm either player Some branches lll never be played by x aliunul players since After explote this part of the nee what can we say Alpha Beta Pruning Why Alpha AND Beta MAX MAX When we explote this part of the tIee what can we say Who does the pruning min or max Why Think of 13911 terms of at least and at most Alpha Beta Pruning Why Alpha AND Beta MAX MAX 4 9 5 3 5 When we explote this part 0 e nee what can we say Do we prune the 2 and 1 nodes Alpha Beta Pruning Why Alpha AND Beta MAX MAX 9 5 3 5 When we explote this part 0 e nee what can we say Do we prune the 2 and 1 nodes Why not This is why we Characterize Max s situation as a tight best casemax lower bound Alpha Beta Pruning Why Alpha AND Beta MAX MAX When we explote this part of the nee what can we say Do we prune the 9 and 5 nodes Why not This is why we Characterize Mill s situation as a tight best casemin upper bound Together Alpha and Beta Are What What does the search through the tree do to Alpha and Beta Result MAX MIN lAX nodes that were never explored 5 What is Vital to the success of this appIoaCh When would we prune at the bottom a node say quot2 in this tree When we know that will never this How can we be sure of this Max prunes quot2 when 6 gtelte alphbeta Properties of aB Pruning does not affect final result Good move ordering improves effectiveness of pruning With quotperfect orderingquot time complexity 0bm2 9 doubles depth of search A simple example of the value of reasoning about which computations are relevant a form of metareasoning Alpha Beta Pruning Produces exact same results as niinirnax algorithm Reduces search by not expanding sub optimal paths Alpha and Beta terms are the floor and ceiling of the range of values the player is interested in Some Logistical Observations Alpha and Beta are lower and upper bounds on the Nash equilibrium MaX fills in alpha Min fills in beta Why MaX and min will eventually converge and we get the Nash equilibrium of the game An observation of a payoff can either Tighten the bounds Fall outside the bounds Parents pass down estimates of alpha and beta so far to Children by value Alphabeta pruning example Step 1 a is the maximum lower bound of possible solutions MAX plays 3 is ihe minimum upper bomcl of possible solutions MIN plays 45353 I So what does Alpha and beta 5 Represent 450533 435 Max fills left hand alpha value Min fills in right beta value 539 Parent can set current best ooltm Estunates for alpha and beta 2 I IF n lm all grf The ahmlazim Fm MM altsHg flu pa rh m shini ll13939 wall all the alternatqu I m 51131 Hl pafh quot1 gm THEN WHY SHOULD IT BE a is the maximn lower buunc l of possible snlLtims MAX plays 6 is the minimum unper bumd of possible snlutions MIN plays Should not it be that MAX maintains the upper bound and MIN the lower bound Alphabeta pruning example Step 2 a is he maxirrum lower bound of possible solutions MAX plays FOI thlS path 5 is he minimum upper boLnd of possible solutions l 4m 1 ms worst min can Alphabeta pruning example Ste 39 39 m b SND do is 5 maxlrru lower ound of possible solutions HM paw SN 0 4315 lt 5 is he minimum upper boLnd of possible solutions MIN plays iii SNE Even without seeing The rest of the tree If Min plays rationally For this path They will allow a Pay 0ff worst max can No greater than 5 dois5 Alphabeta pruning example Step 4 a is he maxirrum lower bound of possible solutions MAX plays 5 is he minimum upper boLnd of possible solutions MIN plays Q7 Alphabeta pruning example Step 5 a is he maxirrum lower bound of possible solutions MAX plays 5 is he minimum upper boLnd of possible solutions Mi39 plays 55 Irrational for MAX to ever Play this path Alphabeta pruning example Step 6 xirrum lower bound of possible solutions MAX plays i i he ma 5 is he min mum upper boLnd of possible solutions MIN plays 3 Alphabeta pruning example Step at is he maxirrum lower bound of possible solutions MAX plays 5 is he minimum upper boLnd of possible solutions MIN plays 3 Alphabeta pruning example Step 8 a is he maxirrum lower bound of possible solutions MAX plays 5 is he minimum upper boLnd of possible solutions MIN DIEDquot T Alphabeta pruning example Step 9 a is he maxirrum lower bound of possible solutions MM plain lt 5 is he minimum upper boLnd of possible solutions MIN plays 427 Alphabeta pruning example Step 10 a is he maxirrum lower bound of possible solutions MAX plays 5 is he minimum upper boLnd of possible solutions MEI Mays T Alphabeta pruning example Step 11 a is he maxirrum lower bound of possible solutions HM plays 5 is he minimum upper boLnd of possible solutions MIN plays 5ltN D Alphabeta pruning example Step 12 a is he maxirrum lower bound of possible solutions MAi pays 5 is he minimum upper boLnd of possible solutions MIN plays Expand the node next to 3 Since it is RATIONAL that Min could rede ne MAX S lower bound Alphabeta pruning example Step 13 o 39s 39 m b possible solutions max mm 5 is he minimum upper boLnd of possible solutions MIN plays I But it doesn t If 7 was say 4 then It would have Alphabeta pruning example Step 14 a is he maxirrum lower bound of possible solutions MAX plays 7 5 is he minimum upper boLnd of possible solutions MIN play Alphabeta pruning example Step 15 a is he maxirrum lower bound of possible solutions MA peeve 5 is he minimum upper boLnd of possible solutions MIN plays 7 Alphabeta pruning example Step 16 a is the maxirrum lower bound of possible solutions MAX plays 7 6 is the minimum upper bomd of possible solutions MIN plays Alphabeta pruning example Step 18 a is ihe maxirrum lower bound of possible solutions MAX play 5 is he minimum upper bomd of possible solutions MIN plays s1 31 Alphabeta pruning example Step 17 a is ne maxirmm lower bound of possible solutions MAX plays 7 3 is ihe minimum upper bomd of possible solutions Mm plan Initial call is to MAXVALUEr00tn0de oltgt 00 Alpha lt Beta otherwise cutoff search AlphaBeta pruning it m game gmuugnme Ileatnptmn inputs mm curlem 7 5513mm rm M x aln g ma mm mm as39t gems rm mm along the rum tnimm il no mime Illl ll relurn EVALLWIE rDl i39nl39ll x in SUH I39SKDRHVMIEI I0 r 42 MM RHWNV Ur Hm15 it 393 5 then mm 5 end mlum a I39Ilnclirm MIN TU HI mm gmm in return the mmmm value DH39MIL i 0Lrwmm Inn ulum Emwml DI earl ll SUIT RMEl ID 7 Min of max values mm Men My gunk g j hm mm a Irlumj Lets Try Algorithm On This Example Alpha beta pruning example Step 18 a is ihe maximum lower bound of possible solutions MAX plays 5 is the minimum upper bomd of possible solutions MIN plays Analysis of Alpha Beta Pruning Knuth D E and Moore R W An analysis of AlphaBeta pruningquot Artificial Intelligence 6293326 1975 Most results for perfectly ordered trees Some for randomly ordered trees Performance analysis of AlphaBeta Pruning Since alphabeta pruning performs a minimaX search while pruning much of the tree its effect is to allow a deeper search with the same amount of computation The question how much does alphabeta improve performance and when When should alphabeta prune the most Example of alphabeta best case Evaluation from left to right Best case analysis Obd2 What does this mean in practice 9 096 12 l Note when Min is playing last the best order is monotonically decreasing The Proof sketch MAX MIN 412 v 7 300 lilii For b 3 and d 3 we need to expand 11 nodes What type of state values do we have in this tIee What information do we need to know an exact value What information do we need to know a bounded value The Proof 2 We want to know how many expansions we have to do to get an exact value the Nash Equilibrium Let Sk be the min of states kply away to expand to get an exact value Let Rk be the min of states kply away to expand to get a bounded value b is the branching factor Sk1 Rk1 The Proof 3 Sk1 Sk b1Rk Rk1 Sk SORO1 53 2 52 b1R2 51 b1R1 b1S1 50b1R0b1S0b1S0 b1R0 2 1 b1 b1 b11b1 12b 2bb2 b 1 b 1 2 NZ b 1 oc b2 The Proof 4 We said we can look twice as far ahead with alphabeta pruning How can we express this with respect to Sk The Proof 5 We said we can look twice as far ahead with alphabeta pruning Without alpha beta pruning Sk2 b28k With alpha beta pruning Sk2 lt b228k lt 2bSk The Proof 6 Sk2 Sk1 b1Rk1 What do we want to do The Proof 6 Sk2 Sk1 b1Rk1 What do we want to do Sk b1Rk b1Sk bSk b1Sk1 lt 2b1Sk why lt2bSk Why MinimaX value of game trees The most natural definition for the average case is that the leaf nodes are randomly ordered Heuristic node ordering would Violate this assumption Average case performance is not a prediction of its performance in practice N graph search 1 Start With OPEN eentainlng just the in rtial state 2 Until a geal IS feund er there are ne nedea en DPEN de at Seleet the node an OPEN W the Ieweet f 39uv alue b Generate its sueeeaaere e Fer eaeh aueeeaser de i If it hasn39t been gewera ted betere tie it39s net in CLGSED J evaluate it add it In UPEN and reeerd its parent ii If it hae heen generated Defere change the parent if39thia new path is better than the preview ene In that ease update the Beat ef getting te th ia nude and to any eueeeeeere that th is nede may already in ave Th en add Example on Graphs Ail 39 ix 4 1 ER ETD 62 D 3 EN EN 413 EH Gi Haj h3g3 J1i MERE Eff r 1123 K4 12 L 3 Mm m5 m5 P13 mm H133 3r 56 5 3910 Tim LI D Hunters in parentheses are hm I Numbers on edges are aperator gusts 48 Informed Search Chapter 4 ermghlrhne dlsume m Enchamsx What trends do you see 5quot as Egan mum Vila an What do these mean Closed CSZG S591 A366 5393 RV413 H415 B450 CSZG RV607 A366 5393 RV413 F4lS P4l7 Completeness of Aquot n A expands nodes in increasing order of f n 80 it must eventually reach a goal state unless there are infinitely many nodes with fn lt f which is possible only if Completeness of A n A expands nodes in increasing order off So it must eventually reach a goal state unless there are infinitely many nodes with fin lt f which is possible only if there is a node with an infinite branching factor there is a path with a finite path cost but an infinite number of nodes along it A is complete on locally finite graphs graphs with a finite branching factor provided there is some positive constant 6 such that every operator costs at least 6 Optimality at N n We want ta prawa that N is aptimal law it will always fiihcl the heat aaltitiah Tarminalagy f is the mat at the optimal aalutiah path f ith because the hauriatic ia admiaaihlagr igga Will Liaa a grant by E l ltfadl tl l l Ramambarthat all giaal atataa have hm If X J Dp imal gnal slate Subnptirral gnal stale H318 be an marina guel same am I132 be a Sub p jmal goal state Aasunme m n is cm thne antimal pail m g and Has rm been expanded Aslswne that GE is atmut it be exclaimed Whns cantradncls the asswmptim l mam IE2 is sub p mal Th r f 39 A newer sele s a Subnep jnnal gmal fur expanaim K tel G be en epti nel geel state em 32 be a subepliittel gravel state Assume that n is en the eptimel path m g email has net been expended Assttme that 32 is ebeut is be Etta eseei ded t x E Eirteeh is admissible f ft n l If I ll n is met eltesen Her expensiee then 1 Elm tt isgt D t Therelere t WEE 1 But since G2 is e geel state les 3 339 Elias E ENG21 5 gigs This CDNI EUECIE the EESUI Tl39I ll l that 32 is Dp ml 99339 Summim39 subsptir39rtlel Therefete A newer selects stale gnal state e subeeptimel geel fer expansiert 55 N is maximally eftieient Fer e given heuristic funetieni rte eptimel elgerithm ie guaranteed te eie ieee vveriz Aside tmm tiee m f i W expene everyr rtetie rteeeeeerv fer the parent that we ve teurid the eherteet path arid rte unneeeeeerv nedee That is every node with fn lt fG is expanded Why Robot navigation fN gN hN with hN straightline distance from N to goal Cost of one horizontalvertical step 1 Cost of one diagonal step 2 57 A Is Admissible Heuristics Good Enough In some examples we will find that items on the Closed lists need to be updated as there were multiple paths to the same node ie previous example How can we overcome this X y The admissible heuristic h is consistent or satisfies the monotone restriction if for every node N and every successor N of N Use a Consistent Heuristic hN s cNN hN N triangular inequality CN N What does this really mean N hm Counter example hN i K J The admissible heuristic h is consistent or satisfies the monotone restriction if for every node N and every successor N of N Use a Consistent Heuristic hN s cNN hN N triangular inequality CN N What does this really mean N hm Travel times in cars hN i K J Claims If h is consistent then the function f along any path is nondecreasing great for d ugging cNN hN Proof hN39 If h is consistent then whenever A expands a node it has already found an optimal path to the state associated with this node y If h is consistent then the function f along any path is nondecreasing great for d ugging Claims fNgNhN CW fN gNcNN hN N m hNS cNN hN fN s fN WNW5 If h is consistent then whenever A expands a node it has already found an optimal path to the state associated with this node K J Another View Lemma A expands nodes in order of increasing f value Gradually adds fcontoursquot of nodes cf breadthfirst adds layers Contour i has all nodes with f j where fi lt le For h n 0 what will the bands look like9 D 39 CSl 535 lntmdumnn m M Lettures 6 63 Let Open be a list centaiming the initial state Loop If Open is EItiIJty return failure Node lt1 chpiiomnl Closed Puethode Closed If Node is a goal then return the path from initial state t0 Node El se expand Nedeg meme the newly generated States into Open sort upen f in I End LDDp What39s in the closed list Inventing Admissible Heuristics List constraints for environment RelaX constraints to obtain admissible heuristics since constraints increase cost K J 82Puizzrle Inventing Admissible Heuristics How goa 82Puzzle 2 I goa h1N number of misplaced tiles h2N sum of distances of each tile to goal are both consistent 67 Which one is better A A For TSP Example Search tree What is an admissible heuristic Recall how we created admissible heuristics before Wellknown example travelling sale Find the shorter mun visiting all cit Wellknuwn example travelling salesperson problem TSP Find the shortest tour visiting all citi5 exactly once Wellknuwn example travelling salesperson problem TSP Find the shortest tour visiting all CitiE exactly once An Example OfAN nimmn Spanning Tm must 7 W hat these mean What trends do you see do m Enchamsx Ami ermghlrhne dlsume Open Closed A366 5393 T447 2449 A366 RV413 H415 2449 A646 0671 A366 5393 H415 H417 2449 CSZG 5553 A366 5393 RV413 bff zmw 450 CSZG S591 A366 5393 RV413 H415 B418 2449 B450 CSZG RV607 C615O671 A366 5393 RV413 H415 H417 Following Results Are for A With K Consistent Heuristics y Some Proofs of A Behavior 1 In A for any node n n is extracted from OPEN iff fn lt fg 3 How can we prove this What does it really mean K J Some Proofs of A Behavior 1 In A for any node n n is extracted from OPEN iff fn lt fg 3 How can we prove this What does it really mean K J Some Proofs of A Behavior 1 In A for any node n n is extracted from OPEN iff fn lt fg 3 Proof gt If part What type of condition is this lt Only if part What type of condition is this K J Some Proofs of A Behavior 1 In A for any node n n is extracted from OPEN iff fn lt fg 3 Proof gt If part Sufficient condition lt Only if part Necessary condition K J Some Proofs of A Behavior 1 In A for any node n n is extracted from OPEN iff fn lt fg 3 Proof gt If part Sufficient condition P gt Q lt Only if part Necessary condition Qgt P K J Some Proofs of A Behavior 1 In A for any node n n is extracted from OPEN iff fn lt fg 3 Proof gt If part What does this really show Consider any node m on the optimal path in the state search graph fIn gmhm lt gmhm fm lt fg Furthermore some element of the optimal path will always be in OPEN so they will be expanded lt Only if part K Some Proofs of A Behavior 1 In A for any node n n is extracted from OPEN iff fn lt fg 3 Proof gt If part What does this really show Cons1der any node m on the optimal path in the state search graph fIn gmhm lt gmhm fm lt fg Furthermore some element of the optimal path will always be in OPEN so they will be expanded lt Only if part Consider a node m such that fm lt fg Since f is computed for a node only if m has been or is going to be in OPEN m is at some point in OPEN and will be extracted since it has a better value than fg wat would be a misinterpretation of this theorem and pry 79 Some Proofs of A Behavior 2 FACT If A1 and A2 are two versions of the Agt lt algorithm using respectively heuristic functions h1 and h2 where h1 is more informeddominates than h2 then A1 dorninates A2 ie every node opened by A1 is also opened by A2 Proof K J Some Proofs of A Behavior 2 FACT If A1 and A2 are two versions of the Agt lt algorithm using respectively heuristic functions h1 and h2 where h1 is more informeddominates than h2 then A1 dorninates A2 ie every node opened by A1 is also opened by A2 Proof Consider a node n opened by A1 We have fg gtf1n gnh1n gt gnh2n f2n We have already seen that Agt lt opens all nodes where fn lt fg Thus n will be opened by A2 K J Some Proofs of A Behavior 3 PAC T Any consistent heuristic h is admissible Proof Some Proofs of A Behavior 3 PAC T Any consistent heuristic h is admissible Proof We need to show that for all n hn lt hn Consider the goal optimal state g reachable from n Then because of consistency hn lt cnghg cng hn Some Proofs of A Behavior A FACT In the sequence of nodes n1 n2 opened by the A algorithm we have fn1 lt fn2 lt Proof ACT A will never move a node from CLOSED to I PEN K J Some Proofs of A Behavior A FACT In the sequence of nodes n1 n2 opened by the A algorithm we have fn1 lt fn2 lt Proof Suppose for all the nodes expanded up to i1 we have fs fn1 lt fn2 lt fn3 lt lt fni1 The next node opened ni is the successor of one of those nodes say Hi Thus fHi gnihni gnjCnjnihni gt gnj hnj gt f n39 Proof A ter 39 y success1ve visit to a node n will have the same h value and an increasing g value Thus the value of f at n will not decrease thus n will not move from CLOSED back to OPEN K Avoiding Repeated States in A If the heuristic h is consistent then Let CLOSED be the list of states associated with expanded nodes When a new node N is generated If its state is in CLOSED then discard N If it has the same state as another node in the fringe then discard the node with the largest f K J In Your Class Groups of Three 14 u L mdw m A A colorsInitially H L 39 39 L39 4 4 L r 39 r L L museum degrees to reach the goal state shown below a Formulate solving Rubik s cube as an informed search problem that uses A Give details on the b List two admissible heuristics for this problem that can be used with Ah 0 Consider a two player version of Rubik s cube where your opposition is a random process that r V yum variation of one of the above two heuristics ECSZ7O AI Course Overview Lecture What is AI A Classic AI Problems and Algorithm A Course Overview Course Logistics K J What is Al Typically in computer science classes you will program a computer to perform some well defined computationtask in some closedstatic environment Example Al problems are more challenging Win against many opponents at checkerschess Learn to recognize what differentiates a male from a female face Given a set of axioms What theorems can be proved Guiding principle As per text modern Al is designing computer programs to behave rationally 2 What A1 Is Not Acting or Thinking Like a Human Turing 1950 Computing machinery and intelligencequot Can machines thinkquot gt Can machines behave intelligentlyquot ltgt Operational test for intelligent behavior the Imitation Game Emuquot HUMAN quot 39 INTEHROGATOR Predicted that by 2000 a machine might have a 30 chance of fooling a lay person for 5 minutes Anticipated all major arguments against Al in following 50 years Suggested major components of Al knowledge reasoning language understanding learning ltgt ltgtltgt Many prizes millions of for passing the Turing test but not a lot of effort C51 535 Introduction to AI Lecture 1 3 Key TasksProblems in AI Searching for shortest pathssolutions in the presence of obstacles Search for best sequence of moves in an adversarial environment Reasoning in the presence of certainty Reasoning in the presence of uncertainty Learning from Ve and Ve feedback Planning ie a shortest path planning in Video games SeaFCh Medical diagnosis systems Eggsgirgngg or Voice recognition ie checking flight status g39 Game playing ie Checkers Rubik s cube Chless Theorem proving Examples of AI Applications Practical Motivation SzPlanning ie a shortest path planning in video games RzMedical diagnosis systems LzVoice recognition ie checking flight status LWritten letter recognition ie scanning of zip codes on letters Academic Motivation SzGame playing ie Checkers Rubik s cube Chess RzTheorem proving AI Is practical But I will give many simple examples for clarity teXt book s coauthor Norvig is the CTO aka Director of Search Quality Google 4 any of the Topics Will Involve a Clever problem representation b Algorithms with strong performance bounds guarantees First Module a UninformedInformed Search X J What data structure could we use to represent these search problems I Grade I39ll focus on route planning problems but approaches applicable to Shortest tours Layout problems Robot navigation Assembly sequences Internet searching K Beyond Route Planning J For any algorithm that searches the tree what would we like to know about it39s performance Performance Guarantees K J For any algorithm that searches the tree what would we like to know about it39s performance a Complete b Optimal C Time complexity 1 Space complexity K J Performance Guarantees Single State Problem Definition A problem is defined by four items l ogrators or successor function Sw eg Arad gt Zerind Arad gt Sibiu eg at Aradquot etc goal test can be explicit eg a7 at Bucharestquot implicit eg NoDirta path wst additive eg sum of distances number of operators executed etc A solution is a sequence of operators leading from the initial state to a goal state Eight State Puzzle 77 operators goal test77 M7 BE 1W gag E E m 7M5 Sun Slut Eight State Puzzle E E E EE E Shirl SIMIL iunl Sum m integer Iacations of tiles ignom intermediate positions MW move blank left right up clam ignore unjamming etch goal test goal state given Bath cost 1 per move E Meta Optimal aalutiom 01F nPuzzle famin is MP hard Syllabus I Date Topic Search I S ouroe 035110 Info m ed Search A c Metropolis Hastings Algorithms RN Cl l pb l 3 for review R N Chapter 4 Cansn int Sa qj ttc ar l Problems B aok tracking Search Loc a search RN Chapter 5 Adversa af Search M in in so A lph a beta pron in g RN Chapter 6 Reasoning Syllabus II H irh P rch 05139 ff anal Laugh I Chapter 7 Resolution Furw arc B ack W 31111 Ch aim in g W39Tn39 First Order Logic lChapter s and 9 Unification Forw arc I39B ack w ard ch aim in g The Ofelle PIT VETS W i th G rap h FCm39 quotlfadefs Chapter 13 1 1 Exact Inference quotvia variable elimination NI Cquot M C 5 amp lars Learning H Fth Cr39 r39a phicaf fodefs Chapter 2D Expectation max 1111 iza39rion Hidden Mm kov Models Text Russell and NorVig AI 2Ild Edition Logistics and Expectations 1 Mailing List slides posted after lecture at wwwcsucdaVisedudaVidsoncoursesEC827009 Meeting times Class TuT h 9001020am Wellman 233 My Office hoursTu1030noon daVidsoncsucdaVisedu Your expected to attend lectures ask questions and discuss with other students You39ll need to read before the lecture 2 X exams on fundamentals 2 x team programming assignments search and connect 4 and 1 written mework Class participation will be a significant part 0 16 your grade Programming Assignments Infrastructure typically given Assign 1 Route planning on topological maps climb Mt Saint Helens twist Assign 2 Connect 4 Search in an adversarial environment J
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'