New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here


by: Adele Schaden MD


Marketplace > University of California Riverside > ComputerScienence > CS 170 > INTRO TO ARTIFICIAL INTELLIGENCE
Adele Schaden MD
GPA 3.88

Eamonn Keogh

Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Eamonn Keogh
Class Notes
25 ?




Popular in Course

Popular in ComputerScienence

This 4 page Class Notes was uploaded by Adele Schaden MD on Thursday October 29, 2015. The Class Notes belongs to CS 170 at University of California Riverside taught by Eamonn Keogh in Fall. Since its upload, it has received 33 views. For similar materials see /class/231743/cs-170-university-of-california-riverside in ComputerScienence at University of California Riverside.

Similar to CS 170 at UCR

Popular in ComputerScienence




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: 10/29/15
Heuristic Search The search techniques we have seen so far Breadth first search Uniform cost search a a g lt o e o o o p ing Bidirectional Search are all too slow for most real world problems Sometimes we can tell that some states appear better that others 1 23 4 5 6 7 8 FWC we can usethis knowledge ofthe relative ment ofstates to gulde search Heuristic Search informed search A Heuristic is afunction that when applied to astate returns a number that is an estimate ofthe men39t ofthe state with respect to the oal In other words the heuristic tells us approximately how far the state is from the goal state ote we said approximately Heuristics might underestimate or overestimate the merit ofa state But for reasons which we will see heuristics that unly underestimate are very desirable and are called admissible Heuristics for 8puzz1e I 1 2 3 Cur rmt state 4 5 L 7 I s Thenumberof misplaced les not including Goal II theblankgt State H i In this case only 3 is misplaced so theheuristic functlon evaluates to l Notation hn hcurrent state 1 Heuristics for 8puzz1eH 2 spaces 39The Manhattan Dismnce not including the blank 3 Spaces In this case only the s and 1quot tiles are misplaced by z 3 and 3 squares respectively so 3 spaces the heuristic functhn evaluates to 8 Total 8 Notation hn hcurrent state 8 an use heuristics to guide hill climbing search In this example the Man attan Distance heuristic helps us quickly find a solution to the 8puzzle But hill climbing has 0 2 aptamen n E5 In this example hill climbing does not work local minima Note that this puzz e is solvable in just 12 more steps We have seen two interesting algorithms Uniform Cost Measures the cost to each node 1s optimal and complete Can be very slow Hill Climbing Estimates how far away the goal is Is neither optimal nor complete Can be very fas an we combine them to create an optimal and complete algorithm that is also very fast Uniform Cost Search Emu mdcsmmderorcost Irltwttan as M the cheapest node Where the cost 15 we path castgm Hill Climbing Search ucuc nodes in order or esnmied dlstnnce to 0 17 19 17 19 1 14 Intutttan EXpand the node you think is nearest to goal Where the esttmcte ofdtrtchce to god ts hm The A Algorithm AStar mm nusmmmsmtmm gn is the cost to get to anode hn is the estimated distance to the goal fln gn Mn Note that we can use the general search algorithm we used before All that we have changed is the queuing strategy Lfthe heuristic is optimistic that is to say it never overestimates the distance to the goal then Aquot is optimal and complete Iniormsl pronoutline oI A completeness Assume that every operator has some minimum positive cost EPSZIUVL Assume that a goal state exists therefore some finite set of operators lead to it Expanding nodes produces paths whose actual costs increase by at least epsilon each time since the algorithm will not terminate until it finds a goal state it must expand a goal state in finite time Iniormsl pronoutline oI A optimality he M 39 ates ithas found agoalstate All remaining nodes have an estimate cost to goal n greater than or equal to that of goal we have found since the heuristic function was optimistic the actual cost to goal for these other paths can be no better than the cost ofthe one we have already found How fast is A A is the isstest Search algorithm That is for any given heuristic no algorithm can expand fewer nodes than M How fast is it Depends ofthe quality ofthe heuristic Lfthe heuristic is useless ie hn is hardcoded to equal 0 the algorithm degenerates to uniform cost Lfthe heuristic is perfect there is no real search we just march down the tree to the goal Generally we are somewhere in between the two situations above The time taken depends on the quality ofthe heuristic Two Player Games Adversarial Search Max alvmysmovesfirst Mn is the opponent We have enence in search where we assume that we are the We have exp only intelligent being and we have explicit control overthe world An initial state A set ofoperat or Max Vs Min A terminal test which tells us when the game is over A utility function evaluation function Lets consider what happens when we relax those assumptions The utility function is like the heuristic function we have seen in the past except it evaluates a node in terms ofhow good it is for each p ayer positive values indicate states advantageous for Max negative values indicate states advantageous forMin A simple abstract game Max makes amove then Min replies I X 0 X 0 X X 0 X X X 0 X X X Tennlnal O X States 0 O X 0 1 O 1 Utility is calledamwe The Minimax Algorithm Generate the game tree down to the terminal nodes Apply the utility function to the terminal nodes siblin n par V Recursiver do the above until the backedup Wlues reach the 39 tlal ate The value ofthe initial state is the minimum score for Max score ofat least 3 Althuugn the Mlmmax algnnthm ls uptannalthere ls apmblem Example Utlllty Functlons l The tune nmplexlty ls ow where 5 ts the effeeuve branching TIE Ta Tne factnr and m ls the depth nfthe terminal states Assume Max ls uslng X the nan cannean snyunnntnu museum anusuyunn nanny son 0 one pnsslble suluuunls tn dn depth limited Mlmmax Search swaths gamete 9mm as eepasyvucmm lfnlswlnfurMaxw naues Ew1unt39hfrmg 39h39hewhwfmwan lfn ls wln fur Mm e w 201 6 e 4 2 Eackupthzvaluestathzmwt Ichaasebestmave repeat else Wewmld luau hutwedm39t l anmmIaxnn have nmmwe t cutnff numbernfmws enlumns and dlagnnals O X X thu rungnnu wmaxplmelttn avallable tn Max 7 number nfrnws O m 52 W 39 eulumns and dlagnnals avallable tn Mm 201 4 e l Example Utility Functions H Example Utility Functions HI Chess I Chess II 1 55quot Max Wh w The prevmus evaluatlnn funan nawely Assume eaeh piecehas the fullnwlng values gavethe samewaauttn amaze regardhsss XX XX l W nfltsnnslunn nnthebnard 5 knight 39 lusth Let Xhe the numbEr nfsquares the lvh Xx XX hunk pleee attaeks uee 7 let w Sum nfthe value nfwhlte pieces 201 let 5 sum nfthe value nfblack pleees a X X pleeewalue X placezvalue x2 M Nate thutthswlu ranges hzw mm all nuunn the nnpensntthns hunk u XX W t b betweznl unuLl thamz ml Dll lxlthmlcmbr awalglltzd my mnltlmml39tlv places mu 3mm pammn Utility Functions AlphaBeta Pruning I We have seen thatthe abllltytn play a gnnd game ls hlghly dependant unthe evaluauun functmns w an we came up with gnarl evaluatinn functinns39 We have seen hnwtn use Mlmmax searchtn play an npunnal game We have seen thatbecause nftlme Intemew an exvert llmltatmns wemay havetn use M achme Leamlng X s uaetahle Using a utnff eauses prnblems heeause nfthe hmnznn effect s there same way we ean Search deeper tn the same amnunt nfhme7 Yesl Use AlpharBeta Prunlng


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


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'

Why people love StudySoup

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

Kyle Maynard Purdue

"When you're taking detailed notes and trying to help everyone else out in the class, it really helps you learn and understand the I made $280 on my first study guide!"

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Parker Thompson 500 Startups

"It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.